In our direct policy approach, we trained a separate classifier for each action. The input is the sensor measurements and features, and the output is whether to turn the component on or off.

The sensors that were sampled every second were active application, keyboard and mouse activity, CPU load, and network traffic. Out of these sensors we constructed various features, such as sums, decayed sums, averages, and gradients of sensor readings over different past windows.

The labels for the classification problems were generated by heuristic laws after going through the trace of sensor readings. We used several ad-hoc rules to determine the labels, such as, if turning WLAN off and packets are sent within 30 seconds, determines the action to turn WLAN off to be a mistake. This labeling scheme gives a "target" policy that is guaranteed not to annoy the user because it will never turn off components when needed in the next fixed look-ahead.

As a yardstick for a learning algorithm, we used logistic regression, k-nearest-neighbors and the C4.5 decision tree. These algorithms are simple to use and produced more or less similar results. Since these algorithms are standard, we do not describe them here. We refer the reader to [5]. Many classifiers (such as logistic regression) have some threshold function. For example, if the outcome is probabilistic between the two classes, then the threshold is the minimum probability for deciding the first class. By varying the threshold, we can make the resulting classifier more or less aggressive leading to different points on the annoyance-power-saving curve.

The second yardstick we used is timeout-based policies. The decision to turn off a component in such a policy is according to the time passed since it was last used–we turn it off if it was not used for more than some predefined threshold. We can control the level of annoyance by varying the threshold (the larger the threshold the less aggressive the timeout policy and the less annoyance we will observe).

Context-based policy learning

For context-based policy learning, we explicitly take into consideration the user context variable. The idea is to separate the data for each value of the context variable and then train a separate classifier for each data partition. We then choose the decision threshold for each classifier such that the overall power savings are maximized. As we show in our experiments, this approach performs better than naïve classifiers trained on all data.

In general, user context is not directly observable and represents the user's internal state, mood, or intentions. In our experiments we discovered that the time since the component was last active is a good feature for predicting the actions. Therefore, we defined context to be the time since the component was last active. We partitioned these durations into 30 categories, where each category represents a value for the context variable. Value 1 means in the previous time step the component was active, and value 30 means the component was idle for the last 600 steps. We chose the rest of the 28 thresholds heuristically across the 600 seconds. We observed that the longer a component is idle the more likely it will be idle (which means it should be easier to predict the action); therefore, for larger idle times we made the partition density coarser than that for shorter idle times. Empirically, the number 30 gave us reasonable performance. For smaller numbers the predictions were not as good, and for larger numbers we were over fitting.

In order to determine the thresholds for each context classifier we used an optimization algorithm. The algorithm starts by setting the least annoying thresholds for all classifiers. At each step, we increase the threshold that corresponds to the maximal power savings over annoyance increase ratio subject to a global annoyance constraint. Identifying the threshold and its new value is computationally simple because we only enumerate a single parameter and freeze the remaining ones. This optimization method proved efficient and it always converged to a local optimum. Figure 4 shows a graphical representation of our algorithm.

Figure 4: The top graph shows power savings/user annoyance curves corresponding to the 30 individual contexts. The black diamonds represent the decision points returned by the heuristic optimization method subject to the annoyance constraint of 0.1. The bottom graph compares power savings/user annoyance curves for the optimized mixture classifier (black line) and timeout policies (black line with cross markers). The black diamond denotes the global annoyance constraint for 0.1.
 

Experiments

We compare the quality APM policies with naïve classifiers and with timeout policies. The different policies were evaluated on 42 traces, which were collected for 7 users, and they represent the cumulative experience of 210 usage hours. The data are obtained from T42 laptops by using an application that we developed. We present results for standby policies only. These results generalize to the power management of the LCD, CPU, and WLAN. In order to make a fair comparison, we compare the performance of the various policies for the same annoyance level.

Figure 5: The graph shows expected power savings and their standard deviations for various classification techniques. The target annoyance level is 0.05.
click image for larger view
 

Based on Figure 5, we know that the context-based LR outperforms the baselines methods. This observation justifies the benefits of training classifiers for individual contexts, which are constructed based on our domain knowledge. An obvious question that arises is why we save more power for some users than for others. This phenomenon can be explained from the distribution of the idle times for each user. Simply, if the user spends more time in longer inactivity periods, we save more power. This demonstrates the difference between users. Different users may have a very different behavior and the APM policy has to adapt to the specific user.