Monthly Archives: August 2016

Mobile image processing in the cloud

As smartphones become people’s primary computers and their primary cameras, there is growing demand for mobile versions of image-processing applications.

Image processing, however, can be computationally intensive and could quickly drain a cellphone’s battery. Some mobile applications try to solve this problem by sending image files to a central server, which processes the images and sends them back. But with large images, this introduces significant delays and could incur costs for increased data usage.

At the Siggraph Asia conference last week, researchers from MIT, Stanford University, and Adobe Systems presented a system that, in experiments, reduced the bandwidth consumed by server-based image processing by as much as 98.5 percent, and the power consumption by as much as 85 percent.

The system sends the server a highly compressed version of an image, and the server sends back an even smaller file, which contains simple instructions for modifying the original image.

Michaël Gharbi, a graduate student in electrical engineering and computer science at MIT and first author on the Siggraph paper, says that the technique could become more useful as image-processing algorithms become more sophisticated.

“We see more and more new algorithms that leverage large databases to take a decision on the pixel,” Gharbi says. “These kinds of algorithm don’t do a very complex transform if you go to a local scale on the image, but they still require a lot of computation and access to the data. So that’s the kind of operation you would need to do on the cloud.”

One example, Gharbi says, is recent work at MIT that transfers the visual styles of famous portrait photographers to cellphone snapshots. Other researchers, he says, have experimented with algorithms for changing the apparent time of day at which photos were taken.

Joining Gharbi on the new paper are his thesis advisor, Frédo Durand, a professor of computer science and engineering; YiChang Shih, who received his PhD in electrical engineering and computer science from MIT in March; Gaurav Chaurasia, a former postdoc in Durand’s group who’s now at Disney Research; Jonathan Ragan-Kelley, who has been a postdoc at Stanford since graduating from MIT in 2014; and Sylvain Paris, who was a postdoc with Durand before joining Adobe.

The MIT Media Lab and Tufts University

Based on the ScratchJr programming language co-developed by the MIT Media Lab and Tufts University, PBS has released PBS KIDS ScratchJr, a free app to help children ages 5-8 learn coding concepts as they create their own stories and games using over 150 PBS KIDS characters.

With the PBS KIDS ScratchJr app, kids can snap together colorful programming blocks to make their favorite characters move, jump, dance, and sing. In the process, they learn to solve problems, design projects, and express themselves creatively. The free app is now available from the App Store on iPad and from the Google Play store on Android tablet.

Through outreach efforts supported by the Verizon Foundation and the Ready To Learn Initiative, PBS member stations will extend the reach of PBS KIDS ScratchJr to children in underserved communities across the U.S. through programs and partnerships with Title I schools. Verizon will also be supporting the development of after-school activities and a weeklong summer camp. In addition, PBS stations will provide professional development training pilots to help teachers integrate PBS KIDS ScratchJr into classroom activities.

“We see coding as a new way for people to organize, express, and share their ideas,” said Mitchel Resnick, the LEGO Papert Professor of Learning Research at MIT, head of the Media Lab’s Lifelong Kindergarten group, and director of its Scratch team. “Coding is not just a set of technical skills, but a new type of literacy and personal expression, valuable for everyone, much like learning to write.”

To help ScratchJr learners get more out of the programming language, Media Lab alumna Professor Marina Umaschi Bers, director of the Developmental Technologies Research Group at Tufts University, and Resnick have co-authored “The Official ScratchJr Book: Help Your Kids Learn to Code,” released in November.

The app has been developed as part of the Corporation for Public Broadcasting and PBS Ready To Learn Initiative with funding from the U.S. Department of Education. Ready To Learn is a federal program that supports the development of innovative educational television and digital media targeted at preschool and early elementary school children and their families.

Computer scientists build a professional network

Success in higher education, especially for women in computer science and electrical engineering, takes a network. And while some connections are only a text message or tweet away, the personal touch still matters, and it works differently.

For graduate students like Judy Hoffman, who studies adaptive learning algorithms at the University of California at Berkeley, there is no substitute for actually meeting fellow female engineers and computer scientists in person. To make this happen, the Department of Electrical Engineering and Computer Science (EECS) hosts “Rising Stars in EECS,” a three-day workshop for graduate students and postdocs who are considering careers in academic research.

“Rising Stars helped me connect with current and future leaders in our field, all within a very supportive environment,” says Hoffman, one of 61 attendees who came to campus this year. “I have a good sense of where I want to go with my research,” she adds, but “the workshop provided me with the insights I needed to successfully navigate the process.”

Network effect

Created in 2012 by EECS head Anantha Chandrakasan, Rising Stars has nearly doubled in size since its inception. More than just a meet-up, Rising Stars offers women in EECS the opportunity to learn by doing, with sessions focused on landing a faculty job, gaining tenure, and building a professional support network.

Participants and speakers candidly discussed how to tackle common issues such as dual-career hiring (when an applicant’s spouse is also seeking a job in academia), work-life balance, and family leave policies. Attendees also presented their research at a poster session and gave talks about their research (Hoffman presented her work on the performance of deep visual models). All sessions are designed to help demystify what many young female faculty describe as the “black box” of academic hiring and the tenure process.

“We hope to give them the information they need to be successful as they explore job opportunities,” says Chandrakasan, the Vannevar Bush Professor of Electrical Engineering and Computer Science. “But we also feel very strongly about giving participants a chance to get to know each other and make lasting connections. These connections can open doors for collaborations and provide professional support for years to come.”

While MIT and other institutions have had success in attracting an increasing number of female students to EECS — 43 percent of sophomores studying EECS at MIT are women — the journey can still be a lonely one. Many of the participants at Rising Stars shared a common experience: being one of only a handful of women at their home lab.

Precious Cantú, a Fulbright Postdoctoral Fellow at the Swiss Federal Institute of Technology in Lausanne, says, “It was amazing to see such a large group of women in one room, but once we got into the talks and presentations, we were all just scientists and engineers together in a room doing fantastic science.”

“It’s great to listen to so many presentations. It has really motivated me to work even harder,” adds Kun (Linda) Li, a graduate student at the University of California at Berkeley.

Computer exploits quantum phenomena

In 2010, a Canadian company called D-Wave announced that it had begun production of what it called the world’s first commercial quantum computer, which was based on theoretical work done at MIT. Quantum computers promise to solve some problems significantly faster than classical computers — and in at least one case, exponentially faster. In 2013, a consortium including Google and NASA bought one of D-Wave’s machines.

Over the years, critics have argued that it’s unclear whether the D-Wave machine is actually harnessing quantum phenomena to perform its calculations, and if it is, whether it offers any advantages over classical computers. But this week, a group of Google researchers released a paper claiming that in their experiments, a quantum algorithm running on their D-Wave machine was 100 million times faster than a comparable classical algorithm.

Scott Aaronson, an associate professor of electrical engineering and computer science at MIT, has been following the D-Wave story for years. MIT News asked him to help make sense of the Google researchers’ new paper.

Q: The Google researchers’ paper focused on two algorithms: simulated annealing and quantum annealing. What are they?

A: Simulated annealing is one of the premier optimization methods that’s used today. It was invented in the early 1980s by direct analogy with what happens when people anneal metals, which is a 7,000-year-old technology. You heat the metal up, the atoms are all jiggling around randomly, and as you slowly cool it down, the atoms are more and more likely to go somewhere that will decrease the total energy.

In the case of an algorithm, you have a whole bunch of bits that start flipping between 1 and 0 willy-nilly, regardless of what that does to the solution quality. And then as you lower the “temperature,” a bit becomes more and more unwilling to flip in a way that would make the solution worse, until at the end, when the temperature is zero, a bit will only go to the value that keeps the solution going straight downhill — toward better solutions.

The main problem with simulated annealing, or for that matter with any other local-search method, is that you can get stuck in local optima. If you’re trying to reach the lowest point in some energy landscape, you can get stuck in a crevice that is locally the best, but you don’t realize that there’s a much lower valley somewhere else, if you would only go up and search. Simulated annealing tries to deal with that already: When the temperature is high, then you’re willing to move up the hill sometimes. But if there’s a really tall hill, even if it’s a very, very narrow hill — just imagine it’s a big spike sticking out of the ground — it could take you an exponential amount of time until you happen to flip so many bits that you happen to get over that spike.

In quantum mechanics, we know that particles can tunnel through barriers. (This is the language that the physicists use, which is a little bit misleading.) There’s an important 2002 paper by Farhi, Goldstone, and Gutmann, all of whom are here at MIT, and what they showed is that if your barrier really is a tall thin spike, then quantum annealing can give you an exponential speedup over classical simulated annealing. Classical annealing is going to get stuck at the base of that spike for exponential time, and quantum annealing is going to tunnel over it and get down to the global minimum in polynomial time.

Q: So is the D-Wave machine using quantum tunneling?

A: In the current model of the D-Wave chip, there are 1,000 or so qubits [quantum bits], but they’re organized into clusters of eight qubits each. The qubits within each cluster are very tightly connected to each other, and between clusters there are only weaker connections. I think that this is the best evidence we’ve had so far for quantum tunneling behavior, at least at the level of the eight-bit clusters.

Eye tracking research reveals which types of visuals

Spend 10 minutes on social media, and you’ll learn that people love infographics. But why, exactly, do we gravitate towards articles with titles like “24 Diagrams to Help You Eat Healthier” and “All You Need To Know About Beer In One Chart”? Do they actually serve their purpose of not only being memorable, but actually helping us comprehend and retain information?

Researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) and Harvard University are on the case.

In a new study that analyzes people’s eye-movements and text responses as they look at charts, graphs, and infographics, researchers have been able to determine which aspects of visualizations make them memorable, understandable, and informative — and reveal how to make sure your own graphics really pop.

Presenting a paper last week at the proceedings for the IEEE Information Visualization Conference (InfoViz) in Chicago, the team members say that their findings can provide better design principles for communications in industries such as marketing, business, and education, as well as teach us more about how human memory, attention, and comprehension work.

“By integrating multiple methods, including eye-tracking, text recall, and memory tests, we were able to develop what is, to our knowledge, the largest and most comprehensive user study to date on visualizations,” says CSAIL PhD student Zoya Bylinskii, first-author on the paper alongside Michelle Borkin, a former doctoral student at Harvard’s John A. Paulson School of Engineering and Applied Sciences (SEAS) who is now an assistant professor at Northeastern University.

The paper’s other co-authors include Bylinskii’s advisor, MIT principal research scientist Aude Oliva; CSAIL research assistant Constance May Bainbridge; Harvard graduate student Nam Wook Kim, former Harvard undergraduate Chelsea S. Yeh and research intern Daniel Borkin; and Harvard professor Hanspeter Pfister.

Visual Turing test

Researchers at MIT, New York University, and the University of Toronto have developed a computer system whose ability to produce a variation of a character in an unfamiliar writing system, on the first try, is indistinguishable from that of humans.

That means that the system in some sense discerns what’s essential to the character — its general structure — but also what’s inessential — the minor variations characteristic of any one instance of it.

As such, the researchers argue, their system captures something of the elasticity of human concepts, which often have fuzzy boundaries but still seem to delimit coherent categories. It also mimics the human ability to learn new concepts from few examples. It thus offers hope, they say, that the type of computational structure it’s built on, called a probabilistic program, could help model human acquisition of more sophisticated concepts as well.

“In the current AI landscape, there’s been a lot of focus on classifying patterns,” says Josh Tenenbaum, a professor in the Department of Brain and Cognitive sciences at MIT, a principal investigator in the MIT Center for Brains, Minds and Machines, and one of the new system’s co-developers. “But what’s been lost is that intelligence isn’t just about classifying or recognizing; it’s about thinking.”

“This is partly why, even though we’re studying hand-written characters, we’re not shy about using a word like ‘concept,’” he adds. “Because there are a bunch of things that we do with even much richer, more complex concepts that we can do with these characters. We can understand what they’re built out of. We can understand the parts. We can understand how to use them in different ways, how to make new ones.”

The new system was the thesis work of Brenden Lake, who earned his PhD in cognitive science from MIT last year as a member of Tenenbaum’s group, and who won the Glushko Prize for outstanding dissertations from the Cognitive Science Society. Lake, who is now a postdoc at New York University, is first author on a paper describing the work in the latest issue of the journal Science. He’s joined by Tenenbaum and Ruslan Salakhutdinov, an assistant professor of computer science at the University of Toronto who was a postdoc in Tenenbaum’s group from 2009 to 2011.

Rough ideas

“We analyzed these three core principles throughout the paper,” Lake says. “The first we called compositionality, which is the idea that representations are built up from simpler primitives. Another is causality, which is that the model represents the abstract causal structure of how characters are generated. And the last one was learning to learn, this idea that knowledge of previous concepts can help support the learning of new concepts. Those ideas are relatively general. They can apply to characters, but they could apply to many other types of concepts.”

The researchers subjected their system to a battery of tests. In one, they presented it with a single example of a character in a writing system it had never seen before and asked it to produce new instances of the same character — not identical copies, but nine different variations on the same character. In another test, they presented it with several characters in an unfamiliar writing system and asked it to produce new characters that were in some way similar. And in a final test, they asked it to make up entirely new characters in a hypothetical writing system.

Human subjects were then asked to perform the same three tasks. Finally, a separate group of human judges was asked to distinguish the human subjects’ work from the machine’s. Across all three tasks, the judges could identify the machine outputs with about 50 percent accuracy — no better than chance.

Conventional machine-learning systems — such as the ones that led to the speech-recognition algorithms on smartphones — often perform very well on constrained classification tasks, but they must first be trained on huge sets of training data. Humans, by contrast, frequently grasp concepts after just a few examples. That type of “one-shot learning” is something that the researchers designed their system to emulate.

Learning to learn

Like a human subject, however, the system comes to a new task with substantial background knowledge, which in this case is captured by a probabilistic program. Whereas a conventional computer program systematically decomposes a high-level task into its most basic computations, a probabilistic program requires only a very sketchy model of the data it will operate on. Inference algorithms then fill in the details of the model by analyzing a host of examples.

Startup makes synthesizing

Inside and outside of the classroom, MIT professor Joseph Jacobson has become a prominent figure in — and advocate for — the emerging field of synthetic biology.

As head of the Molecular Machines group at the MIT Media Lab, Jacobson’s work has focused on, among other things, developing technologies for the rapid fabrication of DNA molecules. In 2009, he spun out some of his work into Gen9, which aims to boost synthetic-biology innovation by offering scientists more cost-effective tools and resources.

Headquartered in Cambridge, Massachusetts, Gen9 has developed a method for synthesizing DNA on silicon chips, which significantly cuts costs and accelerates the creation and testing of genes. Commercially available since 2013, the platform is now being used by dozens of scientists and commercial firms worldwide.

Synthetic biologists synthesize genes by combining strands of DNA. These new genes can be inserted into microorganisms such as yeast and bacteria. Using this approach, scientists can tinker with the cells’ metabolic pathways, enabling the microbes to perform new functions, including testing new antibodies, sensing chemicals in an environment, or creating biofuels.

But conventional gene-synthesizing methods can be time-consuming and costly. Chemical-based processes, for instance, cost roughly 20 cents per base pair — DNA’s key building block — and produce one strand of DNA at a time. This adds up in time and money when synthesizing genes comprising 100,000 base pairs.

Gen9’s chip-based DNA, however, drops the price to roughly 2 cents per base pair, Jacobson says. Additionally, hundreds of thousands of base pairs can be tested and compiled in parallel, as opposed to testing and compiling each pair individually through conventional methods.

This means faster testing and development of new pathways — which usually takes many years — for applications such as advanced therapeutics, and more effective enzymes for detergents, food processing, and biofuels, Jacobson says. “If you can build thousands of pathways on a chip in parallel, and can test them all at once, you get to a working metabolic pathway much faster,” he says.

Over the years, Jacobson and Gen9 have earned many awards and honors. In November, Jacobson was also inducted into the National Inventors Hall of Fame for co-inventing E Ink, the electronic ink used for Amazon’s Kindle e-reader display.

Scaling gene synthesizing

Throughout the early-and mid-2000s, a few important pieces of research came together to allow for the scaling up of gene synthesis, which ultimately led to Gen9.

First, Jacobson and his students Chris Emig and Brian Chow began developing chips with thousands of “spots,” which each contained about 100 million copies of a different DNA sequence.

Then, Jacobson and another student, David Kong, created a process that used a certain enzyme as a catalyst to assemble those small DNA fragments into larger DNA strands inside microfluidics devices — “which was the first microfluidics assembly of DNA ever,” Jacobson says.

Despite the novelty, however, the process still wasn’t entirely cost effective. On average, it produced a 99 percent yield, meaning that about 1 percent of the base pairs didn’t match when constructing larger strands. That’s not so bad for making genes with 100 base pairs. “But if you want to make something that’s 10,000 or 100,000 bases long, that’s no good anymore,” Jacobson says.