Better machine learning

March 3, 2015

When Kalyan Veeramachaneni joined the Any Scale Learning For All (ALFA) group at MIT’s CSAIL as a postdoc in 2010, he worked on large-scale machine-learning platforms that enable the construction of models from huge data sets. “The question then was how to decompose a learning algorithm and data into pieces, so each piece could be locally loaded into different machines and several models could be learnt independently,” says Veeramachaneni, currently a research scientist at ALFA.

“We then had to decompose the learning algorithm so we could parallelize the compute on each node,” says Veeramachaneni. “In this way, the data on each node could be learned by the system, and then we could combine all the solutions and models that had been independently learned.”

By 2013, once ALFA had built multiple platforms to accomplish these goals, the team started on a new problem: the growing bottleneck caused by the process of translating the raw data into the formats required by most machine-learning systems.

“Machine-learning systems usually require a covariates table in a column-wise format, as well as a response variable that we try to predict,” says Veeramachaneni. “The process to get these from raw data involves curation, syncing and linking of data, and even generating ideas for variables that we can then operationalize and form.”

Much of Veeramachaneni’s recent research has focused on how to automate this lengthy data prep process. “Data scientists go to all these boot camps in Silicon Valley to learn open source big data software like Hadoop, and they come back, and say ‘Great, but we’re still stuck with the problem of getting the raw data to a place where we can use all these tools,’” Veeramachaneni says.

Veeramachaneni and his team are also exploring how to efficiently integrate the expertise of domain experts, “so it won’t take up too much of their time,” he says. “Our biggest challenge is how to use human input efficiently, and how to make the interactions seamless and efficient. What sort of collaborative frameworks and mechanisms can we build to increase the pool of people who participate?”

GigaBeats and BeatDB

One project in which Veeramachaneni tested his automated data prep concepts was ALFA’s GigaBeats project. GigaBeats analyzes arterial blood pressure signals from thousands of patients to predict a future condition. With GigaBeats, numerous steps are involved to prepare the data for analysis, says Veeramachaneni. These include cleaning and conditioning, low pass filters, and extracting features by applying signal-level transformations.

Many of these steps involve human decision-making. Often, domain experts know how to do it, but sometimes it’s up to the computer scientist. In either case, there’s no easy way to go back and revisit those human interventions when a choice made later in the pipeline does not result in the expected level of predictive accuracy, says Veeramachaneni.

Recently, ALFA has built some novel platforms that automate the process, shrinking the prep time from months to a few days. To automate and accelerate data translation, while also enabling visibility into earlier decision-making, ALFA has developed a “complete solution” called BeatDB.

“With BeatDB, we have tunable parameters that in some cases can be input by domain experts, and the rest are automatically tuned,” says Veeramachaneni. “From this, we can learn how decisions made at the low-level, raw representation stage can impact the final predicted accuracy efficacy. This deep-mining solution combines all layers of machine learning into a single pipeline and then optimizes and tunes with other machine-learning algorithms on top of it. It really enables fast discovery.”

Now that ALFA has made progress on integrating and recording human input, the group is also looking for better ways to present the processed data. For example, when showing GigaBeats data to medical professionals, “they are often much more comfortable if a better representation is given to them instead of showing them raw data,” says Veeramachaneni. “It makes it easier to provide input. A lot of our focus is on improving the presentation so we can more easily pull their input into our algorithms, clean or fix the data, or create variables.”

A crowdsourcing solution

While automating ALFA’s machine-learning pipelines, Veeramachaneni has also contributed to a number of real-world analytics projects. Recently, he has been analyzing raw click data from massive open online courses (MOOCs) with the hopes of improving courseware. The initial project is to determine stop-out (drop-out) rates based on online click behavior.

“The online learning platforms record data coming from the interaction of hundreds of thousands of learners,” says Veeramachaneni. “We are now able to identify variables that can predict stop-out on a single course. The next stage is to reveal the variables of stop-out and show how to improve the course design.”

The first challenge in the MOOC project was to organize the data. There are multiple data streams in addition to clickstream data, and they are usually spread over multiple databases and stored in multiple formats. Veeramachaneni has standardized these sources, integrating them into a single database called MOOCdb. “In this way, software written on top of the database can be re-used,” says Veeramachaneni.

The next challenge is to decide what variables to look at. ALFA has explored all sorts of theories about MOOC behavior. For example, if a student is studying early in the morning, he or she is more likely to stay in the course. Another theory is based on dividing the time spent on the course by how many problems a student gets right. But, Veeramachaneni says, “If I’m trying to predict stop-out, there’s no algorithm that automatically comes up with the behavioral variables that influence it. The biggest challenge is that the variables are defined by humans, which creates a big bottleneck.”

They turned to crowdsourcing “to tap into as many people as we can,” says Veeramachaneni. “We have built a crowdsourcing platform where people can submit an idea against problems such as stop-out,” says Veeramachaneni. “Another set of people can operationalize that, such as writing a script to extract that variable on a per student basis.”

This research could apply to a number of domains where analysts are trying to predict human behavior based on captured data, such as fraud detection, says Veeramachaneni. Banks and other companies are increasingly analyzing their transaction databases to try to determine whether the person doing the transaction is authentic.

“One variable would be how far the transaction happened from the person’s home, or how the amount compares to the total that was spent by the person over the last year,” says Veeramachaneni. “Coming up with these ideas is based on very relatable data with which we can all identify. So crowdsourcing could be helpful here, too.”

By Eric Brown | MIT Industrial Liaison Program

Here’s one way to get kids excited about programming: a “robot garden” with dozens of fast-changing LED lights and more than 100 origami robots that can crawl, swim, and blossom like flowers.

A team from MIT’s Computer Science and Artificial Intelligence Lab (CSAIL) and the Department of Mechanical Engineering have developed a tablet-operated system that illustrates their cutting-edge research on distributed algorithms via robotic sheep, origami flowers that can open and change colors, and robotic ducks that fold into shape by being heated in an oven.

In a paper recently accepted to the 2015 International Conference on Robotics and Automation, researchers describe the system’s dual functions as a visual embodiment of their latest work in distributed computing, as well as an aesthetically appealing way to get more young students, and particularly girls, interested in programming.

The system can be managed via tablet or any Bluetooth-enabled device, either through a simple “control by click” feature that involves clicking on individual flowers, as well as a more advanced “control by code” feature where users can add their own commands and execute sequences in real-time.

“Students can see their commands running in a physical environment, which tangibly links their coding efforts to the real world,” says Lindsay Sanneman, who is lead author on the new paper. “It’s meant to be a launchpad for schools to demonstrate basic concepts about algorithms and programming.”

Each of the system’s 16 tiles are connected via Arduino microcontrollers and programmed via search algorithms that explore the space in different ways, including a “graph-coloring” algorithm that ensures that no two adjacent tiles ever share the same color.

“The garden tests distributed algorithms for over 100 distinct robots, which gives us a very large-scale platform for experimentation,” says CSAIL Director Daniela Rus, the Andrew and Erna Viterbi Professor of Electrical Engineering and Computer Science and a co-author of the paper. “At the same time, we hope that it also helps introduce students to topics like graph theory and networking in a way that’s both beautiful and engaging.”

Rus previously helped develop a distributed system of robots that watered, harvested, and took various metrics of an actual vegetable garden using complex motion-planning and object-recognition algorithms.

Among the other researchers on the new project were PhD candidate Joseph DelPreto, postdocs Ankur Mehta and Shuhei Miyashita, and members of MIT Professor Sangbae Kim’s Biomimetics Robotics Lab, including undergraduates Deborah Ajilo and Negin Abdolrahim Poorheravi, among others.

Kim’s team developed eight distinct varieties of origami flowers — including lilies, tulips, and birds of paradise — which are embedded with printable motors that he says “allow them to blossom in very interesting ways.” The sheep robots were created via traditional print-and-fold origami techniques, while the magnet-powered ducks started as two-dimensional paper prints that were heated in an oven, causing them to automatically fold into shape.

“Many elements of the garden can be made very quickly, including the pouch motors and the LED flowers,” DelPreto says. “We’re hoping that rapid fabrication techniques will continue to improve to the point that something like this could be easily built in a standard classroom.”
Sanneman and DelPreto showed off the current garden to local schools at CSAIL’s “Hour of Code” event in December, and say that they plan to incorporate it into a programming curriculum involving printable robots that they have developed for middle and high schools.

In the future, they also hope to make the garden operable by multiple devices simultaneously, and may even experiment with interactive auditory components by adding microphones and music that would sync to movements.

“Computer science has so many real-world applications that a lot of kids don’t see because they aren’t exposed to them from an earlier age,” Sanneman says. “That’s why we think there’s a lot of potential for tools like this.”

By Adam Conner-Simons | CSAIL

Smarter multicore chips

March 3, 2015

Computer chips’ clocks have stopped getting faster. To keep delivering performance improvements, chipmakers are instead giving chips more processing units, or cores, which can execute computations in parallel.

But the ways in which a chip carves up computations can make a big difference to performance. In a 2013 paper, Daniel Sanchez, the TIBCO Founders Assistant Professor in MIT’s Department of Electrical Engineering and Computer Science, and his student, Nathan Beckmann, described a system that cleverly distributes data around multicore chips’ memory banks, improving execution times by 18 percent on average while actually increasing energy efficiency.

This month, at the Institute of Electrical and Electronics Engineers’ International Symposium on High-Performance Computer Architecture, members of Sanchez’s group have been nominated for a best-paper award for an extension of the system that controls the distribution of not only data but computations as well. In simulations involving a 64-core chip, the system increased computational speeds by 46 percent while reducing power consumption by 36 percent.

“Now that the way to improve performance is to add more cores and move to larger-scale parallel systems, we’ve really seen that the key bottleneck is communication and memory accesses,” Sanchez says. “A large part of what we did in the previous project was to place data close to computation. But what we’ve seen is that how you place that computation has a significant effect on how well you can place data nearby.”


The problem of jointly allocating computations and data is very similar to one of the canonical problems in chip design, known as “place and route.” The place-and-route problem begins with the specification of a set of logic circuits, and the goal is to arrange them on the chip so as to minimize the distances between circuit elements that work in concert.

This problem is what’s known as NP-hard, meaning that as far as anyone knows, for even moderately sized chips, all the computers in the world couldn’t find the optimal solution in the lifetime of the universe. But chipmakers have developed a number of algorithms that, while not absolutely optimal, seem to work well in practice.

Adapted to the problem of allocating computations and data in a 64-core chip, these algorithms will arrive at a solution in the space of several hours. Sanchez, Beckmann, and Po-An Tsai, another student in Sanchez’s group, developed their own algorithm, which finds a solution that is more than 99 percent as efficient as that produced by standard place-and-route algorithms. But it does so in milliseconds.

“What we do is we first place the data roughly,” Sanchez says. “You spread the data around in such a way that you don’t have a lot of [memory] banks overcommitted or all the data in a region of the chip. Then you figure out how to place the [computational] threads so that they’re close to the data, and then you refine the placement of the data given the placement of the threads. By doing that three-step solution, you disentangle the problem.”

In principle, Beckmann adds, that process could be repeated, with computations again reallocated to accommodate data placement and vice versa. “But we achieved 1 percent, so we stopped,” he says. “That’s what it came down to, really.”

Keeping tabs

The MIT researchers’ system monitors the chip’s behavior and reallocates data and threads every 25 milliseconds. That sounds fast, but it’s enough time for a computer chip to perform 50 million operations.

During that span, the monitor randomly samples the requests that different cores are sending to memory, and it stores the requested memory locations, in an abbreviated form, in its own memory circuit.

Every core on a chip has its own cache — a local, high-speed memory bank where it stores frequently used data. On the basis of its samples, the monitor estimates how much cache space each core will require, and it tracks which cores are accessing which data.

The monitor does take up about 1 percent of the chip’s area, which could otherwise be allocated to additional computational circuits. But Sanchez believes that chipmakers would consider that a small price to pay for significant performance improvements.

“There was a big National Academy study and a DARPA-sponsored [information science and technology] study on the importance of communication dominating computation,” says David Wood, a professor of computer science at the University of Wisconsin at Madison. “What you can see in some of these studies is that there is an order of magnitude more energy consumed moving operands around to the computation than in the actual computation itself. In some cases, it’s two orders of magnitude. What that means is that you need to not do that.”

The MIT researchers “have a proposal that appears to work on practical problems and can get some pretty spectacular results,” Wood says. “It’s an important problem, and the results look very promising.”

By Larry Hardesty | MIT News Office

Consumer-friendly makers

March 3, 2015

Entrepreneurship can sometimes take people down unexpected paths.

Just ask the two co-founders of MIT Media Lab spinout Sifteo: Their success in rapidly commercializing their popular “smart” gaming blocks recently led to an acquisition by 3D Robotics (3DR) to help build the company’s newest consumer drones.

In 2011, alumni David Merrill SM ’04, PhD ’09 and Jeevan Kalanithi SM ’07 had turned a Media Lab project into a popular gaming platform, Sifteo Cubes: plastic blocks, about an inch and a half on each side, equipped with color touch displays. Sensors detect the blocks’ movements and nearby blocks, and wireless technology allows them to communicate with each other to enable games and educational experiences.

People can pile, group, sort, tilt, and knock the cubes together to play various games, developed by Sifteo and a community of developers. Some games are simple, such as bouncing a ball across multiple displays, or educational, such as unscrambling words by sliding the tiles into the right order. There are also adventure games, where users uncover sections of a maze for characters by moving cubes up and down, and putting them adjacent to each other.

Energized by Merrill’s 2009 TED Talk on the devices, which went viral, Sifteo’s first run of 1,000 cubes sold out in just 13 hours. For a few years, Sifteo’s first- and second-generation cubes found a niche customer base, while catching the eye of electronics and hardware companies enamored with the novel devices.  

Among those interested parties was hobbyist drone manufacturer 3DR, which acquired Sifteo last July, noting in a press release Sifteo’s expertise in bringing innovative consumer electronics to a wide customer base. (Sifteo Cubes have since been taken out of production.)

Now members of the Sifteo team — including Kalanithi and Merrill — will help 3DR build out the consumer drone market over the next few years. While he can’t provide details, Kalanithi says, “It’s really about a desire to build drones at scale that can get into the hands of everyone.”

Connecting at the Media Lab

The Sifteo story began one spring afternoon in 2006. Kalanithi and Merrill, who became friends as Stanford University undergraduates and had reconnected at MIT, were at a table in the Media Lab’s kitchen, brainstorming ways in which people could use their hands to physically interact with data.

At the time, the two were becoming deeply immersed in the Media Lab’s tangible-computation culture, taking classes like MAS 834 (Tangible Interfaces) and working with other students on sensor networks and “smart” devices. “Those ideas were constantly bouncing around in our heads,” Kalanithi says.

In that conversation, they landed on a novel idea: “smart blocks” for people to physically manipulate computer data. “You have all this information — emails, desktop files, photos — and one mouse pointer to interact with it, like having a single finger tip,” Merrill says. “If you had a pile of LEGOs on the table, you’d use both hands and your body – pushing the piles around. We wanted to build an interface for interacting with information on a computer that was more like a pile of LEGOs.”

Initially labeling the system “The Siftable Computer,” Kalanithi and Merrill built prototypes — tiles of wood and acrylic, with photos plastered on them — to experiment with in the lab, explaining their vision and gaining feedback.

At the time, for his MIT thesis, Kalanithi was developing electronic devices called “Connectibles,” which he described as “tangible social media.” These wirelessly connected tiles — equipped, for instance, with a dial that illuminated onboard LEDs — could be exchanged and plugged into outlets on a plywood board. If two people exchanged Connectibles, for instance, whenever they turned on the lights of their own tiles, the lights of the exchanged Connectibles would also illuminate.

For this project, Kalanithi was implanting working displays into the tiles. “We thought, ‘We can use these little displays for smart blocks,’” he says.

Nine months of prototyping — with help from other Media Lab students — led to Siftables, small computers that could display images and sense nearby blocks and movement. They could be stacked and shuffled to do math, and play music and basic games. “From the original core — physical embodiment of digital information — the details emerged through a series of prototypes and bouncing ideas off other smart people at the Media Lab,” Merrill says.

Bull by the horns

But things changed dramatically in 2009 when Merrill delivered a TED Talk on Siftables, as part of a larger focus on Media Lab projects. A video of the talk went viral, amassing 1 million views and garnering interest from the press, tech circles, and consumers.

“We thought we had to take the bull by the horns,” Kalanithi says. “We could either make them into cool research tools in low volumes, or we could fully commercialize them as far and wide as possible.”

Later that year, the two launched Sifteo in San Francisco, and started completely re-engineering the Siftables code and hardware with cheaper parts for mass production. They conducted intensive market research, including surveys and in-depth interviews with families with young kids — who they assumed would be the product’s primary customers.

In the early days of the startup, they also received sage advice from seasoned entrepreneurs in MIT’s Venture Mentoring Service (VMS) — on MIT’s campus and in San Francisco. A key lesson from VMS, Kalanithi says, was the necessity of developing a mission statement.

“Before we knew what we were doing, we had to find a vision, and core values,” he says. “I thought it was stupid at that time, but I was wrong. Because it’s not a couple of guys starting a company, it’s a group of people that need to cooperate in an intensely productive way. So you need an idea everyone can align on. If you can establish that, and let people rip, then good things will happen.”

Once makers, always makers

Sifteo would go on to sell thousands of Sifteo Cubes to a customer base of teachers, families, makers, and gamers, among others. A software kit created by Sifteo’s engineers allowed developers to create more than 50 games for two generations of the cubes.

Yet the toys never found a broader audience, Kalanithi says, due in part to the sharp rise of iPads and tablets — which allowed for touch-based gaming. To compete, Sifteo had tried developing a third generation of games that better used the physicality of the cubes. For instance, one game involved stacking cubes at one end of the table, and sliding another as a puck to bump the tower without toppling it.

But it wasn’t enough for the long run, especially given the electronic competition. “Turns out [iPads and tablets] were close enough to the experience we were providing,” Kalanithi says. “Even though we, and certain groups of people, saw the differences very clearly, most people didn’t instantly.”

As it turns out, however, a host of electronics and hardware companies had started courting Sifteo with acquisition deals — including 3DR. Open to taking its technology and expertise down new paths, Sifteo accepted 3DR’s offer.

Reflecting on the deal, Merrill, now vice president of enabling technology at 3DR, says transitioning MIT-trained engineers of consumer electronics to a drone company is, in fact, a logical move. “We both bring a strong culture of shipping products, being interested in building cool stuff, and being enthusiastic about the possibilities of technology,” he says. “It’s a near-perfect cultural fit.”

By Rob Matheson | MIT News Office

Better how-to videos

March 3, 2015

Educational researchers have long held that presenting students with clear outlines of the material covered in lectures improves their retention.

Recent studies indicate that the same is true of online how-to videos, and in a paper being presented at the Association for Computing Machinery’s Conference on Computer-Supported Cooperative Work and Social Computing in March, researchers at MIT and Harvard University describe a new system that recruits viewers to create high-level conceptual outlines.

Blind reviews by experts in the topics covered by the videos indicated that the outlines produced by the new system were as good as, or better than, those produced by other experts.

The outlines also serve as navigation tools, so viewers already familiar with some of a video’s content can skip ahead, while others can backtrack to review content they missed the first time around.

“That addresses one of the fundamental problems with videos,” says Juho Kim, an MIT graduate student in electrical engineering and computer science and one of the paper’s co-authors. “It’s really hard to find the exact spots that you want to watch. You end up scrubbing on the timeline carefully and looking at thumbnails. And with educational videos, especially, it’s really hard, because it’s not that visually dynamic. So we thought that having this semantic information about the video really helps.”

Kim is a member of the User Interface Design Group at MIT’s Computer Science and Artificial Intelligence Laboratory, which is led by Rob Miller, a professor of computer science and engineering and another of the paper’s co-authors. A major topic of research in Miller’s group is the clever design of computer interfaces to harness the power of crowdsourcing, or distributing simple but time-consuming tasks among large numbers of paid or unpaid online volunteers.

Joining Kim and Miller on the paper are first author Sarah Weir, an undergraduate who worked on the project through the MIT Undergraduate Research Opportunities Program, and Krzysztof Gajos, an associate professor of computer science at Harvard University.

High-concept video

Several studies in the past five years, particularly those by Richard Catrambone, a psychologist at Georgia Tech, have demonstrated that accompanying how-to videos with step-by-step instructions improves learners’ mastery of the concepts presented. But before beginning work on their crowdsourced video annotation systems, the MIT and Harvard researchers conducted their own user study.

They hand-annotated several video tutorials on the use of the graphics program Photoshop and presented the videos, either with or without the annotations, to study subjects. The subjects were then assigned a task that drew on their new skills, and the results were evaluated by Photoshop experts. The work of the subjects who’d watched the annotated videos scored higher with the experts, and the subjects themselves reported greater confidence in their abilities and satisfaction with the tutorials.

Last year, at the Association for Computing Machinery’s Conference on Human Factors in Computing Systems, the researchers presented a system for distributing the video-annotation task among paid workers recruited through Amazon’s Mechanical Turk crowdsourcing service. Their clever allocation and proofreading scheme got the cost of high-quality video annotation down to $1 a minute.

That system produced low-level step-by-step instructions. But work by Catrambone and others had indicated that learners profited more from outlines that featured something called “subgoal labeling.”

“Subgoal labeling is an educational theory that says that people think in terms of hierarchical solution structures,” Kim explains. “Say there are 20 different steps to make a cake, such as adding sugar, salt, baking soda, egg, butter, and things like that. This could be just a random series of steps, if you’re a novice. But what if the instruction instead said, ‘First, deal with all the dry ingredients,’ and then it talked about the specific steps. Then it moved onto the wet ingredients and talked about eggs and butter and milk. That way, your mental model of the solution is much better organized.”

Division of labor

The system reported in the new paper, dubbed “Crowdy,” produces subgoal labels — and does so essentially for free. Each of a video’s first viewers will find it randomly paused at some point, whereupon the viewer will be asked to characterize the previous minute of instruction. After enough candidate descriptions have been amassed, each subsequent viewer will, at one of the same points, be offered three alternative characterizations of the preceding minute. Once a consensus emerges, Crowdy identifies successive minutes of video with similar characterizations and merges their labels. Finally, another group of viewers is asked whether the resulting labels are accurate and, if not, to provide alternatives.

The researchers tested Crowdy with a group of 15 videos about three common Web programming languages, which were culled from YouTube. The videos were posted on the Crowdy website for a month, during which they attracted about 1,000 viewers. Roughly one-fifth of those viewers participated in the experiment, producing an average of eight subgoal labels per video.

In ongoing work, the researchers are expanding the range of topics covered by the videos on the Crowdy website. They’re also investigating whether occasionally pausing the videos and asking viewers to reflect on recently presented content actually improves retention. There’s some evidence in the educational literature that it should, and if it does, it could provide a strong incentive for viewers to contribute to the annotation process.

“We did a bunch of experiments showing that subgoal-labeled videos really dramatically improve learning and retention, and even transfer to new tasks for people studying computer science,” says Mark Guzdial, a professor of interactive computing at Georgia Tech who has worked with Catrambone. “Immediately afterward, we asked people to attempt another problem, and we found that the people who got the subgoal labels attempted more steps and got them right more often, and they also took less time. And then a week later, we had them come back. When we asked them to try a new problem that they’d never seen before, 50 percent of the subgoal people did it correctly, and less than 10 percent of the people who didn’t get subgoals did that correctly.”

“Rob and Juho came up with the idea of doing crowdsourcing to generate the labels on videos,” Guzdial adds, “which I think is supercool.”

By Larry Hardesty | MIT News Office

The World Health Organization (WHO) cites good hand hygiene as a major factor in stopping the spread of hospital-acquired infections (HAIs) caused by exposure to various bacteria.

In fact, in 2009 the WHO released its “Five Moments of Hand Hygiene” guidelines, which pinpoint five key moments when hospital staff should wash their hands: before touching a patient, before aseptic procedures, after possible exposure to bodily fluids, after touching a patient, and after touching a patient’s surroundings.

But it’s been difficult to track workers’ compliance with these guidelines. Administrators usually just spend a few days a month monitoring health care workers, noting hand-hygiene habits on a WHO checklist.

Now General Sensing — co-founded by MIT Media Lab alumni Jonathan Gips SM ’06 and Philip Liang SM ’06 — is using smart devices to monitor hand hygiene among hospital staff and ensure compliance with WHO guidelines. The aim, Liang says, is to help reduce the spread of HAIs, which affected one in 25 U.S. hospital patients in 2010, according to the Centers for Disease Control and Prevention.

Called MedSense Clear, the system revolves around a badge worn by hospital staff. The badge can tell when a worker comes near or leaves a patient’s side, and whether that worker has used an alcohol-based sanitizer or soap dispenser during those times. It also vibrates to remind workers to wash up. The badge then sends data to a base station that pushes the data to a Web page where individuals can monitor their hand-washing, and administrators can see data about overall hand-hygiene compliance among staff.

A 2014 study in the Journal of Infection and Public Health concluded that compliance with WHO hand-washing rules jumped 25 percent in one month when staff used MedSense in a 16-bed hospital unit at Salmaniya Medical Complex in Bahrain. Currently, the Royal Brompton and Harefield hospital in London is studying the correlation between the MedSense system and reduction in HAIs.

The startup is also now developing a system to monitor hospital workflow, with aims of pinpointing areas where time and resources may be wasted by unnecessary wait times for patients. “We’re trying to drive safety with hand hygiene, and drive efficiency by reducing waste,” Gips says. “Really, we’re trying to be a support system for the hospital.”

In the “patient zone”

MedSense consists of four smart devices, including the badge, that communicate with each other. Beacons installed near patients are tuned to cover small or large areas, creating a “patient zone.”

The badge knows if the wearer has washed his or her hands, because the system’s soap dispensers are designed to sense pressure when their nozzles are pressed down. If the wearer uses the dispenser, the holder sends that information to the smart badge.

When a badge-wearer enters a patient zone and has not performed hand hygiene, the badge vibrates to remind the wearer to wash up, and does so again when the wearer leaves the zone.

“We think it’s important that the system provides feedback when it’s actionable without getting in the way of delivering care,” Gips says.

The system’s final component is a base station, set up near nursing stations. When workers are within 50 feet of the station, the station routes the badge’s data over the network to an online dashboard, called MedSense HQ. These stations also have 16 charging slots for the badge’s flat batteries.

In MedSense HQ, individuals can track, for instance, what times they missed washing their hands, or what times of the day they’re better at hand hygiene. Administrators can see aggregated data indicating, for instance, which units are more or less compliant with hand-hygiene protocols.

What’s interesting, Liang says, is that when it’s used in tandem with visual observation, MedSense consistently shows that hand hygiene increases to about 90 percent as staff know they’re being watched by administrators, a phenomenon called the Hawthorne Effect.

“We’ll look at the data and can pinpoint when the wearer is being watched. You’ll see the data spike and then go back down when [the observer] leaves,” he says.

MedSense, on the other hand, removes that observer bias, he says, and can collect data around the clock.

“Clean” start

General Sensing may tackle a serious health care issue, but its core technology started as a novelty item: smart dog collars.

In the Media Laboratory class MAS 834 (Tangible Interfaces), Liang, Gips, and Noah Paessel SM ’05 created dog collars equipped with RFID technology and accelerometers. These tracked a dog’s movement, communicated with smart collars worn by other dogs, and pushed that data online. Owners could log on to a social media site to check their pets’ exercise levels, interactions, and compare stats with other pets.

“It was a bit tongue-in-cheek,” Gips admits. But the students soon found themselves presenting a prototype to hundreds at human-computer interaction conference in Portland, Oregon — where it garnered significant attention.

With help from Media Lab entrepreneurial advisors and MIT’s Venture Mentoring Service, the students launched SNIF Labs (an acronym for “Social Networking in Fur”) in 2008 and began selling the collars. But after that year’s financial collapse, “Luxury pet products weren’t exactly selling,” Gips says.

When a researcher requested the technology to monitor health care staff, however, the startup decided to get a clean start in the health care industry, “which they say is recession-proof,” Gips says.

And after learning about WHO’s hand-hygiene guidelines, the team developed MedSense as an automated way to help administrators monitor hand-washing among staff. In 2011, researchers at Queen Mary Hospital in Hong Kong published a paper in the journal BioMed Infectious Disease that found MedSense was 88 percent accurate in monitoring staff compliance with the WHO’s guidelines.

Only then did the startup decide to commercialize this system. “We’re from MIT: We like publishing,” Gips says. “We needed to know we had something accurate.”

Cutting waste

Since then, General Sensing has raised more than $15 million in capital, and MedSense has been trialed in 10 hospitals across the United States and Europe, and in Saudi Arabia, Bahrain, and Qatar.

But the data MedSense collects on time spent near and around patients has proven to have another use: monitoring workflow.

As part of MedSense Look, the startup is developing small RFID tags that patients and staff wear, and ceiling-mounted transponders to track the tags, in real-time, as the wearers move through the “patient journey” — the waiting room, pre-procedure, procedure, and recovery room. General Sensing creates digital floor maps of an area being studied; patients and staff show up on the floor map as color-coded dots.

This allows the startup to gather data on patient wait times, treatment patterns, and other things that may reveal wasted time and resources. “Changing even seemingly simple workflows can require buy-in from a lot people. It helps to have quantifiable proof of the problem,” Gips says.

Another possible application is real-time location of surplus staff — particularly important when there’s a sudden influx of patients in one area of a hospital, Gips says. “Today, you have to call different units to see who has extra people on staff,” he explains. “With our system, we’re hoping you can log in and see where there are extra people that can come help. That waste can turn into a critical safety measure.”

By Rob Matheson | MIT News Office

Every undergraduate computer-science major takes a course on data structures, which describes different ways of organizing data in a computer’s memory. Every data structure has its own advantages: Some are good for fast retrieval, some for efficient search, some for quick insertions and deletions, and so on.

Today, hardware manufacturers are making computer chips faster by giving them more cores, or processing units. But while some data structures are well adapted to multicore computing, others are not. In principle, doubling the number of cores should double the efficiency of a computation. With algorithms that use a common data structure called a priority queue, that’s been true for up to about eight cores — but adding any more cores actually causes performance to plummet.

At the Association for Computing Machinery’s Symposium on Principles and Practice of Parallel Programming in February, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory will describe a new way of implementing priority queues that lets them keep pace with the addition of new cores. In simulations, algorithms using their data structure continued to demonstrate performance improvement with the addition of new cores, up to a total of 80 cores.

A priority queue is a data structure that, as its name might suggest, sequences data items according to priorities assigned them when they’re stored. At any given time, only the item at the front of the queue — the highest-priority item — can be retrieved. Priority queues are central to the standard algorithms for finding the shortest path across a network and for simulating events, and they’ve been used for a host of other applications, from data compression to network scheduling.

With multicore systems, however, conflicts arise when multiple cores try to access the front of a priority queue at the same time. The problem is compounded by modern chips’ reliance on caches — high-speed memory banks where cores store local copies of frequently used data.

“As you’re reading the front of the queue, the whole front of the queue will be in your cache,” says Justin Kopinsky, an MIT graduate student in electrical engineering and computer science and one of the new paper’s co-authors. “All of these guys try to put the first element in their cache and then do a bunch of stuff with it, but then somebody writes to it, and it invalidates everybody else’s cache. And this is like an order-of-magnitude slowdown — maybe multiple orders of magnitude.”

Loosening up

To avoid this problem, Kopinsky; fellow graduate student Jerry Li; their advisor, professor of computer science and engineering Nir Shavit; and Microsoft Research’s Dan Alistarh, a former student of Shavit’s, relaxed the requirement that each core has to access the first item in the queue. If the items at the front of the queue can be processed in parallel — which must be the case for multicore computing to work, anyway — they can simply be assigned to cores at random.

But a core has to know where to find the data item it’s been assigned, which is harder than it sounds. Data structures generally trade ease of insertion and deletion for ease of addressability. You could, for instance, assign every position in a queue its own memory address: To find the fifth item, you would simply go to the fifth address.

But then, if you wanted to insert a new item between, say, items four and five, you’d have to copy the last item in the queue into the first empty address, then copy the second-to-last item into the address you just vacated, and so on, until you’d vacated address five. Priority queues are constantly being updated, so this approach is woefully impractical.

An alternative is to use what’s known as a linked list. Each element of a linked list consists of a data item and a “pointer” to the memory address of the next element. Inserting a new element between elements four and five is then just a matter of updating two pointers.

Road less traveled

The only way to find a particular item in a linked list, however, is to start with item one and follow the ensuing sequence of pointers. This is a problem if multiple cores are trying to modify data items simultaneously. Say that a core has been assigned element five. It goes to the head of the list and starts working its way down. But another core is already in the process of modifying element three, so the first core has to sit and wait until it’s done.

The MIT researchers break this type of logjam by repurposing yet another data structure, called a skip list. The skip list begins with a linked list and builds a hierarchy of linked lists on top of it. Only, say, half the elements in the root list are included in the list one layer up the hierarchy. Only half the elements in the second layer are included in the third, and so on.

The skip list was designed to make moving through a linked list more efficient. To find a given item in the root list, you follow the pointers through the top list until you identify the gap into which it falls, then move down one layer and repeat the process.

But the MIT researchers’ algorithm starts farther down the hierarchy; how far down depends on how many cores are trying to access the root list. Each core then moves some random number of steps and jumps down to the next layer of the hierarchy. It repeats the process until it reaches the root list. Collisions can still happen, particularly when a core is modifying a data item that appears at multiple levels of the hierarchy, but they become much rarer.

By Larry Hardesty | MIT News Office

Quantum computers are experimental devices that promise exponential speedups on some computational problems. Where a bit in a classical computer can represent either a 0 or a 1, a quantum bit, or qubit, can represent 0 and 1 simultaneously, letting quantum computers explore multiple problem solutions in parallel. But such “superpositions” of quantum states are, in practice, difficult to maintain.

In a paper appearing this week in Nature Communications, MIT researchers and colleagues at Brookhaven National Laboratory and the synthetic-diamond company Element Six describe a new design that in experiments extended the superposition time of a promising type of qubit a hundredfold.

In the long term, the work could lead toward practical quantum computers. But in the shorter term, it could enable the indefinite extension of quantum-secured communication links, a commercial application of quantum information technology that currently has a range of less than 100 miles.

The researchers’ qubit design employs nitrogen atoms embedded in synthetic diamond. When nitrogen atoms happen to be situated next to gaps in the diamond’s crystal lattice, they produce “nitrogen vacancies,” which enable researchers to optically control the magnetic orientation, or “spin,” of individual electrons and atomic nuclei. Spin can be up, down, or a superposition of the two.

To date, the most successful demonstrations of quantum computing have involved atoms trapped in magnetic fields. But “holding an atom in vacuum is difficult, so there’s been a big effort to try to trap them in solids,” says Dirk Englund, the Jamieson Career Development Assistant Professor in Electrical Engineering and Computer Science at MIT and corresponding author on the new paper. “In particular, you want a transparent solid, so you can send light in and out. Crystals are better than many other solids, like glass, in that their atoms are nice and regular and their electronic structure is well defined. And amongst all the crystals, diamond is a particularly good host for capturing an atom, because it turns out that the nuclei of diamond are mostly free of magnetic dipoles, which can cause noise on the electron spin.”

Light conversation

In bulk diamond, superpositions of the spins in nitrogen vacancies can last almost a second. But in order to communicate with each other, nitrogen-vacancy qubits need to be able to transfer information via particles of light, or photons. This requires positioning the vacancy inside an optical resonator, which temporarily traps photons.

Previously, devices consisting of nitrogen vacancies inside optical resonators exhibited a superposition time of only around a microsecond. The researchers’ new design gets that up to 200 microseconds.

For quantum computing applications, however, it’s not enough to keep individual qubits in superposition. Their quantum states also need to be “entangled,” so that if one qubit falls out of superposition — if it takes on a definite value of either 0 or 1 — it constrains the possible states of the other qubits.

In systems that use light to move information between nitrogen-vacancy qubits, entanglement occurs when light particles emitted by the qubits reach an optical component — such as a beam splitter — at the same time. With the earlier systems, it generally took several minutes to produce entanglement between qubits. With the new system, it should take milliseconds.

That’s still too long: A practical device would need to entangle photons before their corresponding qubits fell out of superposition, or “decohered.” “But the numbers actually look quite promising,” Englund says. “In the coming years, the entanglement rate could be orders of magnitude faster than the decoherence.”

The researchers’ device consists of a ladderlike diamond structure with a nitrogen vacancy at its center, which is suspended horizontally above a silicon substrate. Shining light perpendicularly onto the ladder kicks the electron in the nitrogen vacancy into a higher-energy state. When it drops back down to its ground state, it releases that excess energy as a photon, whose quantum states can be correlated with its own.

The gaps in the diamond structure — the spaces between rungs in the ladder — act as what’s called a photonic crystal, confining the photon so that it bounces back and forth across the vacancy thousands of times. When the photon finally emerges, it has a high likelihood of traveling along the axis of the ladder, so that it can be guided into an optical fiber.

The right direction

Practically, the only way to synchronize the photons emitted by different qubits is probabilistically: Repeat the experiment enough, and eventually the photons will arrive at the optical component at the same time. In previous systems, both the time and the direction of the photons’ emission were left to chance. In the new system, the timing is still erratic, but direction is much more reliable. That, together with the greater purity of the emitted light, should reduce the time required to produce entanglement.

The researchers’ manufacturing process begins with a 5-micrometer-thick wafer of synthetic diamond with nitrogen atoms embedded in it at regular intervals, which is , made by Element Six. The MIT researchers use an oxygen plasma to reduce the diamond’s thickness to only 200 nanometers.

The resulting fragments of diamond are too small to etch using standard lithographic processes. So the MIT researchers developed a new technique in which they affix silicon membranes etched into ladder patterns to the diamond, then again use an oxygen plasma to remove the material not shielded by the silicon. They transfer the resulting structures to a chip using a tungsten atomic probe with a slightly sticky drop of silicone at its tip.

“Etching via a hard mask rather than a focused-ion beam seems to have kept the diamond material free of defects, thus sustaining the spin coherence,” says Mete Atature, a reader in physics at the University of Cambridge who was not involved in the research. “This is an important step toward the utilization of nitrogen-vacancy centers as efficient sources of entanglement, quantum repeaters, or quantum memories within a distributed network. The higher collection efficiency will lead to both faster generation and faster verification of entanglement, so it is analogous to being able to increase the clock rate of a computing device.”

By Larry Hardesty | MIT News Office

Department of Electrical Engineering and Computer Science Department (EECS) head Anantha Chandrakasan announced the appointment of Professor Silvio Micali as associate department head of EECS, effective Jan. 15. Micali succeeds Professor Bill Freeman, who served in this role and as a member of the Department Leadership Group (DLG) since July 2011.

Micali, a graduate of University of California at Berkeley, is best known as a visionary for his fundamental and foundational work on public-key cryptography, pseudorandom number functions, digital signatures, oblivious transfer, secure multiparty computation, zero-knowledge proofs, and mechanism design.

For his work, Micali has been recognized with many honors, including the Gödel Prize in 1993 and the RSA Prize in Cryptography in 2004. He was elected to the American Academy of Arts and Sciences in 2003, and elected in 2007 to both the National Academy of Sciences and the National Academy of Engineering. Silvio Micali and Shafi Goldwasser received the 2012 Turing Award for their work in cryptography — developing new mechanisms for encrypting and securing information — methods that are widely applicable and applied today in communication protocols, Internet transactions, and cloud computing.

Micali has been awarded over 50 patents on practical implementations of his inventions for encryption, digital signatures, electronic cash, certified transactions, key-escrow, and more. He established two start-up companies: Peppercoin, for micropayments, launched in 2002 with Ron Rivest and was acquired by Chockstone in 2007; and CoreStreet, for real-time credentials, was acquired by ActiveIDentity in 2009.

Chandrakasan said in his announcement to the EECS faculty: “I know that Silvio will bring to his new position the clarity, creativity, and passion that characterize his research work and teaching, and the department will be the stronger for it.”

Chandrakasan also extended his appreciation to Freeman for his tremendous service as associate department head. Freeman played a key role in the faculty search and hiring process. Along with former associate department head Munther Dahleh, Freeman co-chaired the Strategic Hiring Areas planning, leading to the hiring of 12 faculty members. He also worked toward successfully establishing a student committee for the faculty search process.

Freeman was instrumental in creating Postdoc6, a dedicated community for the department’s postdoctoral associates. For this initiative, he organized and launched an annual workshop for postdocs (held in January), as well as periodic lunches, with speakers, for the group during the semester.


By Patricia Sampson | Department of Electrical Engineering and Computer Science

For MIT senior Shannon Kao, expert storytelling is essential, even — if not especially — when it comes to coding. The computer science major relies on narrative everywhere from her science fiction writing to her research on educational computer games at the MIT Media Lab — and it all stems from a childhood replete with books.

Kao grew up in Michigan and then China, where her mother, who was her school’s librarian, exposed her and her two younger brothers, from an early age, to everything from picture books to hefty novels. 

“Instead of hanging out, we would all just grab a book and sit in our living room and read,” Kao says with a laugh.

After two semesters of organic chemistry doused her interest in medical school, Kao stumbled on course 6.01 (Introduction to Electrical Engineering and Computer Science) and immediately saw computer science as a way to use her love of math to build something tangible and interactive. The summer after her freshman year, she took on a research position with the Affective Computing Group at the Media Lab, where she worked on a free app called StoryScape.

The program, geared toward families with developmentally challenged children, lets users drag and drop animated characters and illustrations, from a gallery Kao helped build, onto a page where users can write original stories, and can then share those stories with others. The animated characters can react to stimuli in users’ environments, such as loud noises, or the shaking of the phone or tablet on which the app is installed.

Working on StoryScape’s graphic gallery was Kao’s first experience in a computer science lab — her first research position at MIT was in a biology lab — but even though she had very little expertise in the field at that point, the new research setting immediately felt natural.

“It’s important that there’s a strong story underneath something, and the rest will follow,” she says.

Modeling for beginners

Kao has since expanded her research to MIT’s Scheller Teacher Education Program (STEP), which develops learning technology. For the past 2 1/2 years, she has worked with software developer Daniel Wendel, a research associate in MIT’s Department of Urban Studies and Planning, on a project called StarLogo. It teaches students with no computer science background how to build a program for modeling decentralized systems, like traffic jams.

StarLogo’s accessibility to inexperienced coders hinges on a system of blocks-based programming, which works like virtual LEGO bricks: To build a program, rather than writing out lines of code using individual symbols and numbers, users drag and drop ready-made blocks of text that code for 3-D graphics; only certain combinations of text blocks create a functioning program. The process of building a modeling program this way is a lot like building a story — it needs a coherent beginning, middle, and end, or else it won’t function. Kao’s role has been to develop the 3-D graphics that the blocks code for.

“[Blocks] make programming more intuitive for people who don’t necessarily have the background,” she says. 

Kao has helped run several workshops to make ongoing improvements to StarLogo. STEP invites in parents and children with no programming background to complete a series of challenges; the researchers then ask for feedback on usability. Some of the biggest issues the team has encountered are with interfaces that control zooming and scrolling. After each workshop, it’s back to the lab, where Kao and her colleagues whittle away at a list of tweaks in preparation for the next workshop and set of feedback. 

From mindless doodles to an aesthetic sensibility

Kao’s interest in telling stories through design and graphics started as mindless doodles in class, but soon grew into full-on illustrations that she later learned to turn into animations, using her computer science skills to bring her art to life. Looking at the illustrations, it’s easy to see that some of her inspiration comes from Japanese animator Hayao Miyazaki, but Kao cites the 2007 Disney film “Ratatouille” as her favorite animated movie.  

“I feel like part of my interest in art is that I was just in this constant stream of picture books and young adult books that I would read regardless of what age I was,” she says. “I still really enjoy some picture books.”

Kao also works with written narrative: As the literature editor of Rune, MIT’s literary magazine, during her sophomore year, she was responsible for vetting incoming submissions. For the past two years, she has focused more on her own writing, winning MIT’s Ilona Karmel Prize for Science Fiction in 2013 and 2014. 

Despite her passions in art and literature, Kao’s occupational focus remains with computer science, but always with her hobbies and upbringing as her guideposts.

“Computer graphics is that in-between space,” she says. “You need to have some kind of aesthetic sensibility, since the whole point is still to tell a story, but you’re using computer science and math to do that.” 

By Julia Sklar | MIT News correspondent