News in Briefs

Homomorphic encryption is one of the most exciting new research topics in cryptography, which promises to make cloud computing perfectly secure. With it, a Web user would send encrypted data to a server in the cloud, which would process it without decrypting it and send back a still-encrypted result.

Sometimes, however, the server needs to know something about the data it’s handling. Otherwise, some computational tasks become prohibitively time consuming — if not outright impossible.

Suppose, for instance, that the task you’ve outsourced to the cloud is to search a huge encrypted database for the handful of records that match an encrypted search term. Homomorphic encryption ensures that the server has no idea what the search term is or which records match it. As a consequence, however, it has no choice but to send back information on every record in the database. The user’s computer can decrypt that information to see which records matched and which didn’t, but then it’s assuming much of the computational burden that it was trying to offload to the cloud in the first place.

Last week, at the Association for Computing Machinery’s 45th Symposium on the Theory of Computing — the premier conference in theoretical computer science — researchers from MIT’s Computer Science and Artificial Intelligence Laboratory, together with colleagues at the University of Toronto and Microsoft Research, presented a new encryption scheme that solves this problem. Known as a functional-encryption scheme, it allows the cloud server to run a single, specified computation on the homomorphically encrypted result — asking, say, “Is this record a match?” or “Is this email spam?” — without being able to extract any other information about it.

“This is a very, very general paradigm,” says Shafi Goldwasser, the RSA Professor of Electrical Engineering and Computer Science, one of the paper’s co-authors and, together with her fellow MIT professor Silvio Micali, the most recent recipient of the Turing Award, the highest award in computer science. “Say we’re talking about the surveillance cameras of the future, which come up with encrypted images. Why would we want to do that? It’s a question of liberty versus safety. If you’re looking for a suspect, you might be interested in doing some computations on an encrypted image, to match to the subject. Another possibility would be a medical database, where all the information is encrypted and … someone [runs] a drug study on those blood samples — but just that drug study, nothing else. Our result is in some sense the first result showing that you can do this very generally.”

Joining Goldwasser on the paper are Raluca Ada Popa, a graduate student in the Department of Electrical Engineering and Computer Science, her advisor, associate professor Nickolai Zeldovich, and Yael Kalai of Microsoft Research and Vinod Vaikuntanathan of the University of Toronto, both of whom did their graduate work at MIT with Goldwasser.

Near misses

The researchers built their functional-encryption scheme by fitting together several existing schemes, each of which has vital attributes of functional encryption, but none of which is entirely sufficient in itself. The first of those is homomorphic encryption.

Another is what’s known as a garbled circuit, a technique developed in the mid-1980s and widely used in cryptography. A garbled circuit lets a user decrypt the result of one cryptographically protected operation on one cryptographically protected data item — say, “Is this record a match?” The problem is that, if the garbled circuit is used on a second data item — “How about this record?” — the security breaks.

Moreover, a garbled circuit is a so-called private-key system, in which only the holder of a secret cryptographic key can encrypt data. Homomorphic encryption, by contrast, is intended as a public-key system — like most of the encryption schemes used to protect financial transactions on the Web. With public-key encryption, anyone can encrypt a message using a key that’s published online, but only the holder of the secret key can decrypt it.

The final component technique is called attribute-based encryption. Attribute-based encryption is a public-key system, and it’s reusable. But unlike garbled circuits and homomorphic encryption, it can’t reveal the output of a function without revealing the input, too.

The new system begins with homomorphic encryption and embeds the decryption algorithm in a garbled circuit. The key to the garbled circuit, in turn, is protected by attribute-based encryption. In some sense, the garbled circuit can, like all garbled circuits, be used only once. But the encryption schemes are layered in such a way that one use grants the server access to a general function rather than a single value. It can thus ask, of every record in a database, “Is this a match?”

Zeldovich points out that since the scheme relies on homomorphic encryption, it shares the major drawback of existing homomorphic schemes: They’re still too computationally intensive to be practical. On the other hand, he says, “It’s so new, there are so many things that haven’t been explored — like, ‘How do you really implement this correctly?’ ‘What are the right mathematical constructions?’ ‘What are the right parameter settings?’” And, Popa adds, in the four years since the invention of the first fully homomorphic encryption scheme, “People have been shaving off many orders of magnitude in performance improvements.”

Besides, even a currently impractical functional-encryption scheme is still a breakthrough. “Before, we didn’t even know if this was possible,” Popa says.

Ran Canetti, a professor of computer science at Boston University, corroborates that assessment. “It’s an extremely surprising result,” he says. “I myself worked on this problem for a while, and I had no idea how to do it. So I was wowed. And it really opens up the door to many other applications.”

One of those applications, Canetti says, is what’s known as program obfuscation, or disguising the operational details of a computer program so that it can’t be reverse-engineered. “Not obfuscating the way that people are doing it now, which is just scrambling up programs and hoping nobody will understand, and eventually, these are broken,” Canetti says, “but really obfuscating so that it’s cryptographically secure.”

Canetti acknowledges that the researchers’ scheme won’t be deployed tomorrow. But “I’m sure it’s going to lead to more stuff,” he says. “It’s an enabler, and people will be building on it.”
By web.mit.edu

Dennis Freeman, professor of electrical engineering, has been appointed as MIT’s next dean for undergraduate education, effective July 1, Chancellor Eric Grimson announced today. Freeman succeeds Daniel Hastings, the Cecil and Ida Green Education Professor of Aeronautics and Astronautics and Engineering Systems, who has served as dean for undergraduate education since 2006.

In describing Freeman’s commitment to undergraduate education, Grimson said, “He brings to the job many years of dedication to undergraduate teaching, curricular innovation, thoughtful advising and mentoring and creative experiments in lab-based, lecture-based and online-based education.” Freeman served as education officer in the Department of Electrical Engineering and Computer Science (EECS) from 2008 to 2011, and currently serves as the department’s undergraduate officer.

Freeman has a lengthy record of leadership on committees charged with supporting and governing the undergraduate experience at MIT. He has served on the Committee on Curricula, the Task Force on the Undergraduate Commons, the Educational Commons Subcommittee, the Committee on Global Educational Opportunities for MIT Undergraduate Education, the Corporation Joint Advisory Committee and the Institute-wide Planning Task Force, and has chaired the Committee on the Undergraduate Program.

An exceptional educator, Freeman has received numerous teaching awards, including the Ruth and Joel Spira Award for Distinguished Teaching, the Irving M. London Teaching Award and the Bose Award for Excellence in Teaching. He has been a MacVicar Faculty Fellow since 2006, and has on three occasions been the students’ selection as the best academic advisor in EECS.

He recently contributed to the development and teaching of 6.01 (Introduction to EECS I), which introduces software engineering, feedback and control, circuits, probability and planning in a series of hands-on activities involving a mobile robot. Last fall, he worked with EECS department head Anantha Chandrakasan to launch the department’s new “SuperUROP” program, which attracted 77 students to complete yearlong research projects.

Freeman is a member of the Research Laboratory of Electronics, where his group studies cochlear micromechanics. His group was the first to directly measure sound-induced motions of cells and accessory structures in the inner ear. Earlier this spring, the group discovered a new mechanism that could help explain the sensitivity and frequency selectivity of human hearing.

Through leadership of the offices that comprise the DUE — the Admissions Office, Global Education and Career Development, the Office of Experiential Learning, the Office of Faculty Support, the Office of Minority Education, the Office of the Registrar, the Office of Undergraduate Advising and Academic Programming, ROTC Programs, Student Financial Services and the Teaching and Learning Laboratory — the dean for undergraduate education holds a wide range of responsibilities that support and enhance integrated student learning inside and outside of the classroom.

Grimson described the importance of the dean’s role in reimagining the future of an MIT education. “With the evolution of MITx under the new Office of Digital Learning,” Grimson said, “I expect Professor Freeman to play a key collaborative role in furthering the development of new approaches to residential education.”

Freeman will also work to bring a recent faculty resolution on freshman advising to fruition. At last month’s Institute Faculty Meeting, the faculty approved a motion that calls on the administration — and the dean for undergraduate education, in particular — to partner with the faculty governance system to ensure that every freshman is paired with an MIT faculty member.

Freeman believes that technological advances are enabling entirely new ways to think about teaching and learning. “The potential of MITx is not only improved access to content,” he said, “but also the development of entirely new modes of interaction for members of the MIT community.” A strong advocate of MIT’s Undergraduate Research Opportunities Program (UROP), Freeman envisions a future in which MITx can enable even more opportunities to learn by doing. “If we can rely on a solid foundation built on MITx, then faculty will have more freedom to interact with students in projects and UROPs.”

Freeman also believes that technological advances could transform other important aspects of the undergraduate experience. “Students want and deserve information about the best possible subjects to achieve their career goals,” he said. “Imagine a system in which students and faculty could access not only comments from end-of-term surveys, but also access advice from successful alumni about the kinds of experiences that were helpful in their careers. Such a system is not technologically difficult, but could add new dimensions to student advising.”

Freeman is a fellow of the Acoustical Society of America. He received an SB degree in electrical engineering from Pennsylvania State University, and SM and PhD degrees in electrical engineering and computer science from MIT.

Professor of Biology Graham C. Walker chaired the search committee, whose members also included faculty members Steve Graves, Anette “Peko” Hosoi, John Ochsendorf, Christine Ortiz, Julie Soriero, Gigliola Staffilani, Collin Stultz and Kai von Fintel; students Chris Smith, Grace Young and Anu Sinha; and senior associate dean Elizabeth Reed.
By web.mit.edu

Reinforcement learning is a technique, common in computer science, in which a computer system learns how best to solve some problem through trial-and-error. Classic applications of reinforcement learning involve problems as diverse as robot navigation, network administration and automated surveillance.

At the Association for Uncertainty in Artificial Intelligence’s annual conference this summer, researchers from MIT’s Laboratory for Information and Decision Systems (LIDS) and Computer Science and Artificial Intelligence Laboratory will present a new reinforcement-learning algorithm that, for a wide range of problems, allows computer systems to find solutions much more efficiently than previous algorithms did.

The paper also represents the first application of a new programming framework that the researchers developed, which makes it much easier to set up and run reinforcement-learning experiments. Alborz Geramifard, a LIDS postdoc and first author of the new paper, hopes that the software, dubbed RLPy (for reinforcement learning and Python, the programming language it uses), will allow researchers to more efficiently test new algorithms and compare algorithms’ performance on different tasks. It could also be a useful tool for teaching computer-science students about the principles of reinforcement learning.

Geramifard developed RLPy with Robert Klein, a master’s student in MIT’s Department of Aeronautics and Astronautics. RLPy and its source code were both released online in April.

Every reinforcement-learning experiment involves what’s called an agent, which in artificial-intelligence research is often a computer system being trained to perform some task. The agent might be a robot learning to navigate its environment, or a software agent learning how to automatically manage a computer network. The agent has reliable information about the current state of some system: The robot might know where it is in a room, while the network administrator might know which computers in the network are operational and which have shut down. But there’s some information the agent is missing — what obstacles the room contains, for instance, or how computational tasks are divided up among the computers.

Finally, the experiment involves a “reward function,” a quantitative measure of the progress the agent is making on its task. That measure could be positive or negative: The network administrator, for instance, could be rewarded for every failed computer it gets up and running but penalized for every computer that goes down.

The goal of the experiment is for the agent to learn a set of policies that will maximize its reward, given any state of the system. Part of that process is to evaluate each new policy over as many states as possible. But exhaustively canvassing all of the system’s states could be prohibitively time-consuming.

Consider, for instance, the network-administration problem. Suppose that the administrator has observed that in several cases, rebooting just a few computers restored the whole network. Is that a generally applicable solution?

One way to answer that question would be to evaluate every possible failure state of the network. But even for a network of only 20 machines, each of which has only two possible states — working or not — that would mean canvassing a million possibilities.

Faced with such a combinatorial explosion, a standard approach in reinforcement learning is to try to identify a set of system “features” that approximate a much larger number of states. For instance, it might turn out that when computers 12 and 17 are down, it rarely matters how many other computers have failed: A particular reboot policy will almost always work. The failure of 12 and 17 thus stands in for the failure of 12, 17 and 1; of 12, 17, 1 and 2; of 12, 17 and 2, and so on.

Geramifard — along with Jonathan How, the Richard Cockburn Maclaurin Professor of Aeronautics and Astronautics, Thomas Walsh, a postdoc in How’s lab, and Nicholas Roy, an associate professor of aeronautics and astronautics — developed a new technique for identifying pertinent features in reinforcement-learning tasks. The algorithm first builds a data structure known as a tree — kind of like a family-tree diagram — that represents different combinations of features. In the case of the network problem, the top layer of the tree would be individual machines, the next layer would be combinations of two machines, the third layer would be combinations of three machines, and so on.

The algorithm then begins investigating the tree, determining which combinations of features dictate a policy’s success or failure. The relatively simple key to its efficiency is that when it notices that certain combinations consistently yield the same outcome, it stops exploring them. For instance, if it notices that same policy seems to work whenever machines 12 and 17 have failed, it stops considering combinations that include 12 and 17 and begins looking for others.

Geramifard believes that this approach captures something about how human beings learn to perform new tasks. “If you teach a small child what a horse is, at first it might think that everything with four legs is a horse,” he says. “But when you show it a cow, it learns to look for a different feature — say, horns.” In the same way, Geramifard explains, the new algorithm identifies an initial feature on which to base judgments and then looks for complementary features that can refine the initial judgment.

RLPy allowed the researchers to quickly test their new algorithm against a number of others. “Think of it as like a Lego set,” Geramifard says. “You can snap one module out and snap another one in its place.”

In particular, RLPy comes with a number of standard modules that represent different machine-learning algorithms; different problems (such as the network-administration problem, some standard control-theory problems that involve balancing pendulums, and some standard surveillance problems); different techniques for modeling the computer system’s environment; and different types of agents.

It also allows anyone familiar with the Python programming language to build new modules. They just have to be able to hook up with existing modules in prescribed ways.

Geramifard and his colleagues found that in computer simulations, their new algorithm evaluated policies more efficiently than its predecessors, arriving at more reliable predictions in one-fifth the time.

RLPy can be used to set up experiments that involve computer simulations, such as those that the MIT researchers evaluated, but it can also be used to set up experiments that collect data from real-world interactions. In one ongoing project, for instance, Geramifard and his colleagues plan to use RLPy to run an experiment involving an autonomous vehicle learning to navigate its environment. In the project’s initial stages, however, he’s using simulations to begin building a battery of reasonably good policies. “While it’s learning, you don’t want to run it into a wall and wreck your equipment,” he says.

By web.mit.edu

An expandable table. A collapsible CNC router. Motorized wheels whose diameter can enlarge and contract depending on the terrain. These are a few of the examples of “transformable design” now on display from the course, “Mechanical Invention Through Computation” led by visiting designer, engineer and inventor Chuck Hoberman. The seminar, co-taught with MIT professors Erik Demaine and Daniela Rus from the Computer Science and Artificial Intelligence Laboratory (CSAIL), was driven by a simple question: How can you create new transformable objects?

This is the question that has shaped Hoberman’s unique 20-year career at the nexus of art and science, design and engineering. In 1990, he patented the Hoberman sphere: a mechanism resembling a geodesic dome that was created from a series of scissor-like joints (similar to those found on a cherry picker) allowing the object to expand and contract. Since then, Hoberman has invented a variety of shape-shifting products ranging in scale from toys, shelters, stage sets, medical devices, sculptures, buildings and furniture. There seems to be no end to the potential applications for these kinds of dynamic products, which use kinematics — the geometry of motion — to produce surprising and unique movements.

With Demaine and Rus, the course investigated how this kind of mechanical invention could be further optimized using mathematical analysis and computational processes. According to the exhibit text, “The inventive process itself is ripe for innovation.” Like Hoberman, both Demaine and Rus have also built their careers researching reconfigurable forms, making breakthroughs in the areas of programmable matter and computational origami respectively. Together, they have developed a sheet that can assemble into three-dimensional shapes of its own accord — such as a boat or a paper airplane — similar to the way that proteins found in nature can fold and refold into complex shapes to achieve different behaviors.

The resulting student projects ranged in scale and function, from pin joints that could only be seen with a microscope to large retractable tables. There was a DIY expandable lamp created completely from off-the-shelf materials; a foldable trapezoidal kite modeled after one designed by Alexander Graham Bell; a winged Phoenix-like sculpture based on a J.G. Ballard science fiction story; and a skirt that used “inflatable origami” to change size and shape. Every project was the result of continual prototyping with different types of designs and materials, employing methods both digital and physical.

This kind of mechanical intelligence is the wave of the future, as programming meets material to create supple and versatile new forms. In a world defined by flux, we increasingly require products and structures to be flexible, dynamic, and responsive to their changing environments. By transforming the process of invention — a creative act at the intersection of the technical, the scientific and the expressive — the course helped prepare the next generation of inventors for this challenge. “We’re really just beginning to scratch the surface,” Hoberman said at the exhibit’s opening.

The exhibit will be on view through June 20 in the Ray and Maria Stata Center, third floor, Room 32-338. The exhibit was co-presented by the Computer Science and Artificial Intelligence Laboratory (CSAIL) and the Center for Art, Science & Technology (CAST).

By web.mit.edu

The MIT Council on Educational Technology (MITCET) and the Office of Educational Innovation and Technology (OEIT) announced the winner and runners-up for the 2013 iCampus Student Prize competition at the Office of Digital Learning retreat held on May 17. The annual competition is offered each year to all current MIT undergraduates and graduate students (both individuals and groups) to encourage development of technology to improve aspects of MIT’s education and student life.

The grand prize was awarded to Aakanksha Sarda, a rising senior in the Department of Electrical Engineering and Computer Science (EECS), for her work on “WhichClass,” an online-exploration tool to aid students in planning their selection of classes. WhichClass will enable students to filter classes and visualize connections between classes within and across departments. In addition to its primary audience of students, the iCampus judges saw the potential of WhichClass to better understand the relationships between courses across departments. These insights are especially important as MIT continues to explore all aspects of digital learning. Sarda will continue developing WhichClass working with the OEIT in the fall. 

EECS junior Abubakar Abid received the runner-up award for the project he and his EECS teammates — sophomores Abdulrahman Alfozan and Aziz Alghunaim — developed, called “Lounge”: An electronic platform that speeds up and automates the on-campus housing process. Lounge also gives the dorms the flexibility to preserve individual dorm traditions. Abid, who accepted the award at the May 17 retreat, announced that Lounge has been used to successfully run Maseeh Hall’s Fall 2013 room assignment process. OEIT expects the Lounge team to continue to refine its software and work with more dorms for future implementation. 

The other runner-up project, titled “EduCase” was created by EECS graduate student Sara Itani and EECS senior Adin Schmahmann. Itani and Schmahmann described EduCase as the easiest, quickest and cheapest way to record video lectures — no cameraman, no hours wasted editing. A professor walks into a class, folds open his EduCase, and presses a button for a hassle-free-lecture-recording experience. The judges were very interested in the potential of EduCase to help streamline the process of recording lecture videos as MIT expands further into digital and online learning. OEIT will work with the EduCase team as they continue to develop the project.

Building on the entrepreneurial spirit of service exhibited by MIT students to solve the world’s problems, the iCampus Student Competition encourages projects that are developed to the point where MIT can adopt them for integration into its educational and student life programs. Support for the iCampus Student Prize comes from a fund endowed by Microsoft Research. 

“All the projects were simply terrific,” said OEIT Strategic Advisor for the Office of Digital Learning (ODL) and OEIT Director Vijay Kumar. “The iCampus Student Prize activity is a wonderful example of the innovative and creative engagement of our students in developing creative and constructive opportunities for the application of digital technology at MIT. This is particularly significant at a time when the MIT community is so deeply engaged in understanding the impact of these technologies on the future of teaching and learning at MIT.”

By web.mit.edu

One of the most popular online destinations on the MIT network is not a website for scientists, engineers or college students, but an online community where kids learn to code.

Every day, thousands of young people, ages 8 and up, gather on MIT’s Scratch website, where they program their own interactive stories, games, animations and simulations — and share their creations with one another. They account for nearly 10 percent of all visits to MIT webpages. Translated into 50 languages, Scratch has become one of the world’s most popular ways for young people to learn to code.

This week, the MIT Media Lab launched a new version of Scratch, called Scratch 2.0, which moves the programming community into the cloud, so members can examine, experiment with and remix one another’s programs directly in the web browser, without any uploading or downloading.

As with earlier versions of Scratch, young people create computer programs by snapping together colorful graphical blocks. In Scratch 2.0, there are new blocks for creating new types of projects, such as online surveys and games that respond to real-world movements (by using webcams as sensors). Community members can also create their own custom blocks from existing blocks — and share their new blocks with others.

In developing Scratch 2.0, the Media Lab’s Scratch Team sought input from the Scratch community, which posted more than 3,000 suggestions and design ideas. For example, a debate between advocates of different graphics formats led the team to develop an integrated paint editor that combines bitmap and vector graphics.

Many people view coding as a narrow technical activity — a valuable job skill useful for only a small subset of the population — but Scratch aims to make coding accessible and appealing for everyone, says Mitchel Resnick, the LEGO Papert Professor of Learning Research at the MIT Media Lab and director of the Scratch Team. “Just as everyone should learn to write, everyone should learn to code,” he says. “The ability to code is an important part of fluency in the 21st century.”

In the Scratch community, young people see coding as a new means of expression, Resnick says: They combine art, music and programming scripts to create a wide diversity of projects, such as animated stories, virtual tours, science simulations, public service announcements, multimedia art projects, interactive tutorials and community newsletters. Since the launch of Scratch in 2007, its community members have shared more than 3 million projects on the website, with thousands of new projects added every day.

As young people create and share projects, they learn not only specific technical skills, but also broader strategies for solving problems, designing projects, communicating ideas and working collaboratively — valuable skills for everyone to have, Resnick says. “Scratchers aren’t just learning to code, they’re coding to learn,” he says.

Scratch is used in many contexts (homes, schools, libraries, community centers), at many age levels (from elementary school to college), and across many disciplines (math, computer science, language arts, social studies). Although designed primarily for ages 8 to 16, Scratch has been used in introductory computer science courses at some universities.

More than 1.5 million people have registered on the Scratch website, and many of them show a deep commitment to the community, Resnick says. As part of the transition to Scratch 2.0, the Scratch Team asked young members to submit projects on the theme of “Why Do You Scratch?” One of many responses came from a girl who had joined the community six months earlier.

“Scratch allows people to be creative on so many different levels. On Scratch, you can be anything, an artist, a programmer, a musician, a writer and so much more,” she wrote. “The very best thing about Scratch to me is the amazing, amazing community of people to work with. I love doing all sorts of [collaborations] with people, and I love seeing what others do as inspiration. The whole website and the ability to post projects and look at others easily is what really makes Scratch different from all other programming languages out there.”

By web.mit.edu

It is difficult to provide a detailed and comprehensive picture of wireless network data performance in the real world. Although providers like AT&T and Verizon offer coverage maps on their web sites, there is no reliable source of end-to-end network performance across different providers and across a range of locations during different times of day.

CSAIL graduate students Victor Costan, Yu-han (Tiffany) Chen, Ravi Netravali, and Jonathan Perry are looking to build a network map by gathering information on wireless network performance through smartphone games, as part of new research underway in Professor Hari Balakrishnan’s Networks and Mobile Systems Group at CSAIL and Wireless@MIT. The games would drive players to certain locations where there is sparse information on network statistics in order to gather data.

From May 17 – May 19, the group will host a location-based, Android “Game-Jam,” a two-day event dedicated to bringing game developers together to build a host of mobile games that will aid in this research. The hosts are looking for game developers with experience in Android or web programming, graphic designers, and audio professionals to participate. The Game-Jam will start at 7:00 p.m. on May 17 at the Patil/Kiva conference room (32-G449) in the Stata Center, and will wrap up May 19 at 9:00 p.m. with prizes and awards. All members of the MIT community and beyond are invited to participate.

• Register by 12 p.m. on Friday, May 17 at: http://gamejam.mit.edu/.

Once the event is completed, the games will be used to gather network performance statistics and build a comprehensive map of how the network behaves across different regions. The information will be useful in not only providing data on how the network operates for mobile phone and Internet providers, but also to provide a reliable source of information for researchers looking to improve wireless and mobile device connectivity.

“People will hopefully be able to get better performance because of this data,” Perry says. “Researchers can use the information for research on improving network reliability and performance, as it will provide data on data transport latency and throughput for cellular and WiFi networks.”

Users of the mobile games will be aware that the games are gathering information on network connectivity to be used in scientific research, but they will not have to expend any effort, beyond playing the game, in order to help gather information on network connectivity.

Participants are encouraged to express their creativity when developing games during the Game-Jam. Examples of different types of games that might be useful in gathering network statistics include games for individual players that set goals for players to achieve and social games that allow groups of players to collaborate or compete to achieve a common goal.
By web.mit.edu

Shyamnath Gollakota, an MIT graduate who completed his doctoral research in Professor Dina Katabi’s Networks@MIT research group at CSAIL, has won the 2012 Doctoral Dissertation Award presented by the Association for Computing Machinery (ACM). Gollakota was honored for his work designing practical systems that transform wireless systems by embracing the phenomenon of interference and rendering it harmless.

Instead of trying to hide the interference that severely limits wireless systems, Gollakota used an alternate approach that successfully reconstructed the traditional packets of transmitted information. He then manipulated the interfering signals using innovative receiver designs that decode the WiFi collisions and improve security.

Gollakota, an assistant professor at the University of Washington, completed the dissertation at MIT, which nominated him for the award. He will receive the Doctoral Dissertation Award and its $20,000 prize at the annual ACM Awards Banquet on June 15 in San Francisco, Calif. Financial sponsorship of the award is provided by Google Inc.

In his dissertation, “Embracing Interference in Wireless Systems,” Gollakota presented ZigZag, the first WiFi receiver that successfully reconstructs the transmitted information in the presence of packet collisions. He also introduced TIMO, a WiFi receiver that decodes information in the presence of high-power cross-technology interference from other devices such as baby monitors, cordless phones and microwave ovens.

Gollakota’s practical approach also showed how to harness interference to improve security using wireless medical implants, which are susceptible to attacks over wireless channels. He developed the first system that provides confidentiality for implants’ transmissions. The system protects them against commands from unauthorized parties without requiring any modification to the implants themselves.

To make security easy for ordinary users, he introduced the first system that enables WiFi users to establish secure connections without any passwords or pre-shared secret keys. His idea was to construct a new secure message type that can neither be altered nor hidden without detection.

A graduate of MIT with Ph.D. and SM degrees in Electrical Engineering and Computer Science, Gollakota also earned a BA degree in Computer Science and Engineering at Indian Institute of Technology-Madras. He received two ACM SIGCOMM (Special Interest Group on Data Communication) Best Paper awards — in 2008 for ZigZag decoding, and in 2011 for securing medical implants. He also received the AT&T Applied Security Award for password-free wireless security.
By web.mit.edu

Keeping track of individuals in an endangered population of animals is a cumbersome and time-consuming task.

Conservationists physically tag animals in the wild to better follow them over time. But tagging can be intrusive for many species, and difficult to accomplish in larger populations. As an alternative, scientists have photographed animals in their natural environments and catalogued the images, along with information such as individuals’ dimensions and geographic locations.

However, as images accumulate, picking out individuals from among thousands of pictures can be a monumental task. Sai Ravela, a principal research scientist in MIT’s Department of Earth, Atmospheric and Planetary Sciences, estimates that manually sifting through a catalog of 10,000 images can take one person 15 years.

“It’s an enormous amount of time,” Ravela says. “You’re reaching the edges of what people want to do with their lives.”

Now Ravela and his colleagues at MIT have developed computer software that automates much of the image-matching process. The system, which they’ve named SLOOP, sifts through thousands of images, using pattern-recognition algorithms to analyze features in each image, such as an animal’s arrangement of stripes or spots. The system then identifies an average of 20 most likely matches for an individual.

From there, the researchers turned to crowdsourcing, asking online users to pick the most similar pair. Based on such feedback, the system reorders the list, paring it down to fewer images likely to depict the same individual.

“It’s sort of like Google, in that you type in a search term and you get back potential matches, but ultimately you’re the judge of what’s the best match,” Ravela says. “It makes biologists’ lives a lot easier than having to go through an entire catalog.”

Ravela, along with undergraduates James Duyck and Chelsea Finn, are applying the system to various endangered and threatened species, including geckos, whale sharks and skinks. The group will present details of the system at the Mexican Conference on Pattern Recognition in June.

Beyond facial recognition

In recent years, pattern-recognition algorithms have mostly been developed for facial recognition, matching individuals by features such as eyes, noses and mouths. But Ravela says these algorithms are not sophisticated enough to parse out the enormous complexity in animal patterning.

“To distinguish an individual, like a salamander Bob from a salamander Jill, is tough,” Ravela says. “On the whole, the variability we see within species really tests our assumptions of what makes a good pattern-recognition algorithm.”

His group has developed multiple algorithms to identify matching patterns, including several that adjust for changes in an animal’s lighting, orientation and geometry, and other algorithms that overlay images, comparing the positioning of spots or stripes. The researchers use combinations of algorithms to match images, depending on a species’s particular features. 

A user can upload an image to the system, along with any accompanying information such as an individual’s weight, size and location. Depending on the type of animal being catalogued, the user performs a few simple additional steps, such as marking reference points like a lizard’s eyes, nose and shoulder. The system then takes over, using algorithms to adjust the image and ranking its similarity to the rest of the catalog’s images.

Animal tracking

The image-matching system is currently used by New Zealand’s Department of Conservation to track threatened populations of skinks — small lizards that, thanks to a recovery program, have multiplied in recent years. The species’s rebound, while a good sign, poses a more difficult tracking problem for conservationists as the population grows — a problem that SLOOP is helping to solve.

“We had reached the point where two-thirds of our monitoring effort was spent in front of the computer screen, and only one-third in the field directly monitoring the lizards,” says Andy Hutcheon, program manager for the Grand and Otago Skink Recovery Plan in New Zealand. “That’s a lot of eyestrain.”

Using the system, Hutcheon and his colleagues have quickly sorted out individuals from among more than 26,000 existing images. So far, they have found 15 cases in which human error incorrectly identified an individual as two distinct lizards. 

Ultimately, SLOOP may help scientists answer broader questions about animal behavior, such as on species’ breeding habits and migration patterns. For example, Hutcheon says the image-matching system has picked out at least six individuals among the entire population that have migrated between study sites, in some cases traveling up to several miles.

“Many New Zealand natives are characterized by lack of detailed data,” Hutcheon says. “New application of technology that can help us to understand their numbers and life history can only help with their conservation.”

Crowd conservation

Going a step further, Ravela’s team looked at the potential for crowdsourcing to further speed up the image-matching process.

As an experiment, the researchers posted thousands of images of salamanders, in groups of four, on Amazon’s Mechanical Turk, an online crowdsourcing marketplace. The researchers asked users to rank the images in order of similarity.

To “rate” a user’s ability, the system was programmed to know the answer to three of every four images. If a user correctly ranked these known images, the system accepted the user’s fourth answer. As incentive to participate, the researchers offered users a modest monetary reward for correct answers.

“We found about a third of the people who came were really good pattern-matchers,” Ravela says. “One guy had a 99.96 percent performance, and stayed for 3,000 comparisons.”

By combining computer-vision algorithms with crowdsourcing, the team is able to quickly identify image matches among thousands of photos with 97 percent accuracy. 

The researchers are now working to further automate the system. For example, Ravela’s students are developing algorithms that will automatically separate and outline an animal from an image background. The problem is a difficult one, as the system would have to distinguish between, for instance, a lizard’s leg and a nearby twig.  To solve these problems, Finn is developing matching algorithms using feature geometry, while Duyck is combining multiple pattern-matching algorithms to improve image-ranking.

“These are incredibly hard problems,” Ravela says. “On the other hand, doing these things manually is extraordinarily time-consuming. Is there a sweet spot between the two that allows us to solve real problems? That’s what SLOOP is trying to do.”

This work is supported by the National Science Foundation.
By web.mit.edu

Since at least the late 19th century, when John Dewey opened his experimental Laboratory School at the University of Chicago, experiential learning — learning by doing — has had strong proponents among educational theorists. In MIT’s Department of Electrical Engineering and Computer Science (EECS), the influence of experiential-learning theory can be seen in several courses in which each student spends the entire semester working on a single programming project.

Even such project-based classes, however, miss aspects of the experience of commercial software development. “If you go to work at Microsoft, for example, you’re going to be handed code with 30 years of history, and you have to be able to quickly get up to speed, navigate hundreds of thousands of lines of code and then build on top of it, often without access to the people who originally wrote it,” says Ted Benson, a PhD student in EECS, who before coming to MIT worked for three years as a commercial software developer. “And then you need to make your contributions in a way where, 30 years later, other people can do the same.”

This spring, Benson and his thesis advisor, professor of computer science and engineering David Karger, created a new course in which rather than developing small projects from scratch, students participate in large, ongoing, open-source-software development initiatives, mentored by industry professionals. And as is the case with much modern commercial software development, they collaborate online with geographically dispersed colleagues — in this case, their fellow students at some 15 universities around the world.

The consortium of universities, and their joint open-source development projects, were the brainchild of Jay Borenstein, a lecturer in computer science at Stanford University. Borenstein got funding from Facebook, convened a working group of educators — including Karger — to design courses and other educational initiatives around development projects, worked with members of the open-source-software community to identify outstanding problems, and recruited the industry mentors.

Baptism of fire

Not only does working on real development projects impart practical skills that are difficult to acquire in a conventional classroom setting, Benson says, but it also engages the students in a way that readings and problem sets rarely do.

“There’s this age-old question for any teacher, which is how do you motivate the students to really buy into what they’re learning,” Benson says. “They’re fixing bugs and adding features to software that will touch millions of users. And when that’s your homework, it’s completely different. I’ve had students give me high-fives when they come in to report that they’ve finished something.”

One group of students, for instance, is helping repair a deep-rooted problem with the popular web-development framework Ruby on Rails. Frequently, tasks executed by commercial sites need to be processed as “transactions,” meaning that either all the aspects of the task are executed or none are: You wouldn’t want, say, a travel site charging you for one leg of a trip when it couldn’t find a return flight. Ruby on Rails had a bug, however, that meant that sometimes, failed transactions left program code out of sync with the database. MIT students are helping fix it. Another group is helping to develop a monitoring tool for the open-source database application MongoDB, so that application users can tell what types of queries the database is receiving and which servers are processing them.

Software studio

The design of the course — the Open Source Software Project Lab, or 6.S194 in MIT’s course-numbering scheme — borrows elements from both the studio critiques typical of architecture courses and the residency model used in medical schools, Benson says. At the beginning of the semester, students were presented with the nine projects identified by Borenstein. On the basis of their personal preferences, they were sorted into five teams, with each assigned to a different project with a different mentor.

On Mondays, Benson lectures, often tailoring his subject matter to questions raised by the students’ recent work. Every Wednesday, teams present their ongoing work to the rest of the class, explaining their approaches, inviting criticism and prompting general discussion of programming principles and philosophies.

Otherwise, the students work chiefly with each other, with their collaborators at the other schools, and with their mentors. Every week, each team meets with Benson for 20 minutes to describe the next stage of its project and report its progress on the previous stage. “They learn that a very valid thing to accomplish in a week is thoroughly understanding a particular technology and coming up with a plan for how you might use it,” Benson says. “Sometimes learning is their assignment.”

When students have completed work on a particular section of code, they log it into the open-source project’s online code repository, where Benson can, if he chooses, review it to see if it accords with the weekly progress report. Sometimes, indeed, he has found that it doesn’t — but in an unexpected way. “I have had to go to some students and say, ‘Give yourself credit for this!’” Benson says. “You did far more work than I would have expected you to this week.”

Scaling up

That kind of individual attention, Benson acknowledges, is possible mainly because the MIT class, in its inaugural session, is intentionally small — only 11 students. One of the questions that he and Karger spend a lot of time discussing is how to preserve its advantages while increasing its size. One possibility is to assign the students to more homogeneous projects — to have them all, for instance, work on different aspects of a single open-source application, such as Mozilla’s Firefox.

Another possibility is to introduce tiers of instruction, where some of the regular evaluation and feedback is provided by upperclassmen who have already taken the course. A peer mentorship program, Benson says, could be modeled on MIT’s celebrated Undergraduate Research Opportunity Program, in which undergraduates perform original research for either course credit or stipends. Or Benson and Karger might use some other recruitment mechanism altogether. “Some of the students seem to enjoy this so much that I wouldn’t be surprised if they would volunteer to do it,” Benson says.

Aaron Patterson, a senior software architect at AT&T and one of the student mentors, says that he would definitely participate in the course again, but that he could use some more help. “It’s a lot of work,” he says. “Next time, I would try to involve more people as mentors or reduce the number of students I have.”

Patterson doesn’t believe that programs like the Open Source Software Project Lab will supplant the conventional computer science curriculum, but he does think that they complement it. “The textbook background is important for long-term development, but I don’t think textbooks prepare you for how to apply those techniques to real-world software,” he says. “Techniques I learned in school were extremely helpful, but didn’t prepare me for dealing with — frankly — bad code from the real world.”

And with the Open Source Software Project Lab, he says, the students have more to show for their work than a stack of graded problem sets. “Overall, the students are making extremely valuable contributions,” he says. “The work being accomplished via the students I’m working with is greater than I could accomplish on my own.”
By web.mit.edu