More Like this

1. Improving measurements of similarity judgments with machine-learning algorithms

   https://doi.org/10.1007/s42001-020-00098-1  

   Stevens, Jeffrey R.; Polzkill Saltzman, Alexis; Rasmussen, Tanner; Soh, Leen-Kiat (January 2021, Journal of Computational Social Science)

   null (Ed.)

   Intertemporal choices involve assessing options with different reward amounts available at different time delays. The similarity approach to intertemporal choice focuses on judging how similar amounts and delays are. Yet we do not fully understand the cognitive process of how these judgments are made. Here, we use machine-learning algorithms to predict similarity judgments to (1) investigate which algorithms best predict these judgments, (2) assess which predictors are most useful in predicting participants’ judgments, and (3) determine the minimum number of judgments required to accurately predict future judgments. We applied eight algorithms to similarity judgments for reward amount and time delay made by participants in two data sets. We found that neural network, random forest, and support vector machine algorithms generated the highest out-of-sample accuracy. Though neural networks and support vector machines offer little clarity in terms of a possible process for making similarity judgments, random forest algorithms generate decision trees that can mimic the cognitive computations of human judgment making. We also found that the numerical difference between amount values or delay values was the most important predictor of these judgments, replicating previous work. Finally, the best performing algorithms such as random forest can make highly accurate predictions of judgments with relatively small sample sizes (~ 15), which will help minimize the numbers of judgments required to extrapolate to new value pairs. In summary, machine-learning algorithms provide both theoretical improvements to our understanding of the cognitive computations involved in similarity judgments and intertemporal choices as well as practical improvements in designing better ways of collecting data. 

   more » « less
2. Learning-augmented Online Minimization of Age of Information and Transmission Costs

   Liu, Z; Zhang, K; Li, B; Sun, Y; Hou, Y; Ji, B (May 2024, IEEE)

   We consider a discrete-time system where a resource-constrained source (e.g., a small sensor) transmits its time-sensitive data to a destination over a time-varying wireless channel. Each transmission incurs a fixed transmission cost (e.g., energy cost), and no transmission results in a staleness cost represented by the Age-of-Information. The source must balance the tradeoff between transmission and staleness costs. To address this challenge, we develop a robust online algorithm to minimize the sum of transmission and staleness costs, ensuring a worst-case performance guarantee. While online algorithms are robust, they are usually overly conservative and may have a poor average performance in typical scenarios. In contrast, by leveraging historical data and prediction models, machine learning (ML) algorithms perform well in average cases. However, they typically lack worst-case performance guarantees. To achieve the best of both worlds, we design a learning-augmented online algorithm that exhibits two desired properties: (i) consistency: closely approximating the optimal offline algorithm when the ML prediction is accurate and trusted; (ii) robustness: ensuring worst case performance guarantee even ML predictions are inaccurate. Finally, we perform extensive simulations to show that our online algorithm performs well empirically and that our learning augmented algorithm achieves both consistency and robustness. 

   more » « less
3. Energy-Efficient Scheduling with Predictions

   Balkanski, Eric; Perivier, Noemie; Stein, Clifford; Wei, Hao-Ting (December 2023, 37th Conference on Neural Information Processing Systems)

   An important goal of modern scheduling systems is to efficiently manage power usage. In energy-efficient scheduling, the operating system controls the speed at which a machine is processing jobs with the dual objective of minimizing energy consumption and optimizing the quality of service cost of the resulting schedule. Since machine-learned predictions about future requests can often be learned from historical data, a recent line of work on learning-augmented algorithms aims to achieve improved performance guarantees by leveraging predictions. In particular, for energy-efficient scheduling, Bamas et. al. [NeurIPS '20] and Antoniadis et. al. [SWAT '22] designed algorithms with predictions for the energy minimization with deadlines problem and achieved an improved competitive ratio when the prediction error is small while also maintaining worst-case bounds even when the prediction error is arbitrarily large. In this paper, we consider a general setting for energy-efficient scheduling and provide a flexible learning-augmented algorithmic framework that takes as input an offline and an online algorithm for the desired energy-efficient scheduling problem. We show that, when the prediction error is small, this framework gives improved competitive ratios for many different energy-efficient scheduling problems, including energy minimization with deadlines, while also maintaining a bounded competitive ratio regardless of the prediction error. Finally, we empirically demonstrate that this framework achieves an improved performance on real and synthetic datasets. 

   more » « less
4. Machine truth serum: a surprisingly popular approach to improving ensemble methods

   https://doi.org/10.1007/s10994-022-06183-y  

   Luo, Tianyi; Liu, Yang (January 2022, Machine Learning)

   Wisdom of the crowd (Surowiecki, 2005a) disclosed a striking fact that the majority voting answer from a crowd is usually more accurate than a few individual experts. The same story is observed in machine learning - ensemble methods (Dietterich, 2000) leverage this idea to exploit multiple machine learning algorithms in various settings e.g., supervised learning and semi-supervised learning to achieve better performance by aggregating the predictions of different algorithms than that obtained from any constituent algorithm alone. Nonetheless, the existing aggregating rule would fail when the majority answer of all the constituent algorithms is more likely to be wrong. In this paper, we extend the idea proposed in Bayesian Truth Serum (Prelec, 2004) that “a surprisingly more popular answer is more likely to be the true answer instead of the majority one” to supervised classification further improved by ensemble final predictions method and semi-supervised classification (e.g., MixMatch (Berthelot et al., 2019)) enhanced by ensemble data augmentations method. The challenge for us is to define or detect when an answer should be considered as being “surprising”. We present two machine learning aided methods which can reveal the truth when the minority instead of majority has the true answer on both settings of supervised and semi-supervised classification problems. We name our proposed method the Machine Truth Serum. Our experiments on a set of classification tasks (image, text, etc.) show that the classification performance can be further improved by applying Machine Truth Serum in the ensemble final predictions step (supervised) and in the ensemble data augmentations step (semi-supervised). 

   more » « less
5. A Unifying Perspective on Multi-Calibration: Unleashing Game Dynamics for Multi-Objective Learning*

   Nika Haghtalab; Michael I. Jordan; Eric Zhao (February 2023, arXivorg)

   We provide a unifying framework for the design and analysis of multi-calibrated and moment- multi-calibrated predictors. Placing the multi-calibration problem in the general setting of multiobjective learning—where learning guarantees must hold simultaneously over a set of distribu- tions and loss functions—we exploit connections to game dynamics to obtain state-of-the-art guarantees for a diverse set of multi-calibration learning problems. In addition to shedding light on existing multi-calibration guarantees, and greatly simplifying their analysis, our ap- proach yields a 1/ε2 improvement in the number of oracle calls compared to the state-of-the-art algorithm of Jung et al. [19] for learning deterministic moment-calibrated predictors and an exponential improvement in k compared to the state-of-the-art algorithm of Gopalan et al. [14] for learning a k-class multi-calibrated predictor. Beyond multi-calibration, we use these game dynamics to address existing and emerging considerations in the study of group fairness and multi-distribution learning. 

   more » « less