OpenRaiser/Intern-Atlas huggingface dataset:
Fair Division of Goods in the Shadow of Market Values
Venue: arXiv cs.GT 2022
Year: 2022

Inheritances, divorces or liquidations of companies require common assets to be divided among the entitled parties. Legal methods usually consider the market value of goods, while fair division theory takes into account the parties' preferences expressed as utilities. I combine the two practices to define a procedure that optimally allocates divisible goods with market values to people with easily elicited preferences. Imposing exact equality in the bundles' monetary values may produce unacceptable solutions. I drop the tight requirement and suggest a procedure in which the differences in the monetary values are explained in terms of satisfaction per monetary share as perceived by the agents. A robustness study shows the consequences of misspecification in the model parameters.
Emergent naming conventions in a foraging robot swarm
Venue: arXiv cs.RO 2022
Year: 2022

In this study, we investigate the emergence of naming conventions within a swarm of robots that collectively forage, that is, collect resources from multiple sources in the environment. While foraging, the swarm explores the environment and makes a collective decision on how to exploit the available resources, either by selecting a single source or concurrently exploiting more than one. At the same time, the robots locally exchange messages in order to agree on how to name each source. Here, we study the correlation between the task-induced interaction network and the emergent naming conventions. In particular, our goal is to determine whether the dynamics of the interaction network are sufficient to determine an emergent vocabulary that is potentially useful to the robot swarm. To be useful, linguistic conventions need to be compact and meaningful, that is, to be the minimal description of the relevant features of the environment and of the made collective decision. We show that, in order to obtain a useful vocabulary, the task-dependent interaction network alone is not sufficient but it must be combined with a correlation between language and foraging dynamics. On the basis of these results, we propose a decentralised algorithm for collective categorisation which enables the swarm to achieve a useful -- compact and meaningful -- naming of all the available sources. Understanding how useful linguistic conventions emerge contributes to the design of robot swarms with potentially improved autonomy, flexibility, and self-awareness.
Combining No-regret and Q-learning
Venue: arXiv cs.LG 2022
Year: 2022

Counterfactual Regret Minimization (CFR) has found success in settings like poker which have both terminal states and perfect recall. We seek to understand how to relax these requirements. As a first step, we introduce a simple algorithm, local no-regret learning (LONR), which uses a Q-learning-like update rule to allow learning without terminal states or perfect recall. We prove its convergence for the basic case of MDPs (and limited extensions of them) and present empirical results showing that it achieves last iterate convergence in a number of settings, most notably NoSDE games, a class of Markov games specifically designed to be challenging to learn where no prior algorithm is known to achieve convergence to a stationary equilibrium even on average.
Uncertainty Quantification and Exploration for Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

We investigate statistical uncertainty quantification for reinforcement learning (RL) and its implications in exploration policy. Despite ever-growing literature on RL applications, fundamental questions about inference and error quantification, such as large-sample behaviors, appear to remain quite open. In this paper, we fill in the literature gap by studying the central limit theorem behaviors of estimated Q-values and value functions under various RL settings. In particular, we explicitly identify closed-form expressions of the asymptotic variances, which allow us to efficiently construct asymptotically valid confidence regions for key RL quantities. Furthermore, we utilize these asymptotic expressions to design an effective exploration strategy, which we call Q-value-based Optimal Computing Budget Allocation (Q-OCBA). The policy relies on maximizing the relative discrepancies among the Q-value estimates. Numerical experiments show superior performances of our exploration strategy than other benchmark policies.
Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions
Venue: arXiv cs.NE 2022
Year: 2022

As evolutionary algorithms (EAs) are general-purpose optimization algorithms, recent theoretical studies have tried to analyze their performance for solving general problem classes, with the goal of providing a general theoretical explanation of the behavior of EAs. Particularly, a simple multi-objective EA, i.e., GSEMO, has been shown to be able to achieve good polynomial-time approximation guarantees for submodular optimization, where the objective function is only required to satisfy some properties but without explicit formulation. Submodular optimization has wide applications in diverse areas, and previous studies have considered the cases where the objective functions are monotone submodular, monotone non-submodular, or non-monotone submodular. To complement this line of research, this paper studies the problem class of maximizing monotone approximately submodular minus modular functions (i.e., $f=g-c$) with a size constraint, where $g$ is a non-negative monotone approximately submodular function and $c$ is a non-negative modular function, resulting in the objective function $f$ being non-monotone non-submodular. We prove that the GSEMO can achieve the best-known polynomial-time approximation guarantee. Empirical studies on the applications of Bayesian experimental design and directed vertex cover show the excellent performance of the GSEMO.
MUTLA: A Large-Scale Dataset for Multimodal Teaching and Learning Analytics
Venue: arXiv cs.CY 2022
Year: 2022

Automatic analysis of teacher and student interactions could be very important to improve the quality of teaching and student engagement. However, despite some recent progress in utilizing multimodal data for teaching and learning analytics, a thorough analysis of a rich multimodal dataset coming for a complex real learning environment has yet to be done. To bridge this gap, we present a large-scale MUlti-modal Teaching and Learning Analytics (MUTLA) dataset. This dataset includes time-synchronized multimodal data records of students (learning logs, videos, EEG brainwaves) as they work in various subjects from Squirrel AI Learning System (SAIL) to solve problems of varying difficulty levels. The dataset resources include user records from the learner records store of SAIL, brainwave data collected by EEG headset devices, and video data captured by web cameras while students worked in the SAIL products. Our hope is that by analyzing real-world student learning activities, facial expressions, and brainwave patterns, researchers can better predict engagement, which can then be used to improve adaptive learning selection and student learning outcomes. An additional goal is to provide a dataset gathered from real-world educational activities versus those from controlled lab environments to benefit the educational learning community.
Bridging Information Security and Environmental Criminology Research to Better Mitigate Cybercrime
Venue: arXiv cs.CR 2022
Year: 2022

Cybercrime is a complex phenomenon that spans both technical and human aspects. As such, two disjoint areas have been studying the problem from separate angles: the information security community and the environmental criminology one. Despite the large body of work produced by these communities in the past years, the two research efforts have largely remained disjoint, with researchers on one side not benefitting from the advancements proposed by the other. In this paper, we argue that it would be beneficial for the information security community to look at the theories and systematic frameworks developed in environmental criminology to develop better mitigations against cybercrime. To this end, we provide an overview of the research from environmental criminology and how it has been applied to cybercrime. We then survey some of the research proposed in the information security domain, drawing explicit parallels between the proposed mitigations and environmental criminology theories, and presenting some examples of new mitigations against cybercrime. Finally, we discuss the concept of cyberplaces and propose a framework in order to define them. We discuss this as a potential research direction, taking into account both fields of research, in the hope of broadening interdisciplinary efforts in cybercrime research.
When Nash Meets Stackelberg
Venue: arXiv cs.GT 2022
Year: 2022

This article introduces a class of $Nash$ games among $Stackelberg$ players ($NASPs$), namely, a class of simultaneous non-cooperative games where the players solve sequential Stackelberg games. Specifically, each player solves a Stackelberg game where a leader optimizes a (parametrized) linear objective function subject to linear constraints while its followers solve convex quadratic problems subject to the standard optimistic assumption. Although we prove that deciding if a $NASP$ instance admits a Nash equilibrium is generally a $Σ^2_p$-hard decision problem, we devise two exact and computationally-efficient algorithms to compute and select Nash equilibria or certify that no equilibrium exists. We apply $NASPs$ to model the hierarchical interactions of international energy markets where climate-change aware regulators oversee the operations of profit-driven energy producers. By combining real-world data with our models, we find that Nash equilibria provide informative, and often counterintuitive, managerial insights for market regulators.
Iterative Augmentation of Visual Evidence for Weakly-Supervised Lesion Localization in Deep Interpretability Frameworks: Application to Color Fundus Images
Venue: arXiv cs.CV 2022
Year: 2022

Interpretability of deep learning (DL) systems is gaining attention in medical imaging to increase experts' trust in the obtained predictions and facilitate their integration in clinical settings. We propose a deep visualization method to generate interpretability of DL classification tasks in medical imaging by means of visual evidence augmentation. The proposed method iteratively unveils abnormalities based on the prediction of a classifier trained only with image-level labels. For each image, initial visual evidence of the prediction is extracted with a given visual attribution technique. This provides localization of abnormalities that are then removed through selective inpainting. We iteratively apply this procedure until the system considers the image as normal. This yields augmented visual evidence, including less discriminative lesions which were not detected at first but should be considered for final diagnosis. We apply the method to grading of two retinal diseases in color fundus images: diabetic retinopathy (DR) and age-related macular degeneration (AMD). We evaluate the generated visual evidence and the performance of weakly-supervised localization of different types of DR and AMD abnormalities, both qualitatively and quantitatively. We show that the augmented visual evidence of the predictions highlights the biomarkers considered by experts for diagnosis and improves the final localization performance. It results in a relative increase of 11.2+/-2.0% per image regarding sensitivity averaged at 10 false positives/image on average, when applied to different classification tasks, visual attribution techniques and network architectures. This makes the proposed method a useful tool for exhaustive visual support of DL classifiers in medical imaging.
Reducing the Computational Complexity of Pseudoinverse for the Incremental Broad Learning System on Added Inputs
Venue: arXiv cs.LG 2022
Year: 2022

In this brief, we improve the Broad Learning System (BLS) [7] by reducing the computational complexity of the incremental learning for added inputs. We utilize the inverse of a sum of matrices in [8] to improve a step in the pseudoinverse of a row-partitioned matrix. Accordingly we propose two fast algorithms for the cases of q > k and q < k, respectively, where q and k denote the number of additional training samples and the total number of nodes, respectively. Specifically, when q > k, the proposed algorithm computes only a k * k matrix inverse, instead of a q * q matrix inverse in the existing algorithm. Accordingly it can reduce the complexity dramatically. Our simulations, which follow those for Table V in [7], show that the proposed algorithm and the existing algorithm achieve the same testing accuracy, while the speedups in BLS training time of the proposed algorithm over the existing algorithm are 1.24 - 1.30.
On Completeness-aware Concept-Based Explanations in Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Human explanations of high-level decisions are often expressed in terms of key concepts the decisions are based on. In this paper, we study such concept-based explainability for Deep Neural Networks (DNNs). First, we define the notion of completeness, which quantifies how sufficient a particular set of concepts is in explaining a model's prediction behavior based on the assumption that complete concept scores are sufficient statistics of the model prediction. Next, we propose a concept discovery method that aims to infer a complete set of concepts that are additionally encouraged to be interpretable, which addresses the limitations of existing methods on concept explanations. To define an importance score for each discovered concept, we adapt game-theoretic notions to aggregate over sets and propose ConceptSHAP. Via proposed metrics and user studies, on a synthetic dataset with apriori-known concept explanations, as well as on real-world image and language datasets, we validate the effectiveness of our method in finding concepts that are both complete in explaining the decisions and interpretable. (The code is released at https://github.com/chihkuanyeh/concept_exp)
Emanation Graph: A Plane Geometric Spanner with Steiner Points
Venue: arXiv cs.CG 2022
Year: 2022

An emanation graph of grade $k$ on a set of points is a plane spanner made by shooting $2^{k+1}$ equally spaced rays from each point, where the shorter rays stop the longer ones upon collision. The collision points are the Steiner points of the spanner. Emanation graphs of grade one were studied by Mondal and Nachmanson in the context of network visualization. They proved that the spanning ratio of such a graph is bounded by $(2+\sqrt{2})\approx 3.414$. We improve this upper bound to $\sqrt{10} \approx 3.162$ and show this to be tight, i.e., there exist emanation graphs with spanning ratio $\sqrt{10}$. We show that for every fixed $k$, the emanation graphs of grade $k$ are constant spanners, where the constant factor depends on $k$. An emanation graph of grade two may have twice the number of edges compared to grade one graphs. Hence we introduce a heuristic method for simplifying them. In particular, we compare simplified emanation graphs against Shewchuk's constrained Delaunay triangulations on both synthetic and real-life datasets. Our experimental results reveal that the simplified emanation graphs outperform constrained Delaunay triangulations in common quality measures (e.g., edge count, angular resolution, average degree, total edge length) while maintaining a comparable spanning ratio and Steiner point count.
Introduction to Univalent Foundations of Mathematics with Agda
Venue: arXiv cs.LO 2022
Year: 2022

We introduce Voevodsky's univalent foundations and univalent mathematics, and explain how to develop them with the computer system Agda, which is based on Martin-Löf type theory. Agda allows us to write mathematical definitions, constructions, theorems and proofs, for example in number theory, analysis, group theory, topology, category theory or programming language theory, checking them for logical and mathematical correctness. Agda is a constructive mathematical system by default, which amounts to saying that it can also be considered as a programming language for manipulating mathematical objects. But we can assume the axiom of choice or the principle of excluded middle for pieces of mathematics that require them, at the cost of losing the implicit programming-language character of the system. For a fully constructive development of univalent mathematics in Agda, we would need to use its new cubical flavour, and we hope these notes provide a base for researchers interested in learning cubical type theory and cubical Agda as the next step. Compared to most expositions of the subject, we work with explicit universe levels.
Higher Criticism for Discriminating Word-Frequency Tables and Testing Authorship
Venue: arXiv cs.CL 2022
Year: 2022

We adapt the Higher Criticism (HC) goodness-of-fit test to measure the closeness between word-frequency tables. We apply this measure to authorship attribution challenges, where the goal is to identify the author of a document using other documents whose authorship is known. The method is simple yet performs well without handcrafting and tuning; reporting accuracy at the state of the art level in various current challenges. As an inherent side effect, the HC calculation identifies a subset of discriminating words. In practice, the identified words have low variance across documents belonging to a corpus of homogeneous authorship. We conclude that in comparing the similarity of a new document and a corpus of a single author, HC is mostly affected by words characteristic of the author and is relatively unaffected by topic structure.
Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity
Venue: arXiv cs.IT 2022
Year: 2022

Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $α> 0$. We construct, for any sufficiently small $δ> 0$, binary linear codes of block length $O(1/δ^{2+α})$ and rate $I(W)-δ$ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. Shannon's noisy coding theorem established the \emph{existence} of such codes (without efficient constructions or decoding) with block length $O(1/δ^2)$. This quadratic dependence on the gap $δ$ to capacity is known to be best possible. Our result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan's polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.
Kernelized Similarity Learning and Embedding for Dynamic Texture Synthesis
Venue: arXiv cs.CV 2022
Year: 2022

Dynamic texture (DT) exhibits statistical stationarity in the spatial domain and stochastic repetitiveness in the temporal dimension, indicating that different frames of DT possess a high similarity correlation that is critical prior knowledge. However, existing methods cannot effectively learn a promising synthesis model for high-dimensional DT from a small number of training data. In this paper, we propose a novel DT synthesis method, which makes full use of similarity prior knowledge to address this issue. Our method bases on the proposed kernel similarity embedding, which not only can mitigate the high-dimensionality and small sample issues, but also has the advantage of modeling nonlinear feature relationship. Specifically, we first raise two hypotheses that are essential for DT model to generate new frames using similarity correlation. Then, we integrate kernel learning and extreme learning machine into a unified synthesis model to learn kernel similarity embedding for representing DT. Extensive experiments on DT videos collected from the internet and two benchmark datasets, i.e., Gatech Graphcut Textures and Dyntex, demonstrate that the learned kernel similarity embedding can effectively exhibit the discriminative representation for DT. Accordingly, our method is capable of preserving the long-term temporal continuity of the synthesized DT sequences with excellent sustainability and generalization. Meanwhile, it effectively generates realistic DT videos with fast speed and low computation, compared with the state-of-the-art methods. The code and more synthesis videos are available at our project page https://shiming-chen.github.io/Similarity-page/Similarit.html.
Chemical Reactions-based Detection Mechanism for Molecular Communications
Venue: arXiv cs.IT 2022
Year: 2022

In molecular communications, the direct detection of signaling molecules may be challenging due to a lack of suitable sensors and interference in the environment. Motivated by research in molecular biology, we investigate an indirect detection mechanism using chemical reactions between the signaling molecules and a molecular probe to produce an easy-to-measure product at the receiver. We consider two implementations of the proposed detection mechanism, i.e., unrestricted probe movement and probes restricted to a volume around the receiver. The reaction-diffusion equations describing the concentrations of the reactant and product molecules in the system are non-linear and coupled, and cannot be solved in closed form. Therefore, we develop an efficient iterative algorithm by discretizing the time variable and solving for the space variables of the equations in each time step. Our results show that the concentrations of the product molecules and the signalling molecules share a similar characteristic over time, i.e., a single peak and a long tail. The peak and tail values of the product molecule concentration can be controlled by choosing probes with suitable parameters. By carefully choosing the molecular probe and optimizing the decision threshold, the BER can be improved significantly and outperform that of a direct detection system.
Simplified and Unified Analysis of Various Learning Problems by Reduction to Multiple-Instance Learning
Venue: arXiv cs.LG 2022
Year: 2022

In statistical learning, many problem formulations have been proposed so far, such as multi-class learning, complementarily labeled learning, multi-label learning, multi-task learning, which provide theoretical models for various real-world tasks. Although they have been extensively studied, the relationship among them has not been fully investigated. In this work, we focus on a particular problem formulation called Multiple-Instance Learning (MIL), and show that various learning problems including all the problems mentioned above with some of new problems can be reduced to MIL with theoretically guaranteed generalization bounds, where the reductions are established under a new reduction scheme we provide as a by-product. The results imply that the MIL-reduction gives a simplified and unified framework for designing and analyzing algorithms for various learning problems. Moreover, we show that the MIL-reduction framework can be kernelized.
Information in Infinite Ensembles of Infinitely-Wide Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

In this preliminary work, we study the generalization properties of infinite ensembles of infinitely-wide neural networks. Amazingly, this model family admits tractable calculations for many information-theoretic quantities. We report analytical and empirical investigations in the search for signals that correlate with generalization.