Category Archives: Computer and Website

Algorithms to improve computer networks

Daniel Zuo came to MIT with a plan: He wanted to study algorithms and one day to become a research professor.

The senior has more than accomplished the former goal, conducting innovative research on algorithms to reduce network congestion, in the Networks and Mobile Systems group at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL). And, as he graduates this spring with a bachelor’s degree in computer science and electrical engineering and a master’s in engineering, he is well on his way to achieving the latter one.

But Zuo has also taken some productive detours from that roadmap, including minoring in creative writing and helping to launch MakeMIT, the nation’s largest “hardware hackathon.”

The next step in his journey will take him to Cambridge University, where he will continue his computer science research as a Marshall Scholar.

“The Marshall affords me the opportunity to keep exploring for a couple more years on an academic level, and to grow on a personal level, too,” Zuo says. While studying in the Advanced Computer Science program at the university’s Computer Laboratory, “I’ll be able to work with networks and systems to deepen my understanding and take more time to explore this field,” he says.

Algorithms to connect the world

Zuo fell in love with algorithms his first year at MIT. “It was exactly what I was looking for,” he says with a smile. “I took every algorithms course there was on offer.”

His first research experience, the summer after his freshman year, was in the lab of Professor Manolis Kellis, head of the Computational Biology group at CSAIL. Zuo worked with a postdoc in Kellis’ group to use algorithms to identify related clusters of genes in a single cell type within a specific tissue. “We ended up coming up with a pretty cool algorithm,” he says.

As a research assistant for TIBCO Career Development Assistant Professor Mohammad Alizadeh, Zuo is now working on cutting-edge algorithms for congestion control in networks, with a focus on “lossless” data networks.

Modern computer network applications need to be able to transmit large amounts of data quickly, without losing information. Zuo likens the situation to a congested traffic light. When there are too many messages queuing at the light, some information just gets dropped.

“When the traffic light starts to get too full, I can send a packet back upstream that says ‘Wait, if you’re going to send me something, don’t,’” he explains. But sending that signal can create a new problem: a “back-propagation” of even more pauses, and more congestion upstream. Zuo’s algorithms aim to solve both of these problems, ensuring that sent data are never lost and that “traffic lights” don’t become too crowded.

“The idea is we can create a network that never drops a packet of information. I’ve been exploring how to do congestion-control algorithms on these lossless networks, which are becoming more popular,” he says.

Reducing congestion to achieve truly lossless networks could free up a lot of system space and funding for software developers that typically goes to toward maintaining data centers.

“Making communicating within a network more efficient and more reliable can open the door to having more wireless connections across the world,” Zuo says.

Wireless access point towers are ‘leapfrogging’ fiber optic cable in some rural parts of the developing world, he says. Algorithms like his could lower the costs and improve the efficiency of those connections — thereby reducing some key barriers to connectivity in far-flung places. “It’s a long-term goal, and it’s why I’m interested in this field.”

“We’re one of the most connected societies in the world,” he says. “But there are so many places in the world that don’t have this ability. Even if you have amazing ideas, you don’t have access to get your voice heard.”

The programs earn top marks from US

U.S. News and World Report has again placed MIT’s graduate program in engineering at the top of its annual rankings, continuing a trend that began in 1990, when the magazine first ranked such programs.

The MIT Sloan School of Management also placed highly; it shares with Stanford University the No. 4 spot for the best graduate business program.

This year, U.S. News also ranked graduate programs in the social sciences and humanities. The magazine awarded MIT’s graduate program in economics a No. 1 ranking, along with Harvard University, Princeton University, Stanford, the University of California at Berkeley, and Yale University.

Among individual engineering disciplines, MIT placed first in six areas: biomedical/bioengineering (tied with Johns Hopkins University — MIT’s first-ever No. 1 U.S. News ranking in this discipline); chemical engineering; computer engineering; electrical/electronic/communications engineering; materials engineering; and mechanical engineering (tied with Stanford). The Institute placed second in aerospace/aeronautical/astronautical engineering (tied with Georgia Tech) and nuclear engineering.

In the rankings of graduate programs in business, MIT Sloan moved up one step from its No. 5 spot last year. U.S. News awarded a No. 1 ranking to the school’s specialties in information systems and production/operations, and a No. 2 ranking for supply chain/logistics.

U.S. News does not issue annual rankings for all doctoral programs but revisits many every few years. In its new evaluation of programs in the social science and humanities, the magazine gave MIT’s economics program a No. 1 ranking overall and either first- or second-place rankings for all eight economics specialties listed. MIT’s political science and psychology programs also placed among the top 10 in the nation.

In the magazine’s 2014 evaluation of PhD programs in the sciences, five MIT programs earned a No. 1 ranking: biological sciences (tied with Harvard and Stanford); chemistry (tied with Caltech and Berkeley, and with a No. 1 ranking in the specialty of inorganic chemistry); computer science (tied with Carnegie Mellon University, Stanford, and Berkeley); mathematics (tied with Princeton University, and with a No. 1 ranking in the specialty of discrete mathematics and combinations); and physics.

U.S. News bases its rankings of graduate schools of engineering and business on two types of data: reputational surveys of deans and other academic officials, and statistical indicators that measure the quality of a school’s faculty, research, and students. The magazine’s less-frequent rankings of programs in the sciences, social sciences, and humanities are based solely on reputational surveys.

Help make a ubiquitous model of decision processes more accurate

Markov decision processes are mathematical models used to determine the best courses of action when both current circumstances and future consequences are uncertain. They’ve had a huge range of applications — in natural-resource management, manufacturing, operations management, robot control, finance, epidemiology, scientific-experiment design, and tennis strategy, just to name a few.

But analyses involving Markov decision processes (MDPs) usually make some simplifying assumptions. In an MDP, a given decision doesn’t always yield a predictable result; it could yield a range of possible results. And each of those results has a different “value,” meaning the chance that it will lead, ultimately, to a desirable outcome.

Characterizing the value of given decision requires collection of empirical data, which can be prohibitively time consuming, so analysts usually just make educated guesses. That means, however, that the MDP analysis doesn’t guarantee the best decision in all cases.

In the Proceedings of the Conference on Neural Information Processing Systems, published last month, researchers from MIT and Duke University took a step toward putting MDP analysis on more secure footing. They show that, by adopting a simple trick long known in statistics but little applied in machine learning, it’s possible to accurately characterize the value of a given decision while collecting much less empirical data than had previously seemed necessary.

In their paper, the researchers described a simple example in which the standard approach to characterizing probabilities would require the same decision to be performed almost 4 million times in order to yield a reliable value estimate.

With the researchers’ approach, it would need to be run 167,000 times. That’s still a big number — except, perhaps, in the context of a server farm processing millions of web clicks per second, where MDP analysis could help allocate computational resources. In other contexts, the work at least represents a big step in the right direction.

“People are not going to start using something that is so sample-intensive right now,” says Jason Pazis, a postdoc at the MIT Laboratory for Information and Decision Systems and first author on the new paper. “We’ve shown one way to bring the sample complexity down. And hopefully, it’s orthogonal to many other ways, so we can combine them.”

Unpredictable outcomes

In their paper, the researchers also report running simulations of a robot exploring its environment, in which their approach yielded consistently better results than the existing approach, even with more reasonable sample sizes — nine and 105. Pazis emphasizes, however, that the paper’s theoretical results bear only on the number of samples required to estimate values; they don’t prove anything about the relative performance of different algorithms at low sample sizes.

Pazis is joined on the paper by Jonathan How, the Richard Cockburn Maclaurin Professor of Aeronautics and Astronautics at MIT, and by Ronald Parr, a professor of computer science at Duke.

Although the possible outcomes of a decision may be described according to a probability distribution, the expected value of the decision is just the mean, or average, value of all outcomes. In the familiar bell curve of the so-called normal distribution, the mean defines the highest point of the bell.

The trick the researchers’ algorithm employs is called the median of means. If you have a bunch of random values, and you’re asked to estimate the mean of the probability distribution they’re drawn from, the natural way to do it is to average them. But if your sample happens to include some rare but extreme outliers, averaging can give a distorted picture of the true distribution. For instance, if you have a sample of the heights of 10 American men, nine of whom cluster around the true mean of 5 feet 10 inches, but one of whom is a 7-foot-2-inch NBA center, straight averaging will yield a mean that’s off by about an inch and a half.

Communication networks from malicious hackers

Distributed planning, communication, and control algorithms for autonomous robots make up a major area of research in computer science. But in the literature on multirobot systems, security has gotten relatively short shrift.

In the latest issue of the journal Autonomous Robots, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory and their colleagues present a new technique for preventing malicious hackers from commandeering robot teams’ communication networks. The technique could provide an added layer of security in systems that encrypt communications, or an alternative in circumstances in which encryption is impractical.

“The robotics community has focused on making multirobot systems autonomous and increasingly more capable by developing the science of autonomy. In some sense we have not done enough about systems-level issues like cybersecurity and privacy,” says Daniela Rus, an Andrew and Erna Viterbi Professor of Electrical Engineering and Computer Science at MIT and senior author on the new paper.

“But when we deploy multirobot systems in real applications, we expose them to all the issues that current computer systems are exposed to,” she adds. “If you take over a computer system, you can make it release private data — and you can do a lot of other bad things. A cybersecurity attack on a robot has all the perils of attacks on computer systems, plus the robot could be controlled to take potentially damaging action in the physical world. So in some sense there is even more urgency that we think about this problem.”

Identity theft

Most planning algorithms in multirobot systems rely on some kind of voting procedure to determine a course of action. Each robot makes a recommendation based on its own limited, local observations, and the recommendations are aggregated to yield a final decision.

A natural way for a hacker to infiltrate a multirobot system would be to impersonate a large number of robots on the network and cast enough spurious votes to tip the collective decision, a technique called “spoofing.” The researchers’ new system analyzes the distinctive ways in which robots’ wireless transmissions interact with the environment, to assign each of them its own radio “fingerprint.” If the system identifies multiple votes as coming from the same transmitter, it can discount them as probably fraudulent.

“There are two ways to think of it,” says Stephanie Gil, a research scientist in Rus’ Distributed Robotics Lab and a co-author on the new paper. “In some cases cryptography is too difficult to implement in a decentralized form. Perhaps you just don’t have that central key authority that you can secure, and you have agents continually entering or exiting the network, so that a key-passing scheme becomes much more challenging to implement. In that case, we can still provide protection.

“And in case you can implement a cryptographic scheme, then if one of the agents with the key gets compromised, we can still provide  protection by mitigating and even quantifying the maximum amount of damage that can be done by the adversary.”

Prevent customer profiling and price gouging

Most website visits these days entail a database query — to look up airline flights, for example, or to find the fastest driving route between two addresses.

But online database queries can reveal a surprising amount of information about the people making them. And some travel sites have been known to jack up the prices on flights whose routes are drawing an unusually high volume of queries.

At the USENIX Symposium on Networked Systems Design and Implementation next week, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory and Stanford University will present a new encryption system that disguises users’ database queries so that they reveal no private information.

The system is called Splinter because it splits a query up and distributes it across copies of the same database on multiple servers. The servers return results that make sense only when recombined according to a procedure that the user alone knows. As long as at least one of the servers can be trusted, it’s impossible for anyone other than the user to determine what query the servers executed.

“The canonical example behind this line of work was public patent databases,” says Frank Wang, an MIT graduate student in electrical engineering and computer science and first author on the conference paper. “When people were searching for certain kinds of patents, they gave away the research they were working on. Stock prices is another example: A lot of the time, when you search for stock quotes, it gives away information about what stocks you’re going to buy. Another example is maps: When you’re searching for where you are and where you’re going to go, it reveals a wealth of information about you.”

Honest broker

Of course, if the site that hosts the database is itself collecting users’ data without their consent, the requirement of at least one trusted server is difficult to enforce.

Wang, however, points to the increasing popularity of services such as DuckDuckGo, a search engine that uses search results from other sites, such as Bing and Yahoo, but vows not to profile its customers.

“We see a shift toward people wanting private queries,” Wang says. “We can imagine a model in which other services scrape a travel site, and maybe they volunteer to host the information for you, or maybe you subscribe to them. Or maybe in the future, travel sites realize that these services are becoming more popular and they volunteer the data. But right now, we’re trusting that third-party sites have adequate protections, and with Splinter we try to make that more of a guarantee.”

Traffic management solutions for data center networks

The transmission control protocol, or TCP, which manages traffic on the internet, was first proposed in 1974. Some version of TCP still regulates data transfer in most major data centers, the huge warehouses of servers maintained by popular websites.

That’s not because TCP is perfect or because computer scientists have had trouble coming up with possible alternatives; it’s because those alternatives are too hard to test. The routers in data center networks have their traffic management protocols hardwired into them. Testing a new protocol means replacing the existing network hardware with either reconfigurable chips, which are labor-intensive to program, or software-controlled routers, which are so slow that they render large-scale testing impractical.

At the Usenix Symposium on Networked Systems Design and Implementation later this month, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory will present a system for testing new traffic management protocols that requires no alteration to network hardware but still works at realistic speeds — 20 times as fast as networks of software-controlled routers.

The system maintains a compact, efficient computational model of a network running the new protocol, with virtual data packets that bounce around among virtual routers. On the basis of the model, it schedules transmissions on the real network to produce the same traffic patterns. Researchers could thus run real web applications on the network servers and get an accurate sense of how the new protocol would affect their performance.

“The way it works is, when an endpoint wants to send a [data] packet, it first sends a request to this centralized emulator,” says Amy Ousterhout, a graduate student in electrical engineering and computer science (EECS) and first author on the new paper. “The emulator emulates in software the scheme that you want to experiment with in your network. Then it tells the endpoint when to send the packet so that it will arrive at its destination as though it had traversed a network running the programmed scheme.”

Ousterhout is joined on the paper by her advisor, Hari Balakrishnan, the Fujitsu Professor in Electrical Engineering and Computer Science; Jonathan Perry, a graduate student in EECS; and Petr Lapukhov of Facebook.

Traffic control

Each packet of data sent over a computer network has two parts: the header and the payload. The payload contains the data the recipient is interested in — image data, audio data, text data, and so on. The header contains the sender’s address, the recipient’s address, and other information that routers and end users can use to manage transmissions.

When multiple packets reach a router at the same time, they’re put into a queue and processed sequentially. With TCP, if the queue gets too long, subsequent packets are simply dropped; they never reach their recipients. When a sending computer realizes that its packets are being dropped, it cuts its transmission rate in half, then slowly ratchets it back up.

Other critical infrastructure

In a world where hackers can sabotage power plants and impact elections, there has never been a more crucial time to examine cybersecurity for critical infrastructure, most of which is privately owned.

According to MIT experts, over the last 25 years presidents from both parties have paid lip service to the topic while doing little about it, leading to a series of short-term fixes they liken to a losing game of “Whac-a-Mole.” This scattershot approach, they say, endangers national security.

In a new report based on a year of workshops with leaders from industry and government, the MIT team has made a series of recommendations for the Trump administration to develop a coherent cybersecurity plan that coordinates efforts across departments, encourages investment, and removes parts of key infrastructure like the electric grid from the internet.

Coming on the heels of a leak of the new administration’s proposed executive order on cybersecurity, the report also recommends changes in tax law and regulations to incentivize private companies to improve the security of their critical infrastructure. While the administration is focused on federal systems, the MIT team aimed to address what’s left out of that effort: privately-owned critical infrastructure.

“The nation will require a coordinated, multi-year effort to address deep strategic weaknesses in the architecture of critical systems, in how those systems are operated, and in the devices that connect to them,” the authors write. “But we must begin now. Our goal is action, both immediate and long-term.”

Entitled “Making America Safer: Toward a More Secure Network Environment for Critical Sectors,” the 50-page report outlines seven strategic challenges that would greatly reduce the risks from cyber attacks in the sectors of electricity, finance, communications and oil/natural gas. The workshops included representatives from major companies from each sector, and focused on recommendations related to immediate incentives, long-term research and streamlined regulation.

The report was published by MIT’s Internet Policy Research Initiative (IPRI) at the Computer Science and Artificial Intelligence Laboratory (CSAIL), in conjunction with MIT’s Center for International Studies (CIS). Principal author Joel Brenner was formerly inspector general of the National Security Agency and head of U.S. counterintelligence in the Office of the Director of National Intelligence. Other contributors include Hal Abelson, David Clark, Shirley Hung, Kenneth Oye, Richard Samuels, John Tirman and Daniel Weitzner.

To determine what a better security environment would look like, the researchers convened a series of workshops aimed at going beyond the day-to-day tactical challenges to look at deep cyber vulnerabilities.

The workshops highlighted the difficulty of quantifying the level of risk across different sectors and the return on investment for specific cybersecurity measures. In light of facility-directed attacks like the Stuxnet virus and the sabotage of a Saudi oil refinery, attendees expressed deep concern about the security of infrastructure like the electric grid, which depends on public networks.

Intelligence technique known as deep learning

In the past 10 years, the best-performing artificial-intelligence systems — such as the speech recognizers on smartphones or Google’s latest automatic translator — have resulted from a technique called “deep learning.”

Deep learning is in fact a new name for an approach to artificial intelligence called neural networks, which have been going in and out of fashion for more than 70 years. Neural networks were first proposed in 1944 by Warren McCullough and Walter Pitts, two University of Chicago researchers who moved to MIT in 1952 as founding members of what’s sometimes called the first cognitive science department.

Neural nets were a major area of research in both neuroscience and computer science until 1969, when, according to computer science lore, they were killed off by the MIT mathematicians Marvin Minsky and Seymour Papert, who a year later would become co-directors of the new MIT Artificial Intelligence Laboratory.

The technique then enjoyed a resurgence in the 1980s, fell into eclipse again in the first decade of the new century, and has returned like gangbusters in the second, fueled largely by the increased processing power of graphics chips.

“There’s this idea that ideas in science are a bit like epidemics of viruses,” says Tomaso Poggio, the Eugene McDermott Professor of Brain and Cognitive Sciences at MIT, an investigator at MIT’s McGovern Institute for Brain Research, and director of MIT’s Center for Brains, Minds, and Machines. “There are apparently five or six basic strains of flu viruses, and apparently each one comes back with a period of around 25 years. People get infected, and they develop an immune response, and so they don’t get infected for the next 25 years. And then there is a new generation that is ready to be infected by the same strain of virus. In science, people fall in love with an idea, get excited about it, hammer it to death, and then get immunized — they get tired of it. So ideas should have the same kind of periodicity!”

Weighty matters

Neural nets are a means of doing machine learning, in which a computer learns to perform some task by analyzing training examples. Usually, the examples have been hand-labeled in advance. An object recognition system, for instance, might be fed thousands of labeled images of cars, houses, coffee cups, and so on, and it would find visual patterns in the images that consistently correlate with particular labels.

Modeled loosely on the human brain, a neural net consists of thousands or even millions of simple processing nodes that are densely interconnected. Most of today’s neural nets are organized into layers of nodes, and they’re “feed-forward,” meaning that data moves through them in only one direction. An individual node might be connected to several nodes in the layer beneath it, from which it receives data, and several nodes in the layer above it, to which it sends data.

To each of its incoming connections, a node will assign a number known as a “weight.” When the network is active, the node receives a different data item — a different number — over each of its connections and multiplies it by the associated weight. It then adds the resulting products together, yielding a single number. If that number is below a threshold value, the node passes no data to the next layer. If the number exceeds the threshold value, the node “fires,” which in today’s neural nets generally means sending the number — the sum of the weighted inputs — along all its outgoing connections.

When a neural net is being trained, all of its weights and thresholds are initially set to random values. Training data is fed to the bottom layer — the input layer — and it passes through the succeeding layers, getting multiplied and added together in complex ways, until it finally arrives, radically transformed, at the output layer. During training, the weights and thresholds are continually adjusted until training data with the same labels consistently yield similar outputs.

Web browsers to harness micro-moment

Hyper-connectivity has changed the way we communicate, wait, and productively use our time. Even in a world of 5G wireless and “instant” messaging, there are countless moments throughout the day when we’re waiting for messages, texts, and Snapchats to refresh. But our frustrations with waiting a few extra seconds for our emails to push through doesn’t mean we have to simply stand by.

To help us make the most of these “micro-moments,” researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) have developed a series of apps called “WaitSuite” that test you on vocabulary words during idle moments, like when you’re waiting for an instant message or for your phone to connect to WiFi.

Building on micro-learning apps like Duolingo, WaitSuite aims to leverage moments when a person wouldn’t otherwise be doing anything — a practice that its developers call “wait-learning.”

“With stand-alone apps, it can be inconvenient to have to separately open them up to do a learning task,” says MIT PhD student Carrie Cai, who leads the project. “WaitSuite is embedded directly into your existing tasks, so that you can easily learn without leaving what you were already doing.”

WaitSuite covers five common daily tasks: waiting for WiFi to connect, emails to push through, instant messages to be received, an elevator to come, or content on your phone to load. When using the system’s instant messaging app “WaitChatter,” users learned about four new words per day, or 57 words over just two weeks.

Ironically, Cai found that the system actually enabled users to better focus on their primary tasks, since they were less likely to check social media or otherwise leave their app.

WaitSuite was developed in collaboration with MIT Professor Rob Miller and former MIT student Anji Ren. A paper on the system will be presented at ACM’s CHI Conference on Human Factors in Computing Systems next month in Colorado.

Among WaitSuite’s apps include “WiFiLearner,” which gives users a learning prompt when it detects that their computer is seeking a WiFi connection. Meanwhile, “ElevatorLearner” automatically detects when a person is near an elevator by sensing Bluetooth iBeacons, and then sends users a vocabulary word to translate.

Though the team used WaitSuite to teach vocabulary, Cai says that it could also be used for learning things like math, medical terms, or legal jargon.

“The vast majority of people made use of multiple kinds of waiting within WaitSuite,” says Cai. “By enabling wait-learning during diverse waiting scenarios, WaitSuite gave people more opportunities to learn and practice vocabulary words.”

Still, some types of waiting were more effective than others, making the “switch time” a key factor. For example, users liked that with “ElevatorLearner,” wait time was typically 50 seconds and opening the flashcard app took 10 seconds, leaving free leftover time. For others, doing a flashcard while waiting for WiFi didn’t seem worth it if the WiFi connected quickly, but those with slow WiFi felt that doing a flashcard made waiting less frustrating.

Combat media stereotypes of Muslim women

Layla Shaikley SM ’13 began her master’s in architecture at MIT with a hunger to redevelop nations recovering from conflict. When she decided that data and logistics contributed more immediately to development than architecture did, ­Shaikley switched to the Media Lab to work with Professor Sandy ­Pentland, and became a cofounder of Wise Systems, which develops routing software that helps companies deliver goods and services.

“There’s nothing more creative than building a company,” Shaikley says. “We plan the most effective routes and optimize them in real time using driver feedback. Better logistics can dramatically reduce the number of late deliveries, increase efficiency, and save fuel.”

But Shaikley is perhaps better known for a viral video, “Muslim Hipsters: #mipsterz,” that she and friends created to combat the media stereotypes of Muslim women. It reached hundreds of thousands of viewers and received vigorous positive and negative feedback.

The video “is a really refreshing, jovial view of an underrepresented identity: young American Muslim women with alternative interests in the arts and culture,” Shaikley says. “The narrow media image is so far from the real fabric of Muslim-­American life that we all need to add our pieces to the quilt to create a more accurate image.”

Shaikley’s parents moved from Iraq to California in the 1970s, and she and her five siblings enjoyed a “quintessentially all-­American childhood,” she says. “I grew up on a skateboard, and I love to surf and snowboard.” She feels deeply grateful to her parents, who “always put our needs first,” she adds. “When we visited relatives in Iraq, we observed what life is like when people don’t have the privilege of a free society. Those experiences really shaped my understanding of the world and also my sense of responsibility to give back.”

Shaikley says the sum of her diverse life experiences has helped her as a professional with Wise Systems and as a voice for underrepresented Muslim women.

“My work at MIT under [professors] Reinhard Goethert and Sandy ­Pentland was critical to my career and understanding of data as it relates to developing urban areas,” she says. “And every piece of my disparate experiences, which included the coolest internship of my life with NASA working on robotics for Mars, has played a huge role.”