TCP, the transmission control protocol, is one of the core protocols governing the Internet: If counted as a computer program, it’s the most widely used program in the world.

One of TCP’s main functions is to prevent network congestion by regulating the rate at which computers send data. In the last 25 years, engineers have made steady improvements to TCP’s congestion-control algorithms, resulting in several competing versions of the protocol: Many Windows computers, for instance, run a version called Compound TCP, while Linux machines run a version called TCP Cubic.

At the annual conference of the Association for Computing Machinery’s Special Interest Group on Data Communication this summer, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory and Center for Wireless Networks and Mobile Computing will present a computer system, dubbed Remy, that automatically generates TCP congestion-control algorithms. In the researchers’ simulations, algorithms produced by Remy significantly outperformed algorithms devised by human engineers.

“I think people can think about what happens to one or two connections in a network and design around that,” says Hari Balakrishnan, the Fujitsu Professor in Electrical Engineering and Computer Science, who co-authored the new paper with graduate student Keith Winstein. “When you have even a handful of connections, or more, and a slightly more complicated network, where the workload is not a constant — a single file being sent, or 10 files being sent — that’s very hard for human beings to reason about. And computers seem to be a lot better about navigating that search space.”

Lay of the land

Remy is a machine-learning system, meaning that it arrives at its output by trying lots of different possibilities, and exploring further variations on those that seem to work best. Users specify certain characteristics of the network, such as whether the bandwidth across links fluctuates or the number of users changes, and by how much. They also provide a “traffic profile” that might describe, say, the percentage of users who are browsing static Web pages or using high-bandwidth applications like videoconferencing.

Finally, the user also specifies the metrics to be used to evaluate network performance. Standard metrics include throughput, which indicates the total amount of data that can be moved through the network in a fixed amount of time, and delay, which indicates the average amount of time it takes one packet of information to travel from sender to receiver. The user can also assign metrics different weights — say, reducing delay is important, but only one-third as important as increasing throughput.

Remy needs to test each candidate algorithm’s performance under a wide range of network conditions, which could have been a prohibitively time-consuming task. But Winstein and Balakrishnan developed a clever algorithm that can concentrate Remy’s analyses on cases in which small variations in network conditions produce large variations in performance, while spending much less time on cases where network behavior is more predictable.

They also designed Remy to evaluate possible indicators of network congestion that human engineers have not considered. Typically, TCP congestion-control algorithms look at two main factors: whether individual data packets arrive at their intended destination and, if they do, how long it takes for acknowledgments to arrive. But as it turns out, the ratio between the rates at which packets are sent and received is a rich signal that can dictate a wide range of different behaviors on the sending computer’s end.

Down to cases

Indeed, where a typical TCP congestion-control algorithm might consist of a handful of rules — if the percentage of dropped packets crosses some threshold, cut the transmission rate in half — the algorithms that Remy produces can have more than 150 distinct rules.

“It doesn’t resemble anything in the 30-year history of TCP,” Winstein says. “Traditionally, TCP has relatively simple endpoint rules but complex behavior when you actually use it. With Remy, the opposite is true. We think that’s better, because computers are good at dealing with complexity. It’s the behavior you want to be simple.” Why the algorithms Remy produces work as well as they do is one of the topics the researchers hope to explore going forward.

In the meantime, however, there’s little arguing with the results. Balakrishnan and Winstein tested Remy’s algorithms on a simulation system called the ns-2, which is standard in the field.

In tests that simulated a high-speed, wired network with consistent transmission rates across physical links, Remy’s algorithms roughly doubled network throughput when compared to Compound TCP and TCP Cubic, while reducing delay by two-thirds. In another set of tests, which simulated Verizon’s cellular data network, the gains were smaller but still significant: a 20 to 30 percent improvement in throughput, and a 25 to 40 percent reduction in delay.

“I am thrilled by the approach,” says Victor Bahl, research manager of the Mobility and Networking Group at Microsoft Research. “When you can constrain the problem domain and define precisely what you want out of the protocol, I can believe that their system is better than a human.”

Bahl cautions that “when the protocol has to do many things for many people or many devices, then it’s not clear whether this is the optimal method.” But he adds that it could very well be that, in the future, networked computers will adopt different congestion-control policies depending on the types of applications they’re running. “I could see that that’s where this thing would excel,” he says.
By Larry Hardesty, MIT News Office

Reinventing invention

October 26, 2014

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 Anya Ventura | Center for Art, Science & Technology

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 EECS/Office of Educational Innovation Technology

In a pair of recent papers, researchers at MIT’s Computer Science and Artificial Intelligence Laboratory have demonstrated that, for a few specific tasks, it’s possible to write computer programs using ordinary language rather than special-purpose programming languages.

The work may be of some help to programmers, and it could let nonprogrammers manipulate common types of files — like word-processing documents and spreadsheets — in ways that previously required familiarity with programming languages. But the researchers’ methods could also prove applicable to other programming tasks, expanding the range of contexts in which programmers can specify functions using ordinary language.

“I don’t think that we will be able to do this for everything in programming, but there are areas where there are a lot of examples of how humans have done translation,” says Regina Barzilay, an associate professor of computer science and electrical engineering and a co-author on both papers. “If the information is available, you may be able to learn how to translate this language to code.”

In other cases, Barzilay says, programmers may already be in the practice of writing specifications that describe computational tasks in precise and formal language. “Even though they’re written in natural language, and they do exhibit some variability, they’re not exactly Shakespeare,” Barzilay says. “So again, you can translate them.”

The researchers’ recent papers demonstrate both approaches. In work presented in June at the annual Conference of the North American Chapter of the Association for Computational Linguistics, Barzilay and graduate student Nate Kushman used examples harvested from the Web to train a computer system to convert natural-language descriptions into so-called “regular expressions”: combinations of symbols that enable file searches that are far more flexible than the standard search functions available in desktop software.

In a paper being presented at the Association for Computational Linguistics’ annual conference in August, Barzilay and another of her graduate students, Tao Lei, team up with professor of electrical engineering and computer science Martin Rinard and his graduate student Fan Long to describe a system that automatically learned how to handle data stored in different file formats, based on specifications prepared for a popular programming competition.

Regular irregularities

As Kushman explains, computer science researchers have had some success with systems that translate questions written in natural language into special-purpose formal languages — languages used to specify database searches, for instance. “Usually, the way those techniques work is that they’re finding some fairly direct mapping between the natural language and this formal representation,” Kushman says. “In general, the logical forms are handwritten so that they have this nice mapping.”

Unfortunately, Kushman says, that approach doesn’t work with regular expressions, strings of symbols that can describe the data contained in a file with great specificity. A regular expression could indicate, say, just those numerical entries in a spreadsheet that are three columns over from a cell containing a word of any length whose final three letters are “BOS.”

But regular expressions, as ordinarily written, don’t map well onto natural language. For example, Kushman explains, the regular expression used to search for a three-letter word starting with “a” would contain a symbol indicating the start of a word, another indicating the letter “a,” a set of symbols indicating the identification of a letter, and a set of symbols indicating that the previous operation should be repeated twice. “If I’m trying to do the same syntactic mapping that I would normally do,” Kushman says, “I can’t pull out any sub-chunk of this that means ‘three-letter.’”

What Kushman and Barzilay determined, however, is that any regular expression has an equivalent that does map nicely to natural language — although it may not be very succinct or, for a programmer, very intuitive. Moreover, using a mathematical construct known as a graph, it’s possible to represent all equivalent versions of a regular expression at once. Kushman and Barzilay’s system thus has to learn only one straightforward way of mapping natural language to symbols; then it can use the graph to find a more succinct version of the same expression.

When Kushman presented the paper he co-authored with Barzilay, he asked the roomful of computer scientists to write down the regular expression corresponding to a fairly simple text search. When he revealed the answer and asked how many had gotten it right, only a few hands went up. So the system could be of use to accomplished programmers, but it could also allow casual users of, say, spreadsheet and word-processing programs to specify elaborate searches using natural language.

Opening gambit

The system that Barzilay, Rinard, Lei and Long developed is one that can automatically write what are called input-parsing programs, essential components of all software applications. Every application has an associated file type — .doc for Word programs, .pdf for document viewers, .mp3 for music players, and so on. And every file type organizes data differently. An image file, for instance, might begin with a few bits indicating the file type, a few more indicating the width and height of the image, and a few more indicating the number of bits assigned to each pixel, before proceeding to the bits that actually represent pixel colors.

Input parsers figure out which parts of a file contain which types of data: Without an input parser, a file is just a random string of zeroes and ones.

The MIT researchers’ system can write an input parser based on specifications written in natural language. They tested it on more than 100 examples culled from the Association for Computing Machinery’s International Collegiate Programming Contest, which includes file specifications for every programming challenge it poses. The system was able to produce working input parsers for about 80 percent of the specifications. And in the remaining cases, changing just a word or two of the specification usually yielded a working parser.

“This could be used as an interactive tool for the developer,” Long says. “The developer could look at those cases and see what kind of changes they need to make to the natural language — maybe some word is hard for the system to figure out.”

The system begins with minimal information about how written specifications might correspond to parser programs. It knows a handful of words that should consistently refer to particular data types — the word “integer,” for instance — and it knows that the specification will probably describe some data structures that are nested in others: An image file, for instance, could consist of multiple chunks, and each chunk would be headed by a few bytes indicating how big it is.

Otherwise, the system just tries lots of different interpretations of the specification on a few sample files; in the researchers’ experiments, the samples, too, were provided on the competition website. If the resulting parser doesn’t seem to work on some of the samples, the system varies its interpretation of the specification slightly. Moreover, as it builds more and more working parsers, it becomes more adept at recognizing regularities in the way that parsers are specified. It took only about 10 minutes of calculation on an ordinary laptop for the system to produce its candidate parsers for all 100-odd specifications.

“This is a big first step toward allowing everyday users to program their computers without requiring any knowledge of programming language,” says Luke Zettlemoyer, an assistant professor of computer science and engineering at the University of Washington. “The techniques they have developed should definitely generalize to other related programming tasks.”
By Larry Hardesty, MIT News Office

A market for emotions

October 26, 2014

Emotions can be powerful for individuals. But they’re also powerful tools for content creators, such as advertisers, marketers, and filmmakers. By tracking people’s negative or positive feelings toward ads — via traditional surveys and focus groups — agencies can tweak and tailor their content to better satisfy consumers.

Increasingly, over the past several years, companies developing emotion-recognition technology — which gauges subconscious emotions by analyzing facial cues — have aided agencies on that front.

Prominent among these companies is MIT spinout Affectiva, whose advanced emotion-tracking software, called Affdex, is based on years of MIT Media Lab research. Today, the startup is attracting some big-name clients, including Kellogg and Unilever.

Backed by more than $20 million in funding, the startup — which has amassed a vast facial-expression database — is also setting its sights on a “mood-aware” Internet that reads a user’s emotions to shape content. This could lead, for example, to more relevant online ads, as well as enhanced gaming and online-learning experiences.

“The broad goal is to become the emotion layer of the Internet,” says Affectiva co-founder Rana el Kaliouby, a former MIT postdoc who invented the technology. “We believe there’s an opportunity to sit between any human-to-computer, or human-to-human interaction point, capture data, and use it to enrich the user experience.”

Ads and apps

In using Affdex, Affectiva recruits participants to watch advertisements in front of their computer webcams, tablets, and smartphones. Machine learning algorithms track facial cues, focusing prominently on the eyes, eyebrows, and mouth. A smile, for instance, would mean the corners of the lips curl upward and outward, teeth flash, and the skin around their eyes wrinkles.

Affdex then infers the viewer’s emotions — such as enjoyment, surprise, anger, disgust, or confusion — and pushes the data to a cloud server, where Affdex aggregates the results from all the facial videos (sometimes hundreds), which it publishes on a dashboard.

But determining whether a person “likes” or “dislikes” an advertisement takes advanced analytics. Importantly, the software looks for “hooking” the viewers in the first third of an advertisement, by noting increased attention and focus, signaled in part by less fidgeting and fixated gazes.

Smiles can indicate that a commercial designed to be humorous is, indeed, funny. But if a smirk — subtle, asymmetric lip curls, separate from smiles — comes at a moment when information appears on the screen, it may indicate skepticism or doubt. 

A furrowed brow may signal confusion or cognitive overload. “Sometimes that’s by design: You want people to be confused, before you resolve the problem. But if the furrowed brow persists throughout the ad, and is not resolved by end, that’s a red flag,” el Kaliouby says.

Affectiva has been working with advertisers to optimize their marketing content for a couple of years. In a recent case study with Mars, for example, Affectiva found that the client’s chocolate ads elicited the highest emotional engagement, while its food ads elicited the least, helping predict short-term sales of these products.

In that study, some 1,500 participants from the United States and Europe viewed more than 200 ads to track their emotional responses, which were tied to the sales volume for different product lines. These results were combined with a survey to increase the accuracy of predicting sales volume.

“Clients usually take these responses and edit the ad, maybe make it shorter, maybe change around the brand reveal,” el Kaliouby says. “With Affdex, you see on a moment-by-moment basis, who’s really engaged with ad, and what’s working and what’s not.”

This year, the startup released a developer kit for mobile app designers. Still in their early stages, some of the apps are designed for entertainment, such as people submitting “selfies” to analyze their moods and sharing them across social media.

Still others could help children with autism better interact, el Kaliouby says — such as games that make people match facial cues with emotions. “This would focus on pragmatic training, helping these kids understand the meaning of different facial expressions and how to express their own,” she says.

Entrenched in academia

While several companies are commercializing similar technology, Affectiva is unusual in that it is “entrenched in academia,” el Kaliouby says: Years of data-gathering have “trained” the algorithms to be very discerning.  

As a PhD student at Cambridge University in the early 2000s, el Kaliouby began developing facial-coding software. She was inspired, in part, by her future collaborator and Affectiva co-founder, Rosalind Picard, an MIT professor who pioneered the field of affective computing — where machines can recognize, interpret, process, and simulate human affects.

Back then, the data that el Kaliouby had access to consisted of about 100 facial expressions gathered from photos — and those 100 expressions were fairly prototypical. “To recognize surprise, for example, we had this humongous surprise expression. This meant that if you showed the computer an expression of a person that’s somewhat surprised or subtly shocked, it wouldn’t recognize it,” el Kaliouby says.

In 2006, el Kaliouby came to the Media Lab to work with Picard to expand what the technology can do. Together, they quickly started applying the facial-coding technology to autism research and training the algorithms by collecting vast stores of data.

“Coming from a traditional research background, the Media Lab was completely different,” el Kaliouby says. “You prototype, prototype, prototype, and fail fast. It’s very startup-minded.”

Among their first prototypes was a Google Glass-type invention with a camera that could read facial expressions and provide real-time feedback to the wearer via a Bluetooth headset. For instance, auditory cues would provide feedback, such as, “This person is bored” or, “This person is confused.”

However, inspired by increasing industry attention —- and with a big push by Frank Moss, then the Media Lab’s director — they soon ditched the wearable prototype to build a cloud-based version of the software, founding Affectiva in 2009.

Early support from a group of about eight mentors at MIT’s Venture Mentoring Service helped the Affectiva team connect to industry and shape its pitch — by focusing on the value proposition, not the technology. “We learned to build a product story instead of a technology story — that was key,” el Kaliouby says.

To date, Affectiva has amassed a dataset of about 1.7 million facial expressions, roughly 2 billion data points, ­from people of all races, across 70 different countries — the largest facial-coding dataset in the world, el Kaliouby says — training its software’s algorithms to discern expressions from all different face types and skin colors. It can also track faces that are moving, in all types of lighting, and can avoid tracking any other movement on screen.

A “mood-aware” Internet

One of Affectiva’s long-term goals is to usher in a “mood-aware” Internet to improve users’ experiences. Imagine an Internet that’s like walking into a large outlet store with sales representatives, el Kaliouby says.

“At the store, the salespeople are reading your physical cues in real time, and assessing whether to approach you or not, and how to approach you,” she says. “Websites and connected devices of the future should be like this, very mood-aware.”

Sometime in the future, this could mean computer games that adapt in difficulty and other game variables, based on user reaction. But more immediately, it could work for online learning.

Already, Affectiva has conducted pilot work for online learning, where it captured data on facial engagement to predict learning outcomes. For this, the software indicates, for instance, if a student is bored, frustrated, or focused — which is especially valuable for prerecorded lectures, el Kaliouby says.

“To be able to capture that data, in real time, means educators can adapt that learning experience and change the content to better engage students — making it, say, more or less difficult — and change feedback to maximize learning outcomes,” el Kaliouby says. “That’s one application we’re really excited about.”

By Rob Matheson | MIT News Office

For many companies, moving their web-application servers to the cloud is an attractive option, since cloud-computing services can offer economies of scale, extensive technical support and easy accommodation of demand fluctuations.

But for applications that depend heavily on database queries, cloud hosting can pose as many problems as it solves. Cloud services often partition their servers into “virtual machines,” each of which gets so many operations per second on a server’s central processing unit, so much space in memory, and the like. That makes cloud servers easier to manage, but for database-intensive applications, it can result in the allocation of about 20 times as much hardware as should be necessary. And the cost of that overprovisioning gets passed on to customers.

MIT researchers are developing a new system called DBSeer that should help solve this problem and others, such as the pricing of cloud services and the diagnosis of application slowdowns. At the recent Biennial Conference on Innovative Data Systems Research, the researchers laid out their vision for DBSeer. And in June, at the annual meeting of the Association for Computing Machinery’s Special Interest Group on Management of Data (SIGMOD), they will unveil the algorithms at the heart of DBSeer, which use machine-learning techniques to build accurate models of performance and resource demands of database-driven applications.

DBSeer’s advantages aren’t restricted to cloud computing, either. Teradata, a major database company, has already assigned several of its engineers the task of importing the MIT researchers’ new algorithm — which has been released under an open-source license — into its own software.

Virtual limitations

Barzan Mozafari, a postdoc in the lab of professor of electrical engineering and computer science Samuel Madden and lead author on both new papers, explains that, with virtual machines, server resources must be allocated according to an application’s peak demand. “You’re not going to hit your peak load all the time,” Mozafari says. “So that means that these resources are going to be underutilized most of the time.”

Moreover, Mozafari says, the provisioning for peak demand is largely guesswork. “It’s very counterintuitive,” Mozafari says, “but you might take on certain types of extra load that might help your overall performance.” Increased demand means that a database server will store more of its frequently used data in its high-speed memory, which can help it process requests more quickly.

On the other hand, a slight increase in demand could cause the system to slow down precipitously — if, for instance, too many requests require modification of the same pieces of data, which need to be updated on multiple servers. “It’s extremely nonlinear,” Mozafari says.

Mozafari, Madden, postdoc Alekh Jindal, and Carlo Curino, a former member of Madden’s group who’s now at Microsoft, use two different techniques in the SIGMOD paper to predict how a database-driven application will respond to increased load. Mozafari describes the first as a “black box” approach: DBSeer simply monitors fluctuations in both the number and type of user requests and system performance and uses machine-learning techniques to correlate the two. This approach is good at predicting the consequences of fluctuations that don’t fall too far outside the range of the training data.

Gray areas

Often, however, database managers — or prospective cloud-computing customers — will be interested in the consequences of a fourfold, tenfold, or even hundredfold increase in demand. For those types of predictions, Mozafari explains, DBSeer uses a “gray box” model, which takes into account the idiosyncrasies of particular database systems.

For instance, Mozafari explains, updating data stored on a hard drive is time-consuming, so most database servers will try to postpone that operation as long as they can, instead storing data modifications in the much faster — but volatile — main memory. At some point, however, the server has to commit its pending modifications to disk, and the criteria for making that decision can vary from one database system to another.

The version of DBSeer presented at SIGMOD includes a gray-box model of MySQL, one of the most widely used database systems. The researchers are currently building a new model for another popular system, PostgreSQL. Although adapting the model isn’t a negligible undertaking, models tailored to just a handful of systems would cover the large majority of database-driven Web applications.

The researchers tested their prediction algorithm against both a set of benchmark data, called TPC-C, that’s commonly used in database research and against real-world data on modifications to the Wikipedia database. On average, the model was about 80 percent accurate in predicting CPU use and 99 percent accurate in predicting the bandwidth consumed by disk operations.

“We’re really fascinated and thrilled that someone is doing this work,” says Doug Brown, a database software architect at Teradata. “We’ve already taken the code and are prototyping right now.” Initially, Brown says, Teradata will use the MIT researchers’ prediction algorithm to determine customers’ resource requirements. “The really big question for our customers is, ‘How are we going to scale?’” Brown says.

Brown hopes, however, that the algorithm will ultimately help allocate server resources on the fly, as database requests come in. If servers can assess the demands imposed by individual requests and budget accordingly, they can ensure that transaction times stay within the bounds set by customers’ service agreements. For instance, “if you have two big, big resource consumers, you can calculate ahead of time that we’re only going to run two of these in parallel,” Brown says. “There’s all kinds of games you can play in workload management.”
By Larry Hardesty, MIT News Office

Kids coding in the cloud

October 26, 2014

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 MIT Media Lab

Optical computing — using light rather than electricity to perform calculations — could pay dividends for both conventional computers and quantum computers, largely hypothetical devices that could perform some types of computations exponentially faster than classical computers.

But optical computing requires light particles — photons — to modify each other’s behavior, something they’re naturally averse to doing: Two photons that collide in a vacuum simply pass through each other.

In the latest issue of the journal Science, researchers at MIT’s Research Laboratory of Electronics — together with colleagues at Harvard University and the Vienna University of Technology — describe the experimental realization of an optical switch that’s controlled by a single photon, allowing light to govern the transmission of light. As such, it’s the optical analog of a transistor, the fundamental component of a computing circuit.

Moreover, since the weird, counterintuitive effects of quantum physics are easier to see in individual particles than in clusters of particles, the ability to use a single photon to flip the switch could make it useful for quantum computing.

The heart of the switch is a pair of highly reflective mirrors. When the switch is on, an optical signal — a beam of light — can pass through both mirrors. When the switch is off, only about 20 percent of the light in the signal can get through.

The paired mirrors constitute what’s known as an optical resonator. “If you had just one mirror, all the light would come back,” explains Vladan Vuletić, the Lester Wolfe Professor of Physics at MIT, who led the new work. “When you have two mirrors, something very strange happens.”

Light can be thought of as particles — photons — but it can also be thought of as a wave — an electromagnetic field. Even though, on the particle description, photons are stopped by the first mirror, on the wave description, the electromagnetic field laps into the space between the mirrors. If the distance between the mirrors is precisely calibrated to the wavelength of the light, Vuletić explains, “Basically, a very large field builds up inside the cavity that cancels the field coming back and goes in the forward direction.” In other words, the mirrors become transparent to light of the right wavelength.

Clouding over

In the RLE researchers’ experiment, the cavity between the mirrors is filled with a gas of supercooled cesium atoms. Ordinarily, these atoms don’t interfere with the light passing through the mirrors. But if a single “gate photon” is fired into their midst at a different angle, kicking just one electron of one atom into a higher energy state, it changes the physics of the cavity enough that light can no longer pass through it.

Joining Vuletić on the paper are lead author Wenlan Chen and Kristin M. Beck, both PhD students in his group; Robert Bücker of the Vienna University of Technology; and Michael Gullans, Mikhail D. Lukin and Haruka Tanji-Suzuki of Harvard.

For conventional computers, the chief advantage of optical computing would be in power management: As computer chips have more and more transistors crammed onto them, they draw more power and run hotter. Computing with light instead of electricity would address both problems.

Of course, clouds of supercooled atoms are not a practical design for the transistors in, say, a Web server. “For the classical implementation, this is more of a proof-of-principle experiment showing how it could be done,” Vuletić says. “One could imagine implementing a similar device in solid state — for example, using impurity atoms inside an optical fiber or piece of solid.”

Going quantum

Quantum-computing applications may be more compelling. Bizarrely, tiny particles of matter can be in mutually exclusive states simultaneously, something known as superposition. Where a bit in a classical computer can be either on or off, representing 0 or 1, bits built from particles in superposition can represent 0 and 1 at the same time. As a consequence, they could, in principle, evaluate many possible solutions to a computational problem in parallel, rather than considering them one by one.

Primitive quantum computers have been built using laser-trapped ions and nuclear magnetic resonance, but it’s hard to keep their bits — or “qubits,” for quantum bits — in superposition. Superposition is much easier to preserve in photons, for exactly the same reason that it’s hard to get photons to interact.

The ability to switch an optical gate with a single photon opens the possibility of arrays of optical circuits, all of which are in superposition. “If the gate photon is there, the light gets reflected; if the gate photon is not there, the light gets transmitted,” Vuletić explains. “So if you were to put in a superposition state of the photon being there and not being there, then you would end up with a macroscopic superposition state of the light being transmitted and reflected.”

A photon-switched transistor has other implications for quantum computing. For instance, Vuletić says, one of the first applications of a conventional transistor was to filter noise out of an electrical signal by feeding the transistor’s output back into it. “Quantum feedback can cancel — to the extent allowed by quantum mechanics — quantum noise,” Vuletić says. “You can make quantum states that you wouldn’t otherwise get.”

The switch could also be used as a photon detector: If a photon has struck the atoms, light won’t pass through the cavity. “That means you have a device that can detect a photon without destroying it,” Vuletić says. “That doesn’t exist today. It would have many applications in quantum information processing.”

“Energy consumption in computing devices is a big issue,” says Jelena Vuckovic, a professor of electrical engineering at Stanford University. “The beauty of this approach is that it can really do switching at the single-photon level, so your losses are much smaller. You don’t have to spend a lot of energy for each bit. Your bit is essentially included in a single photon.”

Vuckovic believes that it should be possible to reproduce the MIT researchers’ results in physical systems that are easier to integrate into computer chips. “It’s exactly the same story, except that instead of using these ultracold atoms in the cavity, you use a microscopic cavity on a semiconductor chip on a semiconductor and you use a quantum dot grown inside of the semiconductor as an artificial atom,” she says. “There would be extra steps that people would have to take in order to implement the right energy-level structure. But in principle, the physics could be translated to a platform that could be cascaded and more easily integrated.”

By Larry Hardesty, MIT News Office

The rise of online education and massively open online courses (MOOCs) have prompted much naysaying on their effectiveness, with detractors citing single-digit completion rates and short-lived pilot programs.

Amidst all the arguments about “flipped classrooms” and “hybrid learning,” however, few people have actually analyzed what makes MOOCs work (or fail): the content. Online learners spend most of their time watching videos — but are the videos any good?

This year edX, the online learning platform co-run by MIT and Harvard University, gave researchers at MIT’s Computer Science and Artificial Intelligence Lab (CSAIL) data on the second-by-second viewing habits of more than 100,000 learners perusing more than 6.9 million video sessions.

In a paper published this spring, the CSAIL team outlined some key findings on what online learners want from videos. These include:

  • Brevity (viewers generally tune out after six minutes)
  • Informality, with professors seated at a desk, not standing behind a podium
  • Lively visuals rather than static PowerPoint slides
  • Fast talkers (professors seen as the most engaging spoke at 254 words per minute)
  • More pauses, so viewers can soak in complex diagrams
  • Web-friendly lessons (existing videos broken into shorter chunks are less effective than ones crafted for online audiences)

These insights form the basis of the CSAIL team’s LectureScape, a “YouTube for MOOCs” that seeks to reinvent how online learners watch videos.

LectureScape uses data on viewing behavior — particularly the “interaction peaks” that correspond to points of interest or confusion — to present MOOC videos in a way that’s more intuitive, dynamic, and effective:

  • A timeline shows which parts other users have most frequently watched
  • An interactive transcript lets users enter keywords to find relevant segments
  • A mechanism automatically creates word clouds and summaries of individual sections, as well as the whole presentation
  • Content from popular slides automatically appears in the following slide, as users will likely want to refer back to that information

In summary, viewers can consume videos more efficiently, skipping specific sections or repeating trickier ones, without having to slog through the whole video.

Juho Kim, a graduate student in electrical engineering and computer science, says that the group’s previous work on the tutorial-focused platform ToolScape (PDF) demonstrated that users learn more effectively with this type of interface. He says that traditional MOOC metrics, such as completion rates, are “too simplistic,” and don’t account for the many learners seeking specific skills (versus intending to formally finish a course).

LectureScape was developed by Kim alongside former postdoc Philip Guo; EECS graduate students Carrie Cai and Shang-Wen Li; EECS professor Rob Miller; and Harvard’s Krzysztof Gajos. Kim will present the research at the ACM Symposium on User Interface Software and Technology (UIST) in Honolulu in October.

Kim says the next steps for LectureScape include personalized lecture-video recommendations, in the style of Netflix, as well as “on-demand expansion,” which includes links to relevant videos to clarify potentially confusing topics.

He also hopes to implement the tool on a larger scale to quantify its effect on student engagement and performance. The technology can be easily applied to existing MOOC content, as the tool uses machine learning to automatically segment videos based on visual cues.

By Adam Conner-Simons | CSAIL

Securing the cloud

October 26, 2014

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 Larry Hardesty, MIT News Office