OpenRaiser/Intern-Atlas huggingface dataset:
On the Principle of Least Symmetry Breaking in Shallow ReLU Models
Venue: arXiv cs.LG 2023
Year: 2023

We consider the optimization problem associated with fitting two-layer ReLU networks with respect to the squared loss, where labels are assumed to be generated by a target network. Focusing first on standard Gaussian inputs, we show that the structure of spurious local minima detected by stochastic gradient descent (SGD) is, in a well-defined sense, the \emph{least loss of symmetry} with respect to the target weights. A closer look at the analysis indicates that this principle of least symmetry breaking may apply to a broader range of settings. Motivated by this, we conduct a series of experiments which corroborate this hypothesis for different classes of non-isotropic non-product distributions, smooth activation functions and networks with a few layers.
DADA: Driver Attention Prediction in Driving Accident Scenarios
Venue: arXiv cs.CV 2023
Year: 2023

Driver attention prediction is becoming an essential research problem in human-like driving systems. This work makes an attempt to predict the driver attention in driving accident scenarios (DADA). However, challenges tread on the heels of that because of the dynamic traffic scene, intricate and imbalanced accident categories. In this work, we design a semantic context induced attentive fusion network (SCAFNet). We first segment the RGB video frames into the images with different semantic regions (i.e., semantic images), where each region denotes one kind of semantic categories of the scene (e.g., road, trees, etc.), and learn the spatio-temporal features of RGB frames and semantic images in two parallel paths simultaneously. Then, the learned features are fused by an attentive fusion network to find the semantic-induced scene variation in driver attention prediction. The contributions are three folds. 1) With the semantic images, we introduce their semantic context features and verified the manifest promotion effect for helping the driver attention prediction, where the semantic context features are modeled by a graph convolution network (GCN) on semantic images; 2) We fuse the semantic context features of semantic images and the features of RGB frames in an attentive strategy, and the fused details are transferred over frames by a convolutional LSTM module to obtain the attention map of each video frame with the consideration of historical scene variation in driving situations; 3) The superiority of the proposed method is evaluated on our previously collected dataset (named as DADA-2000) and two other challenging datasets with state-of-the-art methods. DADA-2000 is available at https://github.com/JWFangit/LOTVS-DADA.
Recursion, evolution and conscious self
Venue: arXiv cs.LO 2023
Year: 2023

We introduce and study a learning theory which is roughly automatic, that is, it does not require but a minimum of initial programming, and is based on the potential computational phenomenon of self-reference, (i.e. the potential ability of an algorithm to have its program as an input). The conclusions agree with scientific findings in both biology and neuroscience and provide a plethora of explanations both (in conjunction with Darwinism) about evolution, as well as for the functionality and learning capabilities of human brain, (most importantly), as we perceive them in ourselves.
Optimizing Query Predicates with Disjunctions for Column-Oriented Engines
Venue: arXiv cs.DB 2023
Year: 2023

Database research has always given limited attention to optimizing predicates with disjunctions. What little past work there is, has mostly focused on optimizations for traditional row-oriented databases. However, a key difference between how row-oriented and column-oriented engines evaluate predicates is that while row-oriented engines apply predicates to a single tuple at a time, column-oriented engines apply predicates to sets of tuples, adding another dimension to the problem. As such, row-oriented engines focus only on the best order to apply predicates in to "short-circuit" the overall predicate expression, but column-oriented engines must additionally decide on the input sets of tuples for each predicate application. This is important, since smaller inputs lead to faster runtimes, and nontrivial, since the results of earlier predicates can be used to reduce the inputs to later predicates and predicates may be combined via disjunctions in the predicate expression. In this work, we formally analyze the predicate evaluation problem for column-oriented engines and present BestD/Update, the first ever polynomial-time, provably optimal algorithms to deduce the minimum input sets for each predicate application. BestD/Update's optimality is guaranteed under a wide range of cost models, representing different real-world scenarios. Furthermore, when combined with the predicate ordering algorithm Hanani, BestD/Update reduce into EvalPred, a simple O(n log^2 n) algorithm, which we recommend for practical use and optimal for all predicate expressions of nested depth 2 or less. Our evaluation shows, thanks to its optimality and polynomial planning time, EvalPred outperforms not implementing any disjunction optimizations and exiting optimal algorithms by up to 2.6x and 28x respectively for synthetic workloads and by up to 1.3x and 100x respectively for queries from TPC-H and the CH-benchmark.
Extensional proofs in a propositional logic modulo isomorphisms
Venue: arXiv cs.LO 2023
Year: 2023

System I is a proof language for a fragment of propositional logic where isomorphic propositions, such as $A\wedge B$ and $B\wedge A$, or $A\Rightarrow(B\wedge C)$ and $(A\Rightarrow B)\wedge(A\Rightarrow C)$ are made equal. System I enjoys the strong normalization property. This is sufficient to prove the existence of empty types, but not to prove the introduction property (every closed term in normal form is an introduction). Moreover, a severe restriction had to be made on the types of the variables in order to obtain the existence of empty types. We show here that adding $η$-expansion rules to System I permits to drop this restriction, and yields a strongly normalizing calculus which enjoys the full introduction property.
Power Scaling Laws and Near-Field Behaviors of Massive MIMO and Intelligent Reflecting Surfaces
Venue: arXiv cs.IT 2023
Year: 2023

The use of large arrays might be the solution to the capacity problems in wireless communications. The signal-to-noise ratio (SNR) grows linearly with the number of array elements $N$ when using Massive MIMO receivers and half-duplex relays. Moreover, intelligent reflecting surfaces (IRSs) have recently attracted attention since these can relay signals to achieve an SNR that grows as $N^2$, which seems like a major benefit. In this paper, we use a deterministic propagation model for a planar array of arbitrary size, to demonstrate that the mentioned SNR behaviors, and associated power scaling laws, only apply in the far-field. They cannot be used to study the regime where $N\to\infty$. We derive an exact channel gain expression that captures three essential near-field behaviors and use it to revisit the power scaling laws. We derive new finite asymptotic SNR limits but also conclude that these are unlikely to be approached in practice. We further prove that an IRS-aided setup cannot achieve a higher SNR than an equal-sized Massive MIMO setup, despite its faster SNR growth. We quantify analytically how much larger the IRS must be to achieve the same SNR. Finally, we show that an optimized IRS does not behave as an "anomalous" mirror but can vastly outperform that benchmark.
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
Venue: arXiv cs.CG 2023
Year: 2023

We study the geodesic Voronoi diagram of a set $S$ of $n$ linearly moving sites inside a static simple polygon $P$ with $m$ vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most $O(m^3)$, and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center kinetic data structures handle each event in $O(\log^2 m)$ time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.
First-order tree-to-tree functions
Venue: arXiv cs.FL 2023
Year: 2023

We study tree-to-tree transformations that can be defined in first-order logic or monadic second-order logic. We prove a decomposition theorem, which shows that every transformation can be obtained from prime transformations, such as tree-to-tree homomorphisms or pre-order traversal, by using combinators such as function composition.
Pricing ASICs for Cryptocurrency Mining
Venue: arXiv cs.CR 2023
Year: 2023

Cryptocurrencies that are based on Proof-of-Work (PoW) often rely on special purpose hardware to perform so-called mining operations that secure the system, with miners receiving freshly minted tokens as a reward for their work. A notable example of such a cryptocurrency is Bitcoin, which is primarily mined using application specific integrated circuit (ASIC) based machines. Due to the supposed profitability of cryptocurrency mining, such hardware has been in great demand in recent years, in-spite of high associated costs like electricity. In this work, we show that because mining rewards are given in the mined cryptocurrency, while expenses are usually paid in some fiat currency such as the United States Dollar (USD), cryptocurrency mining is in fact a bundle of financial options. When exercised, each option converts electricity to tokens. We provide a method of pricing mining hardware based on this insight, and prove that any other price creates arbitrage. Our method shows that contrary to the popular belief that mining hardware is worth less if the cryptocurrency is highly volatile, the opposite effect is true: volatility increases value. Thus, if a coin's volatility decreases, some miners may leave, affecting security. We compare the prices produced by our method to prices obtained from popular tools currently used by miners and show that the latter only consider the expected returns from mining, while neglecting to account for the inherent risk in mining, which is due to the high exchange-rate volatility of cryptocurrencies. Finally, we show that the returns made from mining can be imitated by trading in bonds and coins, and create such imitating investment portfolios. Historically, realized revenues of these portfolios have outperformed mining, showing that indeed hardware is mispriced.
Consensus-Halving: Does It Ever Get Easier?
Venue: arXiv cs.CC 2023
Year: 2023

In the $\varepsilon$-Consensus-Halving problem, a fundamental problem in fair division, there are $n$ agents with valuations over the interval $[0,1]$, and the goal is to divide the interval into pieces and assign a label "$+$" or "$-$" to each piece, such that every agent values the total amount of "$+$" and the total amount of "$-$" almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [2019] to be the first "natural" complete problem for the computational class PPA, answering a decade-old open question. In this paper, we examine the extent to which the problem becomes easy to solve, if one restricts the class of valuation functions. To this end, we provide the following contributions. First, we obtain a strengthening of the PPA-hardness result of [Filos-Ratsikas and Goldberg, 2019], to the case when agents have piecewise uniform valuations with only two blocks. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in [Filos-Ratsikas and Goldberg, 2019]. Then, we consider the case of single-block (uniform) valuations and provide a parameterized polynomial time algorithm for solving $\varepsilon$-Consensus-Halving for any $\varepsilon$, as well as a polynomial-time algorithm for $\varepsilon=1/2$. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-$1/k$-Division problem [Simmons and Su, 2003]. In particular, we prove that $\varepsilon$-Consensus-$1/3$-Division is PPAD-hard.
Temporal Convolutional Attention-based Network For Sequence Modeling
Venue: arXiv cs.CL 2023
Year: 2023

With the development of feed-forward models, the default model for sequence modeling has gradually evolved to replace recurrent networks. Many powerful feed-forward models based on convolutional networks and attention mechanism were proposed and show more potential to handle sequence modeling tasks. We wonder that is there an architecture that can not only achieve an approximate substitution of recurrent network, but also absorb the advantages of feed-forward models. So we propose an exploratory architecture referred to Temporal Convolutional Attention-based Network (TCAN) which combines temporal convolutional network and attention mechanism. TCAN includes two parts, one is Temporal Attention (TA) which captures relevant features inside the sequence, the other is Enhanced Residual (ER) which extracts shallow layer's important information and transfers to deep layers. We improve the state-of-the-art results of bpc/perplexity to 30.28 on word-level PTB, 1.092 on character-level PTB, and 9.20 on WikiText-2.
Towards Backdoor Attacks and Defense in Robust Machine Learning Models
Venue: arXiv cs.CV 2023
Year: 2023

The introduction of robust optimisation has pushed the state-of-the-art in defending against adversarial attacks. Notably, the state-of-the-art projected gradient descent (PGD)-based training method has been shown to be universally and reliably effective in defending against adversarial inputs. This robustness approach uses PGD as a reliable and universal "first-order adversary". However, the behaviour of such optimisation has not been studied in the light of a fundamentally different class of attacks called backdoors. In this paper, we study how to inject and defend against backdoor attacks for robust models trained using PGD-based robust optimisation. We demonstrate that these models are susceptible to backdoor attacks. Subsequently, we observe that backdoors are reflected in the feature representation of such models. Then, this observation is leveraged to detect such backdoor-infected models via a detection technique called AEGIS. Specifically, given a robust Deep Neural Network (DNN) that is trained using PGD-based first-order adversarial training approach, AEGIS uses feature clustering to effectively detect whether such DNNs are backdoor-infected or clean. In our evaluation of several visible and hidden backdoor triggers on major classification tasks using CIFAR-10, MNIST and FMNIST datasets, AEGIS effectively detects PGD-trained robust DNNs infected with backdoors. AEGIS detects such backdoor-infected models with 91.6% accuracy (11 out of 12 tested models), without any false positives. Furthermore, AEGIS detects the targeted class in the backdoor-infected model with a reasonably low (11.1%) false positive rate. Our investigation reveals that salient features of adversarially robust DNNs could be promising to break the stealthy nature of backdoor attacks.
LIMEADE: From AI Explanations to Advice Taking
Venue: arXiv cs.IR 2023
Year: 2023

Research in human-centered AI has shown the benefits of systems that can explain their predictions. Methods that allow an AI to take advice from humans in response to explanations are similarly useful. While both capabilities are well-developed for transparent learning models (e.g., linear models and GA$^2$Ms), and recent techniques (e.g., LIME and SHAP) can generate explanations for opaque models, little attention has been given to advice methods for opaque models. This paper introduces LIMEADE, the first general framework that translates both positive and negative advice (expressed using high-level vocabulary such as that employed by post-hoc explanations) into an update to an arbitrary, underlying opaque model. We demonstrate the generality of our approach with case studies on seventy real-world models across two broad domains: image classification and text recommendation. We show our method improves accuracy compared to a rigorous baseline on the image classification domains. For the text modality, we apply our framework to a neural recommender system for scientific papers on a public website; our user study shows that our framework leads to significantly higher perceived user control, trust, and satisfaction.
Correlated Initialization for Correlated Data
Venue: arXiv cs.LG 2023
Year: 2023

Spatial data exhibits the property that nearby points are correlated. This also holds for learnt representations across layers, but not for commonly used weight initialization methods. Our theoretical analysis quantifies the learning behavior of weights of a single spatial filter. It is thus in contrast to a large body of work that discusses statistical properties of weights. It shows that uncorrelated initialization (i) might lead to poor convergence behavior and (ii) training of (some) parameters is likely subject to slow convergence. Empirical analysis shows that these findings for a single spatial filter extend to networks with many spatial filters. The impact of (correlated) initialization depends strongly on learning rates and l2-regularization.
Equilibrium Selection in Data Markets: Multiple-Principal, Multiple-Agent Problems with Non-Rivalrous Goods
Venue: arXiv cs.GT 2023
Year: 2023

There are several aspects of data markets that distinguish them from a typical commodity market: asymmetric information, the non-rivalrous nature of data, and informational externalities. Formally, this gives rise to a new class of games which we call multiple-principal, multiple-agent problem with non-rivalrous goods. Under the assumption that the principal's payoff is quasilinear in the payments given to agents, we show that there is a fundamental degeneracy in the market of non-rivalrous goods. This multiplicity of equilibria also affects common refinements of equilibrium definitions intended to uniquely select an equilibrium: both variational equilibria and normalized equilibria will be non-unique in general. This implies that most existing equilibrium concepts cannot provide predictions on the outcomes of data markets emerging today. The results support the idea that modifications to payment contracts themselves are unlikely to yield a unique equilibrium, and either changes to the models of study or new equilibrium concepts will be required to determine unique equilibria in settings with multiple principals and a non-rivalrous good.
To Be Announced
Venue: arXiv cs.LO 2023
Year: 2023

In this survey we review dynamic epistemic logics with modalities for quantification over information change. Of such logics we present complete axiomatizations, focussing on axioms involving the interaction between knowledge and such quantifiers, we report on their relative expressivity, on decidability and on the complexity of model checking and satisfiability, and on applications. We focus on open problems and new directions for research.
Zero-Shot Compositional Policy Learning via Language Grounding
Venue: arXiv cs.LG 2023
Year: 2023

Despite recent breakthroughs in reinforcement learning (RL) and imitation learning (IL), existing algorithms fail to generalize beyond the training environments. In reality, humans can adapt to new tasks quickly by leveraging prior knowledge about the world such as language descriptions. To facilitate the research on language-guided agents with domain adaption, we propose a novel zero-shot compositional policy learning task, where the environments are characterized as a composition of different attributes. Since there are no public environments supporting this study, we introduce a new research platform BabyAI++ in which the dynamics of environments are disentangled from visual appearance. At each episode, BabyAI++ provides varied vision-dynamics combinations along with corresponding descriptive texts. To evaluate the adaption capability of learned agents, a set of vision-dynamics pairings are held-out for testing on BabyAI++. Unsurprisingly, we find that current language-guided RL/IL techniques overfit to the training environments and suffer from a huge performance drop when facing unseen combinations. In response, we propose a multi-modal fusion method with an attention mechanism to perform visual language-grounding. Extensive experiments show strong evidence that language grounding is able to improve the generalization of agents across environments with varied dynamics.
Vertex Nomination in Richly Attributed Networks
Venue: arXiv cs.IR 2023
Year: 2023

Vertex nomination is a lightly-supervised network information retrieval task in which vertices of interest in one graph are used to query a second graph to discover vertices of interest in the second graph. Similar to other information retrieval tasks, the output of a vertex nomination scheme is a ranked list of the vertices in the second graph, with the heretofore unknown vertices of interest ideally concentrating at the top of the list. Vertex nomination schemes provide a useful suite of tools for efficiently mining complex networks for pertinent information. In this paper, we explore, both theoretically and practically, the dual roles of content (i.e., edge and vertex attributes) and context (i.e., network topology) in vertex nomination. We provide necessary and sufficient conditions under which vertex nomination schemes that leverage both content and context outperform schemes that leverage only content or context separately. While the joint utility of both content and context has been demonstrated empirically in the literature, the framework presented in this paper provides a novel theoretical basis for understanding the potential complementary roles of network features and topology.
Categorical Vector Space Semantics for Lambek Calculus with a Relevant Modality
Venue: arXiv cs.CL 2023
Year: 2023

We develop a categorical compositional distributional semantics for Lambek Calculus with a Relevant Modality !L*, which has a limited edition of the contraction and permutation rules. The categorical part of the semantics is a monoidal biclosed category with a coalgebra modality, very similar to the structure of a Differential Category. We instantiate this category to finite dimensional vector spaces and linear maps via "quantisation" functors and work with three concrete interpretations of the coalgebra modality. We apply the model to construct categorical and concrete semantic interpretations for the motivating example of !L*: the derivation of a phrase with a parasitic gap. The effectiveness of the concrete interpretations are evaluated via a disambiguation task, on an extension of a sentence disambiguation dataset to parasitic gap phrases, using BERT, Word2Vec, and FastText vectors and Relational tensors.