MIT Research News' Journal
[Most Recent Entries]
[Calendar View]
Wednesday, December 6th, 2017
| Time |
Event |
| 12:00a |
Try this! Researchers devise better recommendation algorithm The recommendation systems at websites such as Amazon and Netflix use a technique called “collaborative filtering.” To determine what products a given customer might like, they look for other customers who have assigned similar ratings to a similar range of products, and extrapolate from there.
The success of this approach depends vitally on the notion of similarity. Most recommendation systems use a measure called cosine similarity, which seems to work well in practice. Last year, at the Conference on Neural Information Processing Systems, MIT researchers used a new theoretical framework to demonstrate why, indeed, cosine similarity yields such good results.
This week, at the same conference, they are reporting that they have used their framework to construct a new recommendation algorithm that should work better than those in use today, particularly when ratings data is “sparse” — that is, when there is little overlap between the products reviewed and the ratings assigned by different customers.
The algorithm’s basic strategy is simple: When trying to predict a customer’s rating of a product, use not only the ratings from people with similar tastes but also the ratings from people who are similar to those people, and so on.
The idea is intuitive, but in practice, everything again hinges on the specific measure of similarity.
“If we’re really generous, everybody will effectively look like each other,” says Devavrat Shah, a professor of electrical engineering and computer science and senior author on the paper. “On the other hand, if we’re really stringent, we’re back to effectively just looking at nearest neighbors. Or putting it another way, when you move from a friend’s preferences to a friend of a friend’s, what is the noise introduced in the process, and is there a right way to quantify that noise so that we balance the signal we gain with the noise we introduce? Because of our model, we knew exactly what is the right thing to do.”
All the angles
As it turns out, the right thing to do is to again use cosine similarity. Essentially, cosine similarity represents a customer’s preferences as a line in a very high-dimensional space and quantifies similarity as the angle between two lines.
Suppose, for instance, that you have two points in a Cartesian plane, the two-dimensional coordinate system familiar from high school algebra. If you connect the points to the origin — the point with coordinates (0, 0) — you define an angle, and its cosine can be calculated from the point coordinates themselves.
If a movie-streaming service has, say, 5,000 titles in its database, then the ratings that any given user has assigned some subset of them defines a single point in a 5,000-dimensional space. Cosine similarity measures the angle between any two sets of ratings in that space.
When data is sparse, however, there may be so little overlap between users’ ratings that cosine similarity is essentially meaningless. In that context, aggregating the data of many users becomes necessary.
The researchers’ analysis is theoretical, but here’s an example of how their algorithm might work in practice. For any given customer, it would select a small set — say, five — of those customers with the greatest cosine similarity and average their ratings. Then, for each of those customers, it would select five similar customers, average their ratings, and fold that average into the cumulative average. It would continue fanning out in this manner, building up an increasingly complete set of ratings, until it had enough data to make a reasonable estimate about the rating of the product of interest.
Filling in blanks
For Shah and his colleagues — first author Christina Lee PhD ’17, who is a postdoc at Microsoft Research, and two of her Microsoft colleagues, Christian Borgs and Jennifer Chayes — devising such an algorithm wasn’t the hard part. The challenge was proving that it would work well, and that’s what the paper concentrates on.
Imagine a huge 2-D grid that maps all of a movie-streaming service’s users against all its titles, with a number in each cell that corresponds to a movie that a given user has rated. Most users have rated only a handful of movies, so most of the grid is empty. The goal of a recommendation engine is to fill in the empty grid cells as accurately as possible.
Ordinarily, Shah says, a machine-learning system learns two things: the features of the data set that are useful for prediction, and the mathematical function that computes a prediction from those features. For purposes of predicting movie tastes, useful features might include a movie’s genre, its box office performance, the number of Oscar nominations it received, the historical box-office success of its leads, its distributor, or any number of other things.
Each of a movie-streaming service’s customers has his or her own value function: One might be inclined to rate a movie much more highly if it fits in the action genre and has a big budget; another might give a high rating to a movie that received numerous Oscar nominations and has a small, arty distributor.
Playing the odds
In the new analytic scheme, “You don’t learn features; you don’t learn functions,” Shah says. But the researchers do assume that each user’s value function stays the same: The relative weight that a user assigns to, say, genre and distributor doesn’t change. The researchers also assume that each user’s function is operating on the same set of movie features.
This, it turns out, provides enough consistency that it’s possible to draw statistical inferences about the likelihood that one user’s ratings will predict another’s.
“When we sample a movie, we don’t actually know what its feature is, so if we wanted to exactly predict the function, we wouldn’t be able to,” Lee says. “But if we just wanted to estimate the difference between users’ functions, we can compute that difference.”
Using their analytic framework, the researchers showed that, in cases of sparse data — which describes the situation of most online retailers — their “neighbor’s-neighbor” algorithm should yield more accurate predictions than any known algorithm.
Translating between this type of theoretical algorithmic analysis and working computer systems, however, often requires some innovative engineering, so the researchers’ next step is to try to apply their algorithm to real data.
“The algorithm they present is simple, intuitive, and elegant,” says George Chen, an assistant professor at Carnegie Mellon University's Heinz College of Public Policy and Information Systems, who was not involved in the research. “I'd be surprised if others haven't tried an algorithm that is similar, although Devavrat and Christina's paper with Christian Borgs and Jennifer Chayes presents, to my knowledge, the first theoretical performance guarantees for such an algorithm that handles the sparse sampling regime, which is what's most practically relevant in many scenarios.” | | 1:00p |
Scientists observe supermassive black hole in infant universe A team of astronomers, including two from MIT, has detected the most distant supermassive black hole ever observed. The black hole sits in the center of an ultrabright quasar, the light of which was emitted just 690 million years after the Big Bang. That light has taken about 13 billion years to reach us — a span of time that is nearly equal to the age of the universe.
The black hole is measured to be about 800 million times as massive as our sun — a Goliath by modern-day standards and a relative anomaly in the early universe.
“This is the only object we have observed from this era,” says Robert Simcoe, the Francis L. Friedman Professor of Physics in MIT’s Kavli Institute for Astrophysics and Space Research. “It has an extremely high mass, and yet the universe is so young that this thing shouldn’t exist. The universe was just not old enough to make a black hole that big. It’s very puzzling.”
Adding to the black hole’s intrigue is the environment in which it formed: The scientists have deduced that the black hole took shape just as the universe was undergoing a fundamental shift, from an opaque environment dominated by neutral hydrogen to one in which the first stars started to blink on. As more stars and galaxies formed, they eventually generated enough radiation to flip hydrogen from neutral, a state in which hydrogen’s electrons are bound to their nucleus, to ionized, in which the electrons are set free to recombine at random. This shift from neutral to ionized hydrogen represented a fundamental change in the universe that has persisted to this day.
The team believes that the newly discovered black hole existed in an environment that was about half neutral, half ionized.
“What we have found is that the universe was about 50/50 — it’s a moment when the first galaxies emerged from their cocoons of neutral gas and started to shine their way out,” Simcoe says. “This is the most accurate measurement of that time, and a real indication of when the first stars turned on.”
Simcoe and postdoc Monica L. Turner are the MIT co-authors of a paper detailing the results, published today in the journal Nature. The other lead authors are from the Carnegie Institution for Science, in Pasadena, California.
A shift, at high speed
The black hole was detected by Eduardo Bañados, an astronomer at Carnegie, who found the object while combing through multiple all-sky surveys, or maps of the distant universe. Bañados was looking in particular for quasars — some of the brightest objects in the universe, that consist of a supermassive black hole surrounded by swirling, accreting disks of matter.
After identifying several objects of interest, Bañados focused in on them using an instrument known as FIRE (the Folded-port InfraRed Echellette), which was built by Simcoe and operates at the 6.5-meter-diameter Magellan telescopes in Chile. FIRE is a spectrometer that classifies objects based on their infrared spectra. The light from very distant, early cosmic objects shifts toward redder wavelengths on its journey across the universe, as the universe expands. Astronomers refer to this Doppler-like phenomenon as “redshift”; the more distant an object, the farther its light has shifted toward the red, or infrared end of the spectrum. The higher an object’s redshift, the further away it is, both in space and time.
Using FIRE, the team identified one of Bañados’ objects as a quasar with a redshift of 7.5, meaning the object was emitting light around 690 million years after the Big Bang. Based on the quasar’s redshift, the researchers calculated the mass of the black hole at its center and determined that it is around 800 million times the mass of the sun.
“Something is causing gas within the quasar to move around at very high speed, and the only phenomenon we know that achieves such speeds is orbit around a supermassive black hole,” Simcoe says.
When the first stars turned on
The newly identified quasar appears to inhabit a pivotal moment in the universe’s history. Immediately following the Big Bang, the universe resembled a cosmic soup of hot, extremely energetic particles. As the universe rapidly expanded, these particles cooled and coalesced into neutral hydrogen gas during an era that is sometimes referred to as the dark ages — a period bereft of any sources of light. Eventually, gravity condensed matter into the first stars and galaxies, which in turn produced light in the form of photons. As more stars turned on throughout the universe, their photons reacted with neutral hydrogen, ionizing the gas and setting off what’s known as the epoch of re-ionization.
Simcoe, Bañados, and their colleagues believe the newly discovered quasar existed during this fundamental transition, just at the time when the universe was undergoing a drastic shift in its most abundant element.
The researchers used FIRE to determine that a large fraction of the hydrogen surrounding the quasar is neutral. They extrapolated from that to estimate that the universe as a whole was likely about half neutral and half ionized at the time they observed the quasar. From this, they inferred that stars must have begun turning on during this time, 690 million years after the Big Bang.
“This adds to our understanding of our universe at large because we’ve identified that moment of time when the universe is in the middle of this very rapid transition from neutral to ionized,” Simcoe says. “We now have the most accurate measurements to date of when the first stars were turning on.”
There is one large mystery that remains to be solved: How did a black hole of such massive proportions form so early in the universe’s history? It’s thought that black holes grow by accreting, or absorbing mass from the surrounding environment. Extremely large black holes, such as the one identified by Simcoe and his colleagues, should form over periods much longer than 690 million years.
“If you start with a seed like a big star, and let it grow at the maximum possible rate, and start at the moment of the Big Bang, you could never make something with 800 million solar masses — it’s unrealistic,” Simcoe says. “So there must be another way that it formed. And how exactly that happens, nobody knows.”
This research was supported, in part, by the National Science Foundation (NSF), with support from construction of FIRE from NSF and from Curtis and Kathleen Marble. | | 4:25p |
J-PAL North America calls for proposals from governments and health care organizations J-PAL North America, a research center in the MIT Department of Economics, is announcing two calls for proposals designed to help policymakers better fight poverty. The competitions invite state and local governments and health care organizations to apply for support answering their priority policy questions using randomized evaluations.
State and local governments are increasingly looking to data and evidence to make better-informed decisions on behalf of the people they serve. Through the State and Local Innovation Initiative, J-PAL North America works to support governments in testing innovative approaches to addressing critical social challenges and building their capacity to create and use rigorous evidence. Governments previously selected through the initiative have taken on issues ranging from homelessness to unemployment to the opioid crisis.
“State and local governments often have opportunities to test out promising new ideas,” says initiative co-chair Melissa Kearney, a professor of economics at the University of Maryland and a non-resident senior fellow at the Brookings Institution. “By partnering with governments to help find answers to the tough problems they’re facing, we’re hoping to give policymakers the tools they need to better understand which programs work and why. We hope the lessons learned will also support other governments facing similar challenges.”
Health care agencies, organizations, and nonprofits face a similar challenge: While treatments are scientifically tested, the same level of rigor is not typically applied to health care delivery programs.
Low-income individuals and other vulnerable groups often have difficulty accessing effective treatments. With the Health Care Delivery Innovation Competition, J-PAL North America seeks to partner with organizations to evaluate ways to provide better health care for those who are currently underserved. Selected organizations have worked with J-PAL North America to evaluate substance abuse treatment, care integration, social-service delivery, and patient-engagement programs.
“There’s often a close connection between poverty and poor health in the United States,” says Amy Finkelstein, the Ford Professor of Economics at MIT and co-scientific director of J-PAL North America. “With this initiative, we want to help health care organizations find effective programs to make sure better services reach those who need them most.”
Through these two initiatives, J-PAL North America intends to help organizations answer practical questions about which social programs work, which work best, and why; as well as to build a greater culture of evidence-based policymaking.
Details on how to apply to the State and Local Innovation Initiative can be found online, or through information contact Julia Chabrier. Details on how to apply to the Health Care Delivery Innovation Competition can be found on the competition's web page, or through information contact Anna Spier.
J-PAL North America, a regional office of the Abdul Latif Jameel Poverty Action Lab, was established with support from the Alfred P. Sloan Foundation and the Laura and John Arnold Foundation. It works to reduce poverty by ensuring that policies are informed by scientific evidence. | | 11:59p |
Device makes power conversion more efficient Power electronics, which do things like modify voltages or convert between direct and alternating current, are everywhere. They’re in the power bricks we use to charge our portable devices; they’re in the battery packs of electric cars; and they’re in the power grid itself, where they mediate between high-voltage transmission lines and the lower voltages of household electrical sockets.
Power conversion is intrinsically inefficient: A power converter will never output quite as much power as it takes in. But recently, power converters made from gallium nitride have begun to reach the market, boasting higher efficiencies and smaller sizes than conventional, silicon-based power converters.
Commercial gallium nitride power devices can’t handle voltages above about 600 volts, however, which limits their use to household electronics.
At the Institute of Electrical and Electronics Engineers’ International Electron Devices Meeting this week, researchers from MIT, semiconductor company IQE, Columbia University, IBM, and the Singapore-MIT Alliance for Research and Technology, presented a new design that, in tests, enabled gallium nitride power devices to handle voltages of 1,200 volts.
That’s already enough capacity for use in electric vehicles, but the researchers emphasize that their device is a first prototype manufactured in an academic lab. They believe that further work can boost its capacity to the 3,300-to-5,000-volt range, to bring the efficiencies of gallium nitride to the power electronics in the electrical grid itself.
That’s because the new device uses a fundamentally different design from existing gallium nitride power electronics.
“All the devices that are commercially available are what are called lateral devices,” says Tomás Palacios, who is an MIT professor of electrical engineering and computer science, a member of the Microsystems Technology Laboratories, and senior author on the new paper. “So the entire device is fabricated on the top surface of the gallium nitride wafer, which is good for low-power applications like the laptop charger. But for medium- and high-power applications, vertical devices are much better. These are devices where the current, instead of flowing through the surface of the semiconductor, flows through the wafer, across the semiconductor. Vertical devices are much better in terms of how much voltage they can manage and how much current they control.”
For one thing, Palacios explains, current flows into one surface of a vertical device and out the other. That means that there’s simply more space in which to attach input and output wires, which enables higher current loads.
For another, Palacios says, “when you have lateral devices, all the current flows through a very narrow slab of material close to the surface. We are talking about a slab of material that could be just 50 nanometers in thickness. So all the current goes through there, and all the heat is being generated in that very narrow region, so it gets really, really, really hot. In a vertical device, the current flows through the entire wafer, so the heat dissipation is much more uniform.”
Narrowing the field
Although their advantages are well-known, vertical devices have been difficult to fabricate in gallium nitride. Power electronics depend on transistors, devices in which a charge applied to a “gate” switches a semiconductor material — such as silicon or gallium nitride — between a conductive and a nonconductive state.
For that switching to be efficient, the current flowing through the semiconductor needs to be confined to a relatively small area, where the gate’s electric field can exert an influence on it. In the past, researchers had attempted to build vertical transistors by embedding physical barriers in the gallium nitride to direct current into a channel beneath the gate.
But the barriers are built from a temperamental material that’s costly and difficult to produce, and integrating it with the surrounding gallium nitride in a way that doesn’t disrupt the transistor’s electronic properties has also proven challenging.
Palacios and his collaborators adopt a simple but effective alternative. The team includes first authors Yuhao Zhang, a postdoc in Palacios’s lab, and Min Sun, who received his MIT PhD in the Department of Electrical Engineering and Computer Science (EECS) last spring; Daniel Piedra and Yuxuan Lin, MIT graduate students in EECS; Jie Hu, a postdoc in Palacios’s group; Zhihong Liu of the Singapore-MIT Alliance for Research and Technology; Xiang Gao of IQE; and Columbia’s Ken Shepard.
Rather than using an internal barrier to route current into a narrow region of a larger device, they simply use a narrower device. Their vertical gallium nitride transistors have bladelike protrusions on top, known as “fins.” On both sides of each fin are electrical contacts that together act as a gate. Current enters the transistor through another contact, on top of the fin, and exits through the bottom of the device. The narrowness of the fin ensures that the gate electrode will be able to switch the transistor on and off.
“Yuhao and Min’s brilliant idea, I think, was to say, ‘Instead of confining the current by having multiple materials in the same wafer, let’s confine it geometrically by removing the material from those regions where we don’t want the current to flow,’” Palacios says. “Instead of doing the complicated zigzag path for the current in conventional vertical transistors, let’s change the geometry of the transistor completely.” |
|