[ad_1]
Researchers often use simulations when developing new algorithms because testing ideas in the real world can be both expensive and risky. But because it’s impossible to capture all the details of a complex system in a simulation, they typically collect a small amount of real data that they repeat while simulating the components they want to study.
Known as trace-driven simulation (small pieces of real data are called traces), this method sometimes produces biased results. This means that researchers may unknowingly choose an algorithm that is not the best they have evaluated and that performs worse on real data than the simulation predicted.
MIT researchers have developed a new method that eliminates this source of bias in trace-based simulations. By enabling unbiased trace-oriented simulations, the new technique can help researchers design better algorithms for a variety of applications, including improving video quality on the Internet and increasing the performance of data processing systems.
The researchers’ machine learning algorithm relies on the principles of causality to understand how the data traces were affected by the system’s behavior. This way, they can replicate the correct, unbiased version of the trace during the simulation.
Compared to a previously developed trace-based simulator, the researchers’ simulation method correctly predicted which newly developed algorithm would be the best for video streaming – meaning the one that results in less rebuffering and higher visual quality. Existing simulators that don’t take bias into account pointed the researchers toward a worse algorithm.
“Data is not the only thing that matters. The history of how data is generated and collected is also important. If you want to answer a counterfactual question, you need to know the underlying story of the data generation so you can only intervene in the things you really want to simulate,” says Arash Nasr-Esfahan, a graduate student in Electrical Engineering and Computer Science (EECS). and co-lead author of a paper on this new technique.
He is joined on the paper by co-lead authors and EECS graduate students Abdullah Alomar and Pouya Hamadanian; recent graduate Anish Agarwal PhD ’21; and senior authors Mohammad Alizadeh, associate professor of electrical engineering and computer science; and Devavrat Shah, the Andrew and Erna Viterbi Professor at EECS and a member of the Institute for Data, Systems, and Society and the Information and Decision Systems Laboratory. The research was recently presented at the USENIX Symposium on Design and Implementation of Networked Systems.
specific simulations
MIT researchers studied trace-based simulation in the context of video streaming applications.
In video streaming, an adaptive bitrate algorithm continuously decides the video quality, or bitrate, to transmit to the device based on real-time user bandwidth data. To test how different adaptive bitrate algorithms affect network performance, researchers can collect real data from users during video streaming for a trace-oriented simulation.
They use this trace to simulate what would happen to network performance if the platform used a different adaptive bitrate algorithm under the same underlying conditions.
Researchers have traditionally assumed that trace data are exogenous, meaning that they are not affected by factors that change during the simulation. They assumed that during the time they were collecting network performance data, the choices made by the bitrate adaptation algorithm would not affect that data.
But this is often a false assumption that leads to biases about the behavior of new algorithms that make simulations inaccurate, Alizadeh explains.
“We have recognized, and others have recognized, that this way of simulating can lead to errors. But I don’t think people realize how important those mistakes can be,” he says.
To develop a solution, Alizadeh and his colleagues framed the issue as a causal inference problem. To collect unbiased traces, we need to understand the various factors that affect the observed data. Some causes are internal to the system, while others are influenced by actions taken.
In the video streaming example, the network performance is is affected by the choice of bitrate adaptation algorithm—but it is also affected by intrinsics such as network capacity.
“Our task is to distinguish between these two effects, to try to understand what aspects of the behavior we see are intrinsic to the system, and how much of what we observe is based on the actions taken.” If we can separate these two effects, then we can do unbiased simulations,” he says.
Learning from data
But researchers often cannot directly observe intrinsic properties. That’s where a new tool called CausalSim comes in. An algorithm can learn the basic characteristics of a system using only trace data.
CausalSim takes trace data collected through a randomized control trial and estimates the underlying functions that represent that data. The model tells the researchers, under the exact same underlying conditions that the user experienced, how the new algorithm would change the outcome.
Using a typical trace-oriented simulator, biases may cause the researcher to choose a worse algorithm, even though the simulation indicates it should be better. CausalSim helps researchers select the best algorithm that has been tested.
MIT researchers observed this in practice. When they used CausalSim to develop an improved bitrate adaptation algorithm, it chose a new option that had a pause rate that was nearly 1.4 times lower than the well-received competing algorithm, while achieving the same video quality. The pause rate is the amount of time the user spent rebuffering the video.
In contrast, a trace-oriented simulator designed by experts predicted the opposite. He indicated that this new option should result in a suspension rate that was almost 1.3 times higher. The researchers tested the algorithm on real-world video streaming and confirmed that CausalSim was correct.
“The gain we were getting in the new variant was very close to CausalSim’s prediction, while the expert simulator was way off. This is really exciting because this expertly developed simulator has been used in research for the last decade. If CausalSim can be so clearly better than this, who knows what we can do with it?” says Hamadanian.
During the 10-month experiment, CausalSim continuously improved the accuracy of the simulation, resulting in algorithms that made about half as many errors as those developed using baseline methods.
In the future, researchers would like to use CausalSim in situations where randomized control trial data are not available or where it is particularly difficult to reconstruct the causal dynamics of the system. They also want to explore how to design and monitor systems to make them more amenable to causal analysis.
[ad_2]
Source link
