Download Research Tools
Ever mistype your query in a search engine? Or just flat out misspell it? Of course you have—we all do, especially when our search involves “spelling demons” like minuscule, millennium, or embarrassment. Or personal names: believe it or not, there are more than 500 ways that Britney Spears has been misspelled on the web. Misspellings and typos make it difficult for search engines to give users the best results.
Better spelling algorithms can get users to the information they seek, without their having to carry around a dictionary or scroll through several pages of results. Quality spelling algorithms become even more relevant when the searcher is using a smartphone, as it is difficult to browse through page after page of results on those tinier screens.
With this in mind, Microsoft Research and Microsoft Bing launched the Speller Challenge, encouraging participants worldwide to compete in creating a spelling algorithm that generates the most plausible alternatives for web search queries. Participants were able to access real-world data at web scale by using the Microsoft Research Web N-gram Services. Moreover, participants were able to improve their algorithm and see how it compared to other spelling correction systems by using an evaluation service that we made available to them.
More than 300 participants registered for the Speller Challenge, representing every continent (well almost; no one actually registered from Antarctica) and including researchers from academia, research laboratories, and industry. Winners were automatically selected, based on how well their system performed with respect to figuring out the best spelling alternatives (for example, “Britney Spears” for “briteny spears”). On Tuesday, July 19, we hosted a workshop at Bing headquarters, where Harry Shum, corporate vice president of Bing, presented the winners their prizes. Congratulations to everyone who took part in the program:
Finally, here are a few remarks from first-place winner Gord Lueck:
“Microsoft has been a leader in offering visibility into search data for research purposes. Big data is the driver of many of the tools that make the Internet useful. Through Microsoft, some of that data is now available to the community at large to build up and design algorithms with. It’s this generosity and openness that has allowed many independent researchers, such as myself, to design a high quality software product that leverages these valuable data.
“A very good quality dataset for training was given to the researchers, providing a benchmark against which to compare their work in near real-time against other researchers in the same field. This quick feedback cycle undoubtedly helps to accelerate the pace of research beyond that which might have occurred in an environment where data and methods are hoarded and protected.”
Gord also noted that the competition focused on U.S. English spellings, pointing out that “it would have been nice to see some more variety in input languages and grammars.” Sounds like an idea for another contest!
—Evelyne Viegas, Director of Semantic Computing, Microsoft Research Connections
The beautiful interior of the Eidgenössische Technische Hochschule’s (ETH, the Swiss Federal Institute of Technology) main building in Zurich is always abuzz with conferences at the end of June, including TOOLS—and this year was no exception. Now in its forty-ninth iteration, TOOLS was a week-long event that brought together four major conferences, eight workshops, and a tutorial on the subject of programming languages, models, components, and proofs.
ETH is a world-famous institute for science and technology; it has produced 21 Nobel Prize winners since its inception in 1855—with seven since 1975—a top score among European universities. Perhaps ETH is more widely known as the place where Albert Einstein began his studies. The chair of Software Engineering is held by Bertrand Meyer, who started the TOOLS Conference Series in 1989 with conferences held in different continents: TOOLS Europe, TOOLS USA, TOOLS Pacific, and TOOLS China. Eight people from Microsoft were right at the center of the event this year.
With program committees spread across the world, holding a program committee meeting to discuss the selection of the papers for the conference is a challenge—but one that TOOLS has always met. This year, I had the honor of serving as program co-chair of one of the conferences, and Ethan Jackson was program co-chair of another. The collected papers from TOOLS are available as a volume entitled Objects, Components, Models, Patterns in the prestigious Lecture Notes in Computer Science series, published by Springer.
The program committee meeting for 2011 was held in Zurich in March with 16 members present and 16 listening in from various regions ranging from India to the United States’ west coast. With very careful planning, papers were scheduled for discussion according to the time zone in their reviewers’ regions. Thus, Aditya Nori from Microsoft Research India was brought in first, and Nikolai Tillmann from Microsoft Research Redmond, Washington, had to rise very early to discuss his papers at the end of the meeting.
Other Microsoft researchers who participated in the conference week included Yuri Gurevich, the conference co-chair of TAP (Tests and Proofs), and program committee members of the various conferences: Nikolaj Bjorner, Clemens Syzperski, Margus Veanes, and Madhu Sudan. (I should note that Nikolaj Bjorner and his team are well known for having popularized the use of testers through RiSE4fun, which enables the tools to be run in browsers.)
Patrice Godefroid presented the keynote address for one of the conferences: TAP 2011. He discussed his work with the SAGE tool for white-box testing technology. Test generation has recently become the largest application of SMT solvers as measured by computational usage. Satisfiability Modulo Theories (SMT) are concerned with checking the satisfiability of logical formulas over one or more theories. At Microsoft, the Z3 SMT solver has solved more than 2 billion constraints in the past two years as a sub-component of SAGE, the first white-box fuzzer. Fuzz testing is an effective technique for finding security vulnerabilities in software. Traditionally, fuzz-testing tools apply random mutations to well-formed inputs of a program and test the resulting values.
Patrice Godefroid - Automated Whitebox Fuzz Testing with SAGE
Since 2009, SAGE has been running non-stop on more than 100 (on average) machines, automatically “fuzzing” hundreds of applications in a dedicated lab that is owned by the Windows security test team. In the process, SAGE found many new expensive security vulnerabilities (which were missed by black box testing and static program analysis).
—Judith Bishop, Director of Computer Science, Microsoft Research Connections
If you wanted to be certain that the best IT minds were focused on research into some of today’s most challenging societal problems, what would you do? How would you ensure that there is a global pipeline of computer-science talent? If you’re Microsoft Research, you would set aside US$1.4 million a year to fund the Microsoft Research Faculty Fellowship program.
The 2011 Faculty Fellows receive their awards at the Microsoft Research Faculty Summit. Left to right: Microsoft Research Senior Vice President Rick Rashid, Brent Waters, Keith Noah Snavely, Anderson Rocha, Shwetak Patel, Alistair McEwan, Jure Lescovec, Krishnendu Chatterjee, Maria Florina Balcan, and Microsoft Research Connections Corporate Vice President Tony Hey. (Courtesy Microsoft Corporation)
Now in its seventh year, this program has named 40 academic researchers whose exceptional talent for research and thought leadership make them stand out in their fields. Each Fellow receives up to US$200,000 to pursue breakthrough, high-impact research. The grant is an unrestricted gift, providing the Fellows the freedom to plan their research, hire graduate students, build labs, and acquire equipment. In addition to the monetary grant, each Fellow also receives software, invitations to academic and professional conferences, and the opportunity to work directly with leading computer scientists at Microsoft Research.
During the 2011 Microsoft Research Faculty Summit, currently in progress in Redmond, Washington (July 18 to 20), we were delighted to announce the recipients of the 2011 Microsoft Research Faculty Fellowships. These stellar researchers were chosen through a rigorous, multi-tier selection process that involved more than 100 expert reviewers. The reviewers looked for future academic leaders who are at the beginning of their careers. Microsoft’s goal is to encourage these early-career faculty and help them work on the kind of high-risk/high-reward research that often is overlooked by traditional funding mechanisms.
With these goals in mind, the selection criteria included not only the capability to pursue cutting-edge research, but also the personal leadership skills that are necessary to bring those ideas to fruition and to communicate complex concepts in a way that inspires and intrigues. The review process winnowed the list of candidates down to 18 finalists, who were then interviewed in person by a panel of Microsoft Research executives and researchers, along with faculty members from some of the nation’s leading universities.
Out of this arduous process emerged eight of the best and brightest young researchers—men and women who not only have interesting research agendas, but who also have demonstrated the potential to do great work throughout their careers. So, without further ado, here are this year’s Microsoft Research Faculty Fellows:
So, how do the newest Faculty Fellows feel about their selection? The following are responses from two of them.
Shwetak Patel, an assistant professor at the University of Washington (departments of Computer Science & Engineering and Electrical Engineering), conducts research in a variety of areas such as energy monitoring technology for the home and health-monitoring technologies that use mobile phones and a sensing system, and has been collaborating with Microsoft Research on natural user interface technologies.
Reflecting on the Faculty Fellowship, Professor Patel observed that “The biggest benefit of the fellowship is not just the award, but the exposure of my work to the rest of MSR [Microsoft Research] and the MSR connections that come from it. In addition, my students are going to equally benefit from working with MSR through these joint projects.
“This is a great honor and it is very respected by the community. The MSR Faculty Fellowship is probably one the most prestigious junior faculty awards out there and certainly the most prestigious corporate faculty fellowship.”
Anderson Rocha, an assistant professor at the University of Campinas (Institute of Computing), is working on new machine-learning and computer-vision techniques to help solve problems that are related to digital document forensics.
Professor Rocha proudly noted that his selection breaks new ground. “As far [as] I was told, I'm the first Latin American researcher actually working in Latin America to get this award. Therefore, it means a milestone in the sense it can motivate other young researchers in this region to keep working and believing they are also capable of achieving international recognition for their work.
“The award is an extra motivation for me and my students to keep pursuing digital forensics and innovative techniques to investigate solutions for helping law enforcement agencies in Brazil and abroad in their daily fight against organized crime.”
Professors Patel and Rocha exemplify the drive and intellect of all eight of our new Faculty Fellows. We are proud to welcome them into the fold, and we look forward to helping them advance computer science’s contributions to the future of society and our planet.
—Tom McMail, Senior Research Program Manager, Microsoft Research Connections