OpenRaiser/Intern-Atlas huggingface dataset:
Cognition in Dynamical Systems, Second Edition
Venue: arXiv cs.MA 2022
Year: 2022

Cognition is the process of knowing. As carried out by a dynamical system, it is the process by which the system absorbs information into its state. A complex network of agents cognizes knowledge about its environment, internal dynamics and initial state by forming emergent, macro-level patterns. Such patterns require each agent to find its place while partially aware of the whole pattern. Such partial awareness can be achieved by separating the system dynamics into two parts by timescale: the propagation dynamics and the pattern dynamics. The fast propagation dynamics describe the spread of signals across the network. If they converge to a fixed point for any quasi-static state of the slow pattern dynamics, that fixed point represents an aggregate of macro-level information. On longer timescales, agents coordinate via positive feedback to form patterns, which are defined using closed walks in the graph of agents. Patterns can be coherent, in that every part of the pattern depends on every other part for context. Coherent patterns are acausal, in that (a) they cannot be predicted and (b) no part of the stored knowledge can be mapped to any part of the pattern, or vice versa. A cognitive network's knowledge is encoded or embodied by the selection of patterns which emerge. The theory of cognition summarized here can model autocatalytic reaction-diffusion systems, artificial neural networks, market economies and ant colony optimization, among many other real and virtual systems. This theory suggests a new understanding of complexity as a lattice of contexts rather than a single measure.
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
Venue: arXiv cs.DS 2022
Year: 2022

A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is $\mathcal {\tilde O}(n^{2 - 1/α} + n^{1/(2α)} + δ_{\max})$ with high probability, where $α\in (0.5, 1)$ controls the power-law exponent of the degree distribution, and $δ_{\max}$ is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
Human Action Recognition and Prediction: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

Derived from rapid advances in computer vision and machine learning, video analysis tasks have been moving from inferring the present state to predicting the future state. Vision-based action recognition and prediction from videos are such tasks, where action recognition is to infer human actions (present state) based upon complete action executions, and action prediction to predict human actions (future state) based upon incomplete action executions. These two tasks have become particularly prevalent topics recently because of their explosively emerging real-world applications, such as visual surveillance, autonomous driving vehicle, entertainment, and video retrieval, etc. Many attempts have been devoted in the last a few decades in order to build a robust and effective framework for action recognition and prediction. In this paper, we survey the complete state-of-the-art techniques in action recognition and prediction. Existing models, popular algorithms, technical difficulties, popular action databases, evaluation protocols, and promising future directions are also provided with systematic discussions.
Cut-off Theorems for the PV-model
Venue: arXiv cs.DC 2022
Year: 2022

We prove cut-off results for deadlocks and serializability of a $PV$-thread $T$ run in parallel with itself: For a $PV$ thread $T$ which accesses a set $\mathcal{R}$ of resources, each with a maximal capacity $κ:\mathcal{R}\to\mathbb{N}$, the PV-program $T^n$, where $n$ copies of $T$ are run in parallel, is deadlock free for all $n$ if and only if $T^M$ is deadlock free where $M=Σ_{r\in\mathcal{R}}κ(r)$. This is a sharp bound: For all $κ:\mathcal{R}\to\mathbb{N}$ and finite $\mathcal{R}$ there is a thread $T$ using these resources such that $T^M$ has a deadlock, but $T^n$ does not for $n<M$. Moreover, we prove a more general theorem: There are no deadlocks in $p=T1|T2|\cdots |Tn$ if and only if there are no deadlocks in $T_{i_1}|T_{i_2}|\cdots |T_{i_M}$ for any subset $\{i_1,\ldots,i_M\}\subset [1:n]$. For $κ(r)\equiv 1$, $T^n$ is serializable for all $n$ if and only if $T^2$ is serializable. For general capacities, we define a local obstruction to serializability. There is no local obstruction to serializability in $T^n$ for all $n$ if and only if there is no local obstruction to serializability in $T^M$ for $M=Σ_{r\in\mathcal{R}}κ(r)+1$. The obstructions may be found using a deadlock algorithm in $T^{M+1}$. These serializability results also have a generalization: If there are no local obstructions to serializability in any of the $M$-dimensional sub programs, $T_{i_1}|T_{i_2}|\cdots |T_{i_M}$, then $p$ is serializable.
Backplay: "Man muss immer umkehren"
Venue: arXiv cs.LG 2022
Year: 2022

Model-free reinforcement learning (RL) requires a large number of trials to learn a good policy, especially in environments with sparse rewards. We explore a method to improve the sample efficiency when we have access to demonstrations. Our approach, Backplay, uses a single demonstration to construct a curriculum for a given task. Rather than starting each training episode in the environment's fixed initial state, we start the agent near the end of the demonstration and move the starting point backwards during the course of training until we reach the initial state. Our contributions are that we analytically characterize the types of environments where Backplay can improve training speed, demonstrate the effectiveness of Backplay both in large grid worlds and a complex four player zero-sum game (Pommerman), and show that Backplay compares favorably to other competitive methods known to improve sample efficiency. This includes reward shaping, behavioral cloning, and reverse curriculum generation.
SecuCode: Intrinsic PUF Entangled Secure Wireless Code Dissemination for Computational RFID Devices
Venue: arXiv cs.CR 2022
Year: 2022

The simplicity of deployment and perpetual operation of energy harvesting devices provides a compelling proposition for a new class of edge devices for the Internet of Things. In particular, Computational Radio Frequency Identification (CRFID) devices are an emerging class of battery-free, computational, sensing enhanced devices that harvest all of their energy for operation. Despite wireless connectivity and powering, secure wireless firmware updates remains an open challenge for CRFID devices due to: intermittent powering, limited computational capabilities, and the absence of a supervisory operating system. We present, for the first time, a secure wireless code dissemination (SecuCode) mechanism for CRFIDs by entangling a device intrinsic hardware security primitive Static Random Access Memory Physical Unclonable Function (SRAM PUF) to a firmware update protocol. The design of SecuCode: i) overcomes the resource-constrained and intermittently powered nature of the CRFID devices; ii) is fully compatible with existing communication protocols employed by CRFID devices in particular, ISO-18000-6C protocol; and ii) is built upon a standard and industry compliant firmware compilation and update method realized by extending a recent framework for firmware updates provided by Texas Instruments. We build an end-to-end SecuCode implementation and conduct extensive experiments to demonstrate standards compliance, evaluate performance and security.
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
Venue: arXiv cs.DS 2022
Year: 2022

We obtain the first strong coresets for the $k$-median and subspace approximation problems with sum of distances objective function, on $n$ points in $d$ dimensions, with a number of weighted points that is independent of both $n$ and $d$; namely, our coresets have size $\text{poly}(k/ε)$. A strong coreset $(1+ε)$-approximates the cost function for all possible sets of centers simultaneously. We also give efficient $\text{nnz}(A) + (n+d)\text{poly}(k/ε) + \exp(\text{poly}(k/ε))$ time algorithms for computing these coresets. We obtain the result by introducing a new dimensionality reduction technique for coresets that significantly generalizes an earlier result of Feldman, Sohler and Schmidt \cite{FSS13} for squared Euclidean distances to sums of $p$-th powers of Euclidean distances for constant $p\ge1$.
Generalization Properties of hyper-RKHS and its Applications
Venue: arXiv cs.LG 2022
Year: 2022

This paper generalizes regularized regression problems in a hyper-reproducing kernel Hilbert space (hyper-RKHS), illustrates its utility for kernel learning and out-of-sample extensions, and proves asymptotic convergence results for the introduced regression models in an approximation theory view. Algorithmically, we consider two regularized regression models with bivariate forms in this space, including kernel ridge regression (KRR) and support vector regression (SVR) endowed with hyper-RKHS, and further combine divide-and-conquer with Nyström approximation for scalability in large sample cases. This framework is general: the underlying kernel is learned from a broad class, and can be positive definite or not, which adapts to various requirements in kernel learning. Theoretically, we study the convergence behavior of regularized regression algorithms in hyper-RKHS and derive the learning rates, which goes beyond the classical analysis on RKHS due to the non-trivial independence of pairwise samples and the characterisation of hyper-RKHS. Experimentally, results on several benchmarks suggest that the employed framework is able to learn a general kernel function form an arbitrary similarity matrix, and thus achieves a satisfactory performance on classification tasks.
Efficient Linear Bandits through Matrix Sketching
Venue: arXiv cs.LG 2022
Year: 2022

We prove that two popular linear contextual bandit algorithms, OFUL and Thompson Sampling, can be made efficient using Frequent Directions, a deterministic online sketching technique. More precisely, we show that a sketch of size $m$ allows a $\mathcal{O}(md)$ update time for both algorithms, as opposed to $Ω(d^2)$ required by their non-sketched versions in general (where $d$ is the dimension of context vectors). This computational speedup is accompanied by regret bounds of order $(1+\varepsilon_m)^{3/2}d\sqrt{T}$ for OFUL and of order $\big((1+\varepsilon_m)d\big)^{3/2}\sqrt{T}$ for Thompson Sampling, where $\varepsilon_m$ is bounded by the sum of the tail eigenvalues not covered by the sketch. In particular, when the selected contexts span a subspace of dimension at most $m$, our algorithms have a regret bound matching that of their slower, non-sketched counterparts. Experiments on real-world datasets corroborate our theoretical results.
A Class of Hybrid LQG Mean Field Games with State-Invariant Switching and Stopping Strategies
Venue: arXiv cs.SY 2022
Year: 2022

A novel framework is presented that combines Mean Field Game (MFG) theory and Hybrid Optimal Control (HOC) theory to obtain a unique $ε$-Nash equilibrium for a non-cooperative game with switching and stopping times. We consider the case where there exists one major agent with a significant influence on the system together with a large number of minor agents constituting two subpopulations, each agent with individually asymptotically negligible effect on the whole system. Each agent has stochastic linear dynamics with quadratic costs, and the agents are coupled in their dynamics and costs by the average state of minor agents (i.e. the empirical mean field). It is shown that for a class of Hybrid LQG MFGs, the optimal switching and stopping times are state-invariant and only depend on the dynamical parameters of each agent. Accordingly, a hybrid systems formulation of the game is presented via the indexing by discrete events: (i) the switching of the major agent between alternative dynamics or (ii) the termination of the agents' trajectories in one or both of the subpopulations of minor agents. Optimal switchings and stopping time strategies together with best response control actions for, respectively, the major agent and all minor agents are established with respect to their individual cost criteria by an application of Hybrid LQG MFG theory.
Listening for Sirens: Locating and Classifying Acoustic Alarms in City Scenes
Venue: arXiv cs.SD 2022
Year: 2022

This paper is about alerting acoustic event detection and sound source localisation in an urban scenario. Specifically, we are interested in spotting the presence of horns, and sirens of emergency vehicles. In order to obtain a reliable system able to operate robustly despite the presence of traffic noise, which can be copious, unstructured and unpredictable, we propose to treat the spectrograms of incoming stereo signals as images, and apply semantic segmentation, based on a Unet architecture, to extract the target sound from the background noise. In a multi-task learning scheme, together with signal denoising, we perform acoustic event classification to identify the nature of the alerting sound. Lastly, we use the denoised signals to localise the acoustic source on the horizon plane, by regressing the direction of arrival of the sound through a CNN architecture. Our experimental evaluation shows an average classification rate of 94%, and a median absolute error on the localisation of 7.5° when operating on audio frames of 0.5s, and of 2.5° when operating on frames of 2.5s. The system offers excellent performance in particularly challenging scenarios, where the noise level is remarkably high.
Risk-Sensitive Reinforcement Learning via Policy Gradient Search
Venue: arXiv cs.LG 2022
Year: 2022

The objective in a traditional reinforcement learning (RL) problem is to find a policy that optimizes the expected value of a performance metric such as the infinite-horizon cumulative discounted or long-run average cost/reward. In practice, optimizing the expected value alone may not be satisfactory, in that it may be desirable to incorporate the notion of risk into the optimization problem formulation, either in the objective or as a constraint. Various risk measures have been proposed in the literature, e.g., exponential utility, variance, percentile performance, chance constraints, value at risk (quantile), conditional value-at-risk, prospect theory and its later enhancement, cumulative prospect theory. In this book, we consider risk-sensitive RL in two settings: one where the goal is to find a policy that optimizes the usual expected value objective while ensuring that a risk constraint is satisfied, and the other where the risk measure is the objective. We survey some of the recent work in this area specifically where policy gradient search is the solution approach. In the first risk-sensitive RL setting, we cover popular risk measures based on variance, conditional value-at-risk, and chance constraints, and present a template for policy gradient-based risk-sensitive RL algorithms using a Lagrangian formulation. For the setting where risk is incorporated directly into the objective function, we consider an exponential utility formulation, cumulative prospect theory, and coherent risk measures. This non-exhaustive survey aims to give a flavor of the challenges involved in solving risk-sensitive RL problems using policy gradient methods, as well as outlining some potential future research directions.
Blind Two-Dimensional Super-Resolution and Its Performance Guarantee (Extended Version)
Venue: arXiv cs.IT 2022
Year: 2022

We study the problem of identifying the parameters of a linear system from its response to multiple unknown waveforms. We assume that the system response is a scaled superposition of time-delayed and frequency-shifted versions of the unknown waveforms. Such kind of problem is severely ill-posed and does not yield a unique solution without introducing further constraints. To fully characterize the system, we assume that the unknown waveforms lie in a common known low-dimensional subspace that satisfies certain properties. Then, we develop a blind two-dimensional (2D) super-resolution framework that applies to a large number of applications. In this framework, we show that under a minimum separation between the time-frequency shifts, all the unknowns that characterize the system can be recovered precisely and with high probability provided that a lower bound on the number of the observed samples is satisfied. The proposed framework is based on a 2D atomic norm minimization problem, which is shown to be reformulated and solved via semidefinite programming. Simulation results that confirm the theoretical findings of the paper are provided.
Flexible Representative Democracy: An Introduction with Binary Issues
Venue: arXiv cs.MA 2022
Year: 2022

We introduce Flexible Representative Democracy (FRD), a novel hybrid of Representative Democracy (RD) and Direct Democracy (DD) in which voters can alter the issue-dependent weights of a set of elected representatives. In line with the literature on Interactive Democracy, our model allows the voters to actively determine the degree to which the system is direct versus representative. However, unlike Liquid Democracy, Flexible Representative Democracy uses strictly non-transitive delegations, making delegation cycles impossible, and maintains a fixed set of accountable, elected representatives. We present FRD and analyze it using a computational approach with issues that are binary and symmetric. We compare the outcomes of various voting systems using Direct Democracy with majority voting as an ideal baseline. First, we demonstrate the shortcomings of Representative Democracy in our model. We provide NP-Hardness results for electing an ideal set of representatives, discuss pathologies, and demonstrate empirically that common multi-winner election rules for selecting representatives do not perform well in expectation. To analyze the effects of adding flexibility, we begin by providing theoretical results on how issue-specific delegations determine outcomes. Finally, we provide empirical results comparing the outcomes of Representative Democracy, proxy voting with fixed sets of proxies across issues, and Flexible Representative Democracy with issue-specific delegations. Our results show that variants of Proxy Voting yield no discernible benefit over unweighted representatives and reveal the potential for Flexible Representative Democracy to improve outcomes as voter participation increases.
Speech Intention Understanding in a Head-final Language: A Disambiguation Utilizing Intonation-dependency
Venue: arXiv cs.CL 2022
Year: 2022

For a large portion of real-life utterances, the intention cannot be solely decided by either their semantic or syntactic characteristics. Although not all the sociolinguistic and pragmatic information can be digitized, at least phonetic features are indispensable in understanding the spoken language. Especially in head-final languages such as Korean, sentence-final prosody has great importance in identifying the speaker's intention. This paper suggests a system which identifies the inherent intention of a spoken utterance given its transcript, in some cases using auxiliary acoustic features. The main point here is a separate distinction for cases where discrimination of intention requires an acoustic cue. Thus, the proposed classification system decides whether the given utterance is a fragment, statement, question, command, or a rhetorical question/command, utilizing the intonation-dependency coming from the head-finality. Based on an intuitive understanding of the Korean language that is engaged in the data annotation, we construct a network which identifies the intention of a speech, and validate its utility with the test sentences. The system, if combined with up-to-date speech recognizers, is expected to be flexibly inserted into various language understanding modules.
Attention, Please! Adversarial Defense via Activation Rectification and Preservation
Venue: arXiv cs.CV 2022
Year: 2022

This study provides a new understanding of the adversarial attack problem by examining the correlation between adversarial attack and visual attention change. In particular, we observed that: (1) images with incomplete attention regions are more vulnerable to adversarial attacks; and (2) successful adversarial attacks lead to deviated and scattered attention map. Accordingly, an attention-based adversarial defense framework is designed to simultaneously rectify the attention map for prediction and preserve the attention area between adversarial and original images. The problem of adding iteratively attacked samples is also discussed in the context of visual attention change. We hope the attention-related data analysis and defense solution in this study will shed some light on the mechanism behind the adversarial attack and also facilitate future adversarial defense/attack model design.
Unlabeled sample compression schemes and corner peelings for ample and maximum classes
Venue: arXiv cs.DM 2022
Year: 2022

We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) of a partial shelling of the cross-polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that all previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous. On the positive side we present a new construction of an unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabeled sample compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes.
Output-Oblivious Stochastic Chemical Reaction Networks
Venue: arXiv cs.CC 2022
Year: 2022

We classify the functions $f:\mathbb{N}^2 \rightarrow \mathbb{N}$ which are stably computable by output-oblivious Stochastic Chemical Reaction Networks (CRNs), i.e., systems of reactions in which output species are never reactants. While it is known that precisely the semilinear functions are stably computable by CRNs, such CRNs sometimes rely on initially producing too many output species and then consuming the excess in order to reach a correct stable state. These CRNs may be difficult to integrate into larger systems: if the output of a CRN $\mathcal{C}$ becomes the input to a downstream CRN $\mathcal{C}'$, then $\mathcal{C}'$ could inadvertently consume too many outputs before $\mathcal{C}$ stabilizes. If, on the other hand, $\mathcal{C}$ is output-oblivious then $\mathcal{C}'$ may consume $\mathcal{C}$'s output as soon as it is available. In this work we prove that a semilinear function $f:\mathbb{N}^2 \rightarrow \mathbb{N}$ is stably computable by an output-oblivious CRN with a leader if and only if it is both increasing and either grid-affine (intuitively, its domains are congruence classes), or the minimum of a finite set of fissure functions (intuitively, functions behaving like the min function).