More Like this

1. Deception through Half-Truths

   https://doi.org/10.1609/aaai.v34i06.6570  

   Estornell, Andrew; Das, Sanmay; Vorobeychik, Yevgeniy (June 2020, Proceedings of the AAAI Conference on Artificial Intelligence)

   Deception is a fundamental issue across a diverse array of settings, from cybersecurity, where decoys (e.g., honeypots) are an important tool, to politics that can feature politically motivated “leaks” and fake news about candidates. Typical considerations of deception view it as providing false information. However, just as important but less frequently studied is a more tacit form where information is strategically hidden or leaked. We consider the problem of how much an adversary can affect a principal's decision by “half-truths”, that is, by masking or hiding bits of information, when the principal is oblivious to the presence of the adversary. The principal's problem can be modeled as one of predicting future states of variables in a dynamic Bayes network, and we show that, while theoretically the principal's decisions can be made arbitrarily bad, the optimal attack is NP-hard to approximate, even under strong assumptions favoring the attacker. However, we also describe an important special case where the dependency of future states on past states is additive, in which we can efficiently compute an approximately optimal attack. Moreover, in networks with a linear transition function we can solve the problem optimally in polynomial time. 

   more » « less
2. Deception through Half-Truths

   Estornell, Andrew; Das, Sanmay; Vorobeychik, Yevgeniy (January 2020, Proceedings of the AAAI Conference on Artificial Intelligence)

   Deception is a fundamental issue across a diverse array of settings, from cybersecurity, where decoys (e.g., honeypots) are an important tool, to politics that can feature politically motivated "leaks" and fake news about candidates.Typical considerations of deception view it as providing false information.However, just as important but less frequently studied is a more tacit form where information is strategically hidden or leaked.We consider the problem of how much an adversary can affect a principal's decision by "half-truths", that is, by masking or hiding bits of information, when the principal is oblivious to the presence of the adversary. The principal's problem can be modeled as one of predicting future states of variables in a dynamic Bayes network, and we show that, while theoretically the principal's decisions can be made arbitrarily bad, the optimal attack is NP-hard to approximate, even under strong assumptions favoring the attacker. However, we also describe an important special case where the dependency of future states on past states is additive, in which we can efficiently compute an approximately optimal attack. Moreover, in networks with a linear transition function we can solve the problem optimally in polynomial time. 

   more » « less
3. Robust Estimation of Tree Structured Gaussian Graphical Models

   Katiyar, Ashish; Hoffmann, Jessica; Caramanis, Constantine (June 2019, Proceedings of Machine Learning Research)

   Consider jointly Gaussian random variables whose conditional independence structure is specified by a graphical model. If we observe realizations of the variables, we can compute the covariance matrix, and it is well known that the support of the inverse covariance matrix corresponds to the edges of the graphical model. Instead, suppose we only have noisy observations. If the noise at each node is independent, we can compute the sum of the covariance matrix and an unknown diagonal. The inverse of this sum is (in general) dense. We ask: can the original independence structure be recovered? We address this question for tree structured graphical models. We prove that this problem is unidentifiable, but show that this unidentifiability is limited to a small class of candidate trees. We further present additional constraints under which the problem is identifiable. Finally, we provide an O(n^3) algorithm to find this equivalence class of trees. 

   more » « less
4. Superinfection and the evolution of an initial asymptomatic stage

   https://doi.org/10.1098/rsos.202212  

   Saad-Roy, Chadi M.; Grenfell, Bryan T.; Levin, Simon A.; Pellis, Lorenzo; Stage, Helena B.; van den Driessche, P.; Wingreen, Ned S. (January 2021, Royal Society Open Science)

   null (Ed.)

   Pathogens have evolved a variety of life-history strategies. An important strategy consists of successful transmission by an infected host before the appearance of symptoms, that is, while the host is still partially or fully asymptomatic. During this initial stage of infection, it is possible for another pathogen to superinfect an already infected host and replace the previously infecting pathogen. Here, we study the effect of superinfection during the first stage of an infection on the evolutionary dynamics of the degree to which the host is asymptomatic (host latency) in that same stage. We find that superinfection can lead to major differences in evolutionary behaviour. Most strikingly, the duration of immunity following infection can significantly influence pathogen evolutionary dynamics, whereas without superinfection the outcomes are independent of host immunity. For example, changes in host immunity can drive evolutionary transitions from a fully symptomatic to a fully asymptomatic first infection stage. Additionally, if superinfection relative to susceptible infection is strong enough, evolution can lead to a unique strategy of latency that corresponds to a local fitness minimum, and is therefore invasible by nearby mutants. Thus, this strategy is a branching point, and can lead to coexistence of pathogens with different latencies. Furthermore, in this new framework with superinfection, we also find that there can exist two interior singular strategies. Overall, new evolutionary outcomes can cascade from superinfection. 

   more » « less
5. A Logic for Expressing Log-Precision Transformers

   Merrill, William; Sabharwal, Ashish (December 2023, NeurIPS 2023)

   One way to interpret the reasoning power of transformer-based language models is to describe the types of logical rules they can resolve over some input text. Recently, Chiang et al. (2023) showed that finite-precision transformers can be equivalently expressed in a generalization of first-order logic. However, finite-precision transformers are a weak transformer variant because, as we show, a single head can only attend to a constant number of tokens and, in particular, cannot represent uniform attention. Since attending broadly is a core capability for transformers, we ask whether a minimally more expressive model that can attend universally can also be characterized in logic. To this end, we analyze transformers whose forward pass is computed in logn precision on contexts of length n. We prove that any log-precision transformer can be equivalently expressed as a first-order logic sentence that, in addition to standard universal and existential quantifiers, may also contain majority-vote quantifiers. This is the tightest known upper bound and first logical characterization of log-precision transformers. 

   more » « less