OpenRaiser/Intern-Atlas huggingface dataset:
Exhaustivity and anti-exhaustivity in the RSA framework: Testing the effect of prior beliefs
Venue: arXiv cs.CL 2022
Year: 2022

During communication, the interpretation of utterances is sensitive to a listener's probabilistic prior beliefs, something which is captured by one currently influential model of pragmatics, the Rational Speech Act (RSA) framework. In this paper we focus on cases when this sensitivity to priors leads to counterintuitive predictions of the framework. Our domain of interest is exhaustivity effects, whereby a sentence such as "Mary came" is understood to mean that only Mary came. We show that in the baseline RSA model, under certain conditions, anti-exhaustive readings are predicted (e.g., "Mary came" would be used to convey that both Mary and Peter came). The specific question we ask is the following: should exhaustive interpretations be derived as purely pragmatic inferences (as in the classical Gricean view, endorsed in the baseline RSA model), or should they rather be generated by an encapsulated semantic mechanism (as argued in some of the recent formal literature)? To answer this question, we provide a detailed theoretical analysis of different RSA models and evaluate them against data obtained in a new study which tested the effects of prior beliefs on both production and comprehension, improving on previous empirical work. We found no anti-exhaustivity effects, but observed that message choice is sensitive to priors, as predicted by the RSA framework overall. The best models turn out to be those which include an encapsulated exhaustivity mechanism (as other studies concluded on the basis of very different data). We conclude that, on the one hand, in the division of labor between semantics and pragmatics, semantics plays a larger role than is often thought, but, on the other hand, the tradeoff between informativity and cost which characterizes all RSA models does play a central role for genuine pragmatic effects.
Box Supervised Video Segmentation Proposal Network
Venue: arXiv cs.CV 2022
Year: 2022

Video Object Segmentation (VOS) has been targeted by various fully-supervised and self-supervised approaches. While fully-supervised methods demonstrate excellent results, self-supervised ones, which do not use pixel-level ground truth, attract much attention. However, self-supervised approaches pose a significant performance gap. Box-level annotations provide a balanced compromise between labeling effort and result quality for image segmentation but have not been exploited for the video domain. In this work, we propose a box-supervised video object segmentation proposal network, which takes advantage of intrinsic video properties. Our method incorporates object motion in the following way: first, motion is computed using a bidirectional temporal difference and a novel bounding box-guided motion compensation. Second, we introduce a novel motion-aware affinity loss that encourages the network to predict positive pixel pairs if they share similar motion and color. The proposed method outperforms the state-of-the-art self-supervised benchmark by 16.4% and 6.9% $\mathcal{J}$ &$\mathcal{F}$ score and the majority of fully supervised methods on the DAVIS and Youtube-VOS dataset without imposing network architectural specifications. We provide extensive tests and ablations on the datasets, demonstrating the robustness of our method.
Analysis of Neural Fragility: Bounding the Norm of a Rank-One Perturbation Matrix
Venue: arXiv cs.LG 2022
Year: 2022

Over 15 million epilepsy patients worldwide do not respond to drugs and require surgical treatment. Successful surgical treatment requires complete removal, or disconnection of the epileptogenic zone (EZ), but without a prospective biomarker of the EZ, surgical success rates vary between 30%-70%. Neural fragility is a model recently proposed to localize the EZ. Neural fragility is computed as the l2 norm of a structured rank-one perturbation of an estimated linear dynamical system. However, an analysis of its numerical properties have not been explored. We show that neural fragility is a well-defined model given a good estimator of the linear dynamical system from data. Specifically, we provide bounds on neural fragility as a function of the underlying linear system and noise.
Orthogonalising gradients to speed up neural network optimisation
Venue: arXiv cs.LG 2022
Year: 2022

The optimisation of neural networks can be sped up by orthogonalising the gradients before the optimisation step, ensuring the diversification of the learned representations. We orthogonalise the gradients of the layer's components/filters with respect to each other to separate out the intermediate representations. Our method of orthogonalisation allows the weights to be used more flexibly, in contrast to restricting the weights to an orthogonalised sub-space. We tested this method on ImageNet and CIFAR-10 resulting in a large decrease in learning time, and also obtain a speed-up on the semi-supervised learning BarlowTwins. We obtain similar accuracy to SGD without fine-tuning and better accuracy for naïvely chosen hyper-parameters.
Automatic Generation of Individual Fuzzy Cognitive Maps from Longitudinal Data
Venue: arXiv cs.AI 2022
Year: 2022

Fuzzy Cognitive Maps (FCMs) are computational models that represent how factors (nodes) change over discrete interactions based on causal impacts (weighted directed edges) from other factors. This approach has traditionally been used as an aggregate, similarly to System Dynamics, to depict the functioning of a system. There has been a growing interest in taking this aggregate approach at the individual-level, for example by equipping each agent of an Agent-Based Model with its own FCM to express its behavior. Although frameworks and studies have already taken this approach, an ongoing limitation has been the difficulty of creating as many FCMs as there are individuals. Indeed, current studies have been able to create agents whose traits are different, but whose decision-making modules are often identical, thus limiting the behavioral heterogeneity of the simulated population. In this paper, we address this limitation by using Genetic Algorithms to create one FCM for each agent, thus providing the means to automatically create a virtual population with heterogeneous behaviors. Our algorithm builds on prior work from Stach and colleagues by introducing additional constraints into the process and applying it over longitudinal, individual-level data. A case study from a real-world intervention on nutrition confirms that our approach can generate heterogeneous agents that closely follow the trajectories of their real-world human counterparts. Future works include technical improvements such as lowering the computational time of the approach, or case studies in computational intelligence that use our virtual populations to test new behavior change interventions.
A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Search
Venue: arXiv cs.AI 2022
Year: 2022

Monte-Carlo Tree Search (MCTS) is a class of methods for solving complex decision-making problems through the synergy of Monte-Carlo planning and Reinforcement Learning (RL). The highly combinatorial nature of the problems commonly addressed by MCTS requires the use of efficient exploration strategies for navigating the planning tree and quickly convergent value backup methods. These crucial problems are particularly evident in recent advances that combine MCTS with deep neural networks for function approximation. In this work, we propose two methods for improving the convergence rate and exploration based on a newly introduced backup operator and entropy regularization. We provide strong theoretical guarantees to bound convergence rate, approximation error, and regret of our methods. Moreover, we introduce a mathematical framework based on the use of the $α$-divergence for backup and exploration in MCTS. We show that this theoretical formulation unifies different approaches, including our newly introduced ones, under the same mathematical framework, allowing to obtain different methods by simply changing the value of $α$. In practice, our unified perspective offers a flexible way to balance between exploration and exploitation by tuning the single $α$ parameter according to the problem at hand. We validate our methods through a rigorous empirical study from basic toy problems to the complex Atari games, and including both MDP and POMDP problems.
Discriminability-enforcing loss to improve representation learning
Venue: arXiv cs.CV 2022
Year: 2022

During the training process, deep neural networks implicitly learn to represent the input data samples through a hierarchy of features, where the size of the hierarchy is determined by the number of layers. In this paper, we focus on enforcing the discriminative power of the high-level representations, that are typically learned by the deeper layers (closer to the output). To this end, we introduce a new loss term inspired by the Gini impurity, which is aimed at minimizing the entropy (increasing the discriminative power) of individual high-level features with respect to the class labels. Although our Gini loss induces highly-discriminative features, it does not ensure that the distribution of the high-level features matches the distribution of the classes. As such, we introduce another loss term to minimize the Kullback-Leibler divergence between the two distributions. We conduct experiments on two image classification data sets (CIFAR-100 and Caltech 101), considering multiple neural architectures ranging from convolutional networks (ResNet-17, ResNet-18, ResNet-50) to transformers (CvT). Our empirical results show that integrating our novel loss terms into the training objective consistently outperforms the models trained with cross-entropy alone, without increasing the inference time at all.
Price Cycles in Ridesharing Platforms
Venue: arXiv cs.GT 2022
Year: 2022

In ridesharing platforms such as Uber and Lyft, it is observed that drivers sometimes collaboratively go offline when the price is low, and then return after the price has risen due to the perceived lack of supply. This collective strategy leads to cyclic fluctuations in prices and available drivers, resulting in poor reliability and social welfare. We study a continuous time, non-atomic model and prove that such online/offline strategies may form a Nash equilibrium among drivers, but lead to a lower total driver payoff if the market is sufficiently dense. Further, we show how to set price floors that effectively mitigate the emergence and impact of price cycles.
Computing with Modular Robots
Venue: arXiv cs.RO 2022
Year: 2022

Propagating patterns are used to transfer and process information in chemical and physical prototypes of unconventional computing devices. Logical values are represented by fronts of traveling diffusive, trigger or phase waves. We apply this concept of pattern based computation to develop experimental prototypes of computing circuits implemented in small modular robots. In the experimental prototypes the modular robots Cubelets are concatenated into channels and junction. The structures developed by Cubelets propagate signals in parallel and asynchronously. The approach is illustrated with a working circuit of a one-bit full adder. Complementarily a formalization of these constructions are developed across Sleptsov nets. Finally, a perspective to swarm dynamics is discussed.
Efficient Distributed Computations in Anonymous Dynamic Congested Systems with Opportunistic Connectivity
Venue: arXiv cs.DC 2022
Year: 2022

In this work we address the question of efficiency of distributed computing in anonymous, congested and highly dynamic and not-always-connected networks/systems. More precisely, the system consists of an unknown number of anonymous nodes with congestion on links and local computation. Links can change arbitrarily from round to round, with only limitation that the union of any T consecutive networks must form a temporarily connected (multi-)graph on all nodes (knowledge of T is the only information the nodes require, otherwise the communication would not be feasible). Nodes do not have any IDs, only some number l of them have a bit distinguishing them from nodes without such a bit. In each round a node can send and receive messages from its current neighbors. Links and nodes are congested, in the sense that the length of messages and local cache memory for local computation is (asymptotically) logarithmic. All-to-all communication is a fundamental principle in distributed computing - it assumes that each node has an input message to be delivered to all other nodes. Without loss of generality, the size of each input message is logarithmic to fit in the link and node congestion assumption; otherwise, they could be split in logarithmic batches and considered one-by-one. Because of anonymity, each node needs to receive only a set of all input messages, each accompanied by a number of initiating nodes (message multiplicity). We prove that this task can be done in time polynomial in the (initially unknown) number of nodes n and in the lower bound on the isoperimetric numbers of dynamically evolving graphs. This allows to efficiently emulate a popular Congested Clique model on top of Anonymous Dynamic Congested Systems (ADCS) with Opportunistic Connectivity, even if the number of nodes may arbitrarily change in the beginning of emulation.
Longest (Sub-)Periodic Subsequence
Venue: arXiv cs.DS 2022
Year: 2022

We present an algorithm computing the longest periodic subsequence of a string of length $n$ in $O(n^7)$ time with $O(n^4)$ words of space. We obtain improvements when restricting the exponents or extending the search allowing the reported subsequence to be subperiodic down to $O(n^3)$ time and $O(n^2)$ words of space.
Impact of Pretraining Term Frequencies on Few-Shot Reasoning
Venue: arXiv cs.CL 2022
Year: 2022

Pretrained Language Models (LMs) have demonstrated ability to perform numerical reasoning by extrapolating from a few examples in few-shot settings. However, the extent to which this extrapolation relies on robust reasoning is unclear. In this paper, we investigate how well these models reason with terms that are less frequent in the pretraining data. In particular, we examine the correlations between the model performance on test instances and the frequency of terms from those instances in the pretraining data. We measure the strength of this correlation for a number of GPT-based language models (pretrained on the Pile dataset) on various numerical deduction tasks (e.g., arithmetic and unit conversion). Our results consistently demonstrate that models are more accurate on instances whose terms are more prevalent, in some cases above $70\%$ (absolute) more accurate on the top 10\% frequent terms in comparison to the bottom 10\%. Overall, although LMs exhibit strong performance at few-shot numerical reasoning tasks, our results raise the question of how much models actually generalize beyond pretraining data, and we encourage researchers to take the pretraining data into account when interpreting evaluation results.
Explaining Reject Options of Learning Vector Quantization Classifiers
Venue: arXiv cs.LG 2022
Year: 2022

While machine learning models are usually assumed to always output a prediction, there also exist extensions in the form of reject options which allow the model to reject inputs where only a prediction with an unacceptably low certainty would be possible. With the ongoing rise of eXplainable AI, a lot of methods for explaining model predictions have been developed. However, understanding why a given input was rejected, instead of being classified by the model, is also of interest. Surprisingly, explanations of rejects have not been considered so far. We propose to use counterfactual explanations for explaining rejects and investigate how to efficiently compute counterfactual explanations of different reject options for an important class of models, namely prototype-based classifiers such as learning vector quantization models.
Learning Disentangled Behaviour Patterns for Wearable-based Human Activity Recognition
Venue: arXiv cs.LG 2022
Year: 2022

In wearable-based human activity recognition (HAR) research, one of the major challenges is the large intra-class variability problem. The collected activity signal is often, if not always, coupled with noises or bias caused by personal, environmental, or other factors, making it difficult to learn effective features for HAR tasks, especially when with inadequate data. To address this issue, in this work, we proposed a Behaviour Pattern Disentanglement (BPD) framework, which can disentangle the behavior patterns from the irrelevant noises such as personal styles or environmental noises, etc. Based on a disentanglement network, we designed several loss functions and used an adversarial training strategy for optimization, which can disentangle activity signals from the irrelevant noises with the least dependency (between them) in the feature space. Our BPD framework is flexible, and it can be used on top of existing deep learning (DL) approaches for feature refinement. Extensive experiments were conducted on four public HAR datasets, and the promising results of our proposed BPD scheme suggest its flexibility and effectiveness. This is an open-source project, and the code can be found at http://github.com/Jie-su/BPD
Analysis of a blockchain protocol based on LDPC codes
Venue: arXiv cs.CR 2022
Year: 2022

In a blockchain Data Availability Attack (DAA), a malicious node publishes a block header but withholds part of the block, which contains invalid transactions. Honest full nodes, which can download and store the full blockchain, are aware that some data are not available but they have no formal way to prove it to light nodes, i.e., nodes that have limited resources and are not able to access the whole blockchain data. A common solution to counter these attacks exploits linear error correcting codes to encode the block content. A recent protocol, called SPAR, employs coded Merkle trees and low-density parity-check codes to counter DAAs. In this paper, we show that the protocol is less secure than claimed, owing to a redefinition of the adversarial success probability. As a consequence we show that, for some realistic choices of the parameters, the total amount of data downloaded by light nodes is larger than that obtainable with competitor solutions.
Worldwide Gender Differences in Public Code Contributions
Venue: arXiv cs.SE 2022
Year: 2022

Gender imbalance is a well-known phenomenon observed throughout sciences which is particularly severe in software development and Free/Open Source Software communities. Little is know yet about the geography of this phenomenon in particular when considering large scales for both its time and space dimensions. We contribute to fill this gap with a longitudinal study of the population of contributors to publicly available software source code. We analyze the development history of 160 million software projects for a total of 2.2 billion commits contributed by 43 million distinct authors over a period of 50 years. We classify author names by gender using name frequencies and author geographical locations using heuristics based on email addresses and time zones. We study the evolution over time of contributions to public code by gender and by world region. For the world overall, we confirm previous findings about the low but steadily increasing ratio of contributions by female authors. When breaking down by world regions we find that the long-term growth of female participation is a worldwide phenomenon. We also observe a decrease in the ratio of female participation during the COVID-19 pandemic, suggesting that women's ability to contribute to public code has been more hindered than that of men.
Roomsemble: Progressive web application for intuitive property search
Venue: arXiv cs.IR 2022
Year: 2022

A successful real estate search process involves locating a property that meets a user's search criteria subject to an allocated budget and time constraints. Many studies have investigated modeling housing prices over time. However, little is known about how a user's tastes influence their real estate search and purchase decisions. It is unknown what house a user would choose taking into account an individual's personal tastes, behaviors, and constraints, and, therefore, creating an algorithm that finds the perfect match. In this paper, we investigate the first step in understanding a user's tastes by building a system to capture personal preferences. We concentrated our research on real estate photos, being inspired by house aesthetics, which often motivates prospective buyers into considering a property as a candidate for purchase. We designed a system that takes a user-provided photo representing that person's personal taste and recommends properties similar to the photo available on the market. The user can additionally filter the recommendations by budget and location when conducting a property search. The paper describes the application's overall layout including frontend design and backend processes for locating a desired property. The proposed model, which serves as the application's core, was tested with 25 users, and the study's findings, as well as some key conclusions, are detailed in this paper.
Using Social Media Images for Building Function Classification
Venue: arXiv cs.CV 2022
Year: 2022

Urban land use on a building instance level is crucial geo-information for many applications, yet difficult to obtain. An intuitive approach to close this gap is predicting building functions from ground level imagery. Social media image platforms contain billions of images, with a large variety of motifs including but not limited to street perspectives. To cope with this issue this study proposes a filtering pipeline to yield high quality, ground level imagery from large social media image datasets. The pipeline ensures that all resulting images have full and valid geotags with a compass direction to relate image content and spatial objects from maps. We analyze our method on a culturally diverse social media dataset from Flickr with more than 28 million images from 42 cities around the world. The obtained dataset is then evaluated in a context of 3-classes building function classification task. The three building classes that are considered in this study are: commercial, residential, and other. Fine-tuned state-of-the-art architectures yield F1-scores of up to 0.51 on the filtered images. Our analysis shows that the performance is highly limited by the quality of the labels obtained from OpenStreetMap, as the metrics increase by 0.2 if only human validated labels are considered. Therefore, we consider these labels to be weak and publish the resulting images from our pipeline together with the buildings they are showing as a weakly labeled dataset.
An algorithmic solution to the Blotto game using multi-marginal couplings
Venue: arXiv cs.GT 2022
Year: 2022

We describe an efficient algorithm to compute solutions for the general two-player Blotto game on n battlefields with heterogeneous values. While explicit constructions for such solutions have been limited to specific, largely symmetric or homogeneous, setups, this algorithmic resolution covers the most general situation to date: value-asymmetric game with asymmetric budget. The proposed algorithm rests on recent theoretical advances regarding Sinkhorn iterations for matrix and tensor scaling. An important case which had been out of reach of previous attempts is that of heterogeneous but symmetric battlefield values with asymmetric budget. In this case, the Blotto game is constant-sum so optimal solutions exist, and our algorithm samples from an $\varepsilon$-optimal solution in time $\tilde{\mathcal{O}}(n^2 + \varepsilon^{-4})$, independently of budgets and battlefield values. In the case of asymmetric values where optimal solutions need not exist but Nash equilibria do, our algorithm samples from an $\varepsilon$-Nash equilibrium with similar complexity but where implicit constants depend on various parameters of the game such as battlefield values.