More Like this

1. Information Acquisition Under Resource Limitations in a Noisy Environment

   Soloviev, M.; Halpern, J.Y. (February 2018, Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18))

   We introduce a theoretical model of information acquisition under resource limitations in a noisy environment. An agent must guess the truth value of a given Boolean formula φ after performing a bounded number of noisy tests of the truth values of variables in the formula. We observe that, in general, the problem of finding an optimal testing strategy for φ is hard, but we suggest a useful heuristic. The techniques we use also give insight into two apparently unrelated, but well-studied problems: (1) rational inattention (the optimal strategy may involve hardly ever testing variables that are clearly relevant to φ) and (2) what makes a formula hard to learn/remember 

   more » « less
2. Constraint Optimization over Semirings

   A. Pavan; Kuldeep S Meel; N. V. Vinodchandranl Arnab Bhattacharyya (February 2023, Proceedings of the AAAI Conference on Artificial Intelligence)

   Williams Brian; Chen Yiling; Neville Jennifer (Ed.)

   Interpretations of logical formulas over semirings (other than the Boolean semiring) have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Examples of such semirings include Viterbi semiring, min-max or access control semiring, tropical semiring, and fuzzy semiring. The present work investigates the complexity of constraint optimization problems over semirings. The generic optimization problem we study is the following: Given a propositional formula $$\varphi$$ over $$n$$ variable and a semiring $$(K,+,\cdot,0,1)$$, find the maximum value over all possible interpretations of $$\varphi$$ over $$K$$. This can be seen as a generalization of the well-known satisfiability problem (a propositional formula is satisfiable if and only if the maximum value over all interpretations/assignments over the Boolean semiring is 1). A related problem is to find an interpretation that achieves the maximum value. In this work, we first focus on these optimization problems over the Viterbi semiring, which we call \optrustval\ and \optrust. We first show that for general propositional formulas in negation normal form, \optrustval\ and {\optrust} are in $${\mathrm{FP}}^{\mathrm{NP}}$$. We then investigate {\optrust} when the input formula $$\varphi$$ is represented in the conjunctive normal form. For CNF formulae, we first derive an upper bound on the value of {\optrust} as a function of the number of maximum satisfiable clauses. In particular, we show that if $$r$$ is the maximum number of satisfiable clauses in a CNF formula with $$m$$ clauses, then its $$\optrust$$ value is at most $$1/4^{m-r}$$. Building on this we establish that {\optrust} for CNF formulae is hard for the complexity class $${\mathrm{FP}}^{\mathrm{NP}[\log]}$$. We also design polynomial-time approximation algorithms and establish an inapproximability for {\optrustval}. We establish similar complexity results for these optimization problems over other semirings including tropical, fuzzy, and access control semirings. 

   more » « less
3. Informative and non-informative decomposition of turbulent flow fields

   https://doi.org/10.1017/jfm.2024.1007  

   Arranz, Gonzalo; Lozano-Durán, Adrián (December 2024, Journal of Fluid Mechanics)

   Not all the information in a turbulent field is relevant for understanding particular regions or variables in the flow. Here, we present a method for decomposing a source field into its informative$$\boldsymbol {\varPhi }_{I}(\boldsymbol {x},t)$$and residual$$\boldsymbol {\varPhi }_{R}(\boldsymbol {x},t)$$components relative to another target field. The method is referred to as informative and non-informative decomposition (IND). All the necessary information for physical understanding, reduced-order modelling and control of the target variable is contained in$$\boldsymbol {\varPhi }_{I}(\boldsymbol {x},t)$$, whereas$$\boldsymbol {\varPhi }_{R}(\boldsymbol {x},t)$$offers no substantial utility in these contexts. The decomposition is formulated as an optimisation problem that seeks to maximise the time-lagged mutual information of the informative component with the target variable while minimising the mutual information with the residual component. The method is applied to extract the informative and residual components of the velocity field in a turbulent channel flow, using the wall shear stress as the target variable. We demonstrate the utility of IND in three scenarios: (i) physical insight into the effect of the velocity fluctuations on the wall shear stress; (ii) prediction of the wall shear stress using velocities far from the wall; and (iii) development of control strategies for drag reduction in a turbulent channel flow using opposition control. In case (i), IND reveals that the informative velocity related to wall shear stress consists of wall-attached high- and low-velocity streaks, collocated with regions of vertical motions and weak spanwise velocity. This informative structure is embedded within a larger-scale streak–roll structure of residual velocity, which bears no information about the wall shear stress. In case (ii), the best-performing model for predicting wall shear stress is a convolutional neural network that uses the informative component of the velocity as input, while the residual velocity component provides no predictive capabilities. Finally, in case (iii), we demonstrate that the informative component of the wall-normal velocity is closely linked to the observability of the target variable and holds the essential information needed to develop successful control strategies. 

   more » « less
4. Adaptive Group Testing with Mismatched Models

   https://doi.org/10.1109/ICASSP43922.2022.9747665  

   Fan, Mingzhou; Yoon, Byung-Jun; Alexander, Francis J.; Dougherty, Edward R.; Qian, Xiaoning (May 2022, ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   Accurate detection of infected individuals is one of the critical steps in stopping any pandemic. When the underlying infection rate of the disease is low, testing people in groups, instead of testing each individual in the population, can be more efficient. In this work, we consider noisy adaptive group testing design with specific test sensitivity and specificity that select the optimal group given previous test results based on pre-selected utility function. As in prior studies on group testing, we model this problem as a sequential Bayesian Optimal Experimental Design (BOED) to adaptively design the groups for each test. We analyze the required number of group tests when using the updated posterior on the infection status and the corresponding Mutual Information (MI) as our utility function for selecting new groups. More importantly, we study how the potential bias on the ground-truth noise of group tests may affect the group testing sample complexity. 

   more » « less
5. Surrogate Scoring Rules

   https://doi.org/10.1145/3565559  

   Liu, Yang; Wang, Juntao; Chen, Yiling (October 2022, ACM Transactions on Economics and Computation)

   Strictly proper scoring rules (SPSR) are incentive compatible for eliciting information about random variables from strategic agents when the principal can reward agents after the realization of the random variables. They also quantify the quality of elicited information, with more accurate predictions receiving higher scores in expectation. In this paper, we extend such scoring rules to settings where a principal elicits private probabilistic beliefs but only has access to agents’ reports. We name our solution Surrogate Scoring Rules (SSR). SSR is built on a bias correction step and an error rate estimation procedure for a reference answer defined using agents’ reports. We show that, with a little information about the prior distribution of the random variables, SSR in a multi-task setting recover SPSR in expectation, as if having access to the ground truth. Therefore, a salient feature of SSR is that they quantify the quality of information despite the lack of ground truth, just as SPSR do for the setting with ground truth. As a by-product, SSR induce dominant uniform strategy truthfulness in reporting. Our method is verified both theoretically and empirically using data collected from real human forecasters. 

   more » « less