OpenRaiser/Intern-Atlas huggingface dataset:
Recurrent Neural-Linear Posterior Sampling for Nonstationary Contextual Bandits
Venue: arXiv cs.LG 2023
Year: 2023

An agent in a nonstationary contextual bandit problem should balance between exploration and the exploitation of (periodic or structured) patterns present in its previous experiences. Handcrafting an appropriate historical context is an attractive alternative to transform a nonstationary problem into a stationary problem that can be solved efficiently. However, even a carefully designed historical context may introduce spurious relationships or lack a convenient representation of crucial information. In order to address these issues, we propose an approach that learns to represent the relevant context for a decision based solely on the raw history of interactions between the agent and the environment. This approach relies on a combination of features extracted by recurrent neural networks with a contextual linear bandit algorithm based on posterior sampling. Our experiments on a diverse selection of contextual and noncontextual nonstationary problems show that our recurrent approach consistently outperforms its feedforward counterpart, which requires handcrafted historical contexts, while being more widely applicable than conventional nonstationary bandit algorithms. Although it is very difficult to provide theoretical performance guarantees for our new approach, we also prove a novel regret bound for linear posterior sampling with measurement error that may serve as a foundation for future theoretical work.
Age-Limited Capacity of Massive MIMO
Venue: arXiv cs.IT 2023
Year: 2023

We investigate the age-limited capacity of the Gaussian many channel with total $N$ users, out of which a random subset of $K_{a}$ users are active in any transmission period, and a large-scale antenna array at the base station (BS). In an uplink scenario where the transmission power is fixed among the users, we consider the setting in which both the number of users, $N$, and the number of antennas at the BS, $M$, are allowed to grow large at a fixed ratio $ζ= {M}/{N}$. Assuming perfect channel state information (CSI) at the receiver, we derive the achievability bound under maximal ratio combining. As the number of active users, $K_{a}$, increases, the achievable spectral efficiency is found to increase monotonically to a limit $\log_2\left(1+\frac{M}{K_{a}}\right)$. Further extensions of the analysis to the zero-forcing receiver as well as imperfect CSI are provided, demonstrating the channel estimation penalty in terms of the mean squared error in estimation. Using the age of information (AoI) metric, first coined by Kaul et al., as our measure of data timeliness or freshness, we investigate the trade-offs between the AoI and spectral efficiency in the context massive connectivity with large-scale receiving antenna arrays. As an extension of Liu and Yu, based on our large system analysis, we provide an accurate characterization of the asymptotic (finite system size) spectral efficiency as a function of the number of antennas and the number of users, the attempt probability, and the AoI. It is found that while the spectral efficiency can be made large, the penalty is an increase in the minimum AoI obtainable. The proposed achievability bound is further compared against recent massive MIMO-based massive unsourced random access (URA) schemes.
UnRectDepthNet: Self-Supervised Monocular Depth Estimation using a Generic Framework for Handling Common Camera Distortion Models
Venue: arXiv cs.CV 2023
Year: 2023

In classical computer vision, rectification is an integral part of multi-view depth estimation. It typically includes epipolar rectification and lens distortion correction. This process simplifies the depth estimation significantly, and thus it has been adopted in CNN approaches. However, rectification has several side effects, including a reduced field of view (FOV), resampling distortion, and sensitivity to calibration errors. The effects are particularly pronounced in case of significant distortion (e.g., wide-angle fisheye cameras). In this paper, we propose a generic scale-aware self-supervised pipeline for estimating depth, euclidean distance, and visual odometry from unrectified monocular videos. We demonstrate a similar level of precision on the unrectified KITTI dataset with barrel distortion comparable to the rectified KITTI dataset. The intuition being that the rectification step can be implicitly absorbed within the CNN model, which learns the distortion model without increasing complexity. Our approach does not suffer from a reduced field of view and avoids computational costs for rectification at inference time. To further illustrate the general applicability of the proposed framework, we apply it to wide-angle fisheye cameras with 190$^\circ$ horizontal field of view. The training framework UnRectDepthNet takes in the camera distortion model as an argument and adapts projection and unprojection functions accordingly. The proposed algorithm is evaluated further on the KITTI rectified dataset, and we achieve state-of-the-art results that improve upon our previous work FisheyeDistanceNet. Qualitative results on a distorted test scene video sequence indicate excellent performance https://youtu.be/K6pbx3bU4Ss.
Smart Choices and the Selection Monad
Venue: arXiv cs.LO 2023
Year: 2023

Describing systems in terms of choices and their resulting costs and rewards offers the promise of freeing algorithm designers and programmers from specifying how those choices should be made; in implementations, the choices can be realized by optimization techniques and, increasingly, by machine-learning methods. We study this approach from a programming-language perspective. We define two small languages that support decision-making abstractions: one with choices and rewards, and the other additionally with probabilities. We give both operational and denotational semantics. In the case of the second language we consider three denotational semantics, with varying degrees of correlation between possible program values and expected rewards. The operational semantics combine the usual semantics of standard constructs with optimization over spaces of possible execution strategies. The denotational semantics, which are compositional, rely on the selection monad, to handle choice, augmented with an auxiliary monad to handle other effects, such as rewards or probability. We establish adequacy theorems that the two semantics coincide in all cases. We also prove full abstraction at base types, with varying notions of observation in the probabilistic case corresponding to the various degrees of correlation. We present axioms for choice combined with rewards and probability, establishing completeness at base types for the case of rewards without probability.
Budget-balanced and strategy-proof auctions for multi-passenger ridesharing
Venue: arXiv cs.GT 2023
Year: 2023

Ridesharing and ridesourcing services have become widespread, and pricing the rides is a crucial problem for these systems. We propose and analyze a budget-balanced and strategy-proof auction, the Weighted Minimum Surplus (WMS) auction, for the dynamic ridesharing problem with multiple passengers per ride. Under the assumption of downward closed alternatives, we obtain lower bounds for the surplus welfare and surplus profit of the WMS auction. We also propose and analyze a budget-balanced version of the well-known VCG mechanism, the $\mathrm{VCG}_s$. Encouraging experimental results were obtained for both the WMS auction and the $\mathrm{VCG}_s$.
Anomaly Awareness
Venue: arXiv cs.LG 2023
Year: 2023

We present a new algorithm for anomaly detection called Anomaly Awareness. The algorithm learns about normal events while being made aware of the anomalies through a modification of the cost function. We show how this method works in different Particle Physics situations and in standard Computer Vision tasks. For example, we apply the method to images from a Fat Jet topology generated by Standard Model Top and QCD events, and test it against an array of new physics scenarios, including Higgs production with EFT effects and resonances decaying into two, three or four subjets. We find that the algorithm is effective identifying anomalies not seen before, and becomes robust as we make it aware of a varied-enough set of anomalies.
A Deep Learning Framework for Generation and Analysis of Driving Scenario Trajectories
Venue: arXiv cs.CV 2023
Year: 2023

We propose a unified deep learning framework for the generation and analysis of driving scenario trajectories, and validate its effectiveness in a principled way. To model and generate scenarios of trajectories with different lengths, we develop two approaches. First, we adapt the Recurrent Conditional Generative Adversarial Networks (RC-GAN) by conditioning on the length of the trajectories. This provides us the flexibility to generate variable-length driving trajectories, a desirable feature for scenario test case generation in the verification of autonomous driving. Second, we develop an architecture based on Recurrent Autoencoder with GANs to obviate the variable length issue, wherein we train a GAN to learn/generate the latent representations of original trajectories. In this approach, we train an integrated feed-forward neural network to estimate the length of the trajectories to be able to bring them back from the latent space representation. In addition to trajectory generation, we employ the trained autoencoder as a feature extractor, for the purpose of clustering and anomaly detection, to obtain further insights into the collected scenario dataset. We experimentally investigate the performance of the proposed framework on real-world scenario trajectories obtained from in-field data collection.
Visual Analysis of Discrimination in Machine Learning
Venue: arXiv cs.HC 2023
Year: 2023

The growing use of automated decision-making in critical applications, such as crime prediction and college admission, has raised questions about fairness in machine learning. How can we decide whether different treatments are reasonable or discriminatory? In this paper, we investigate discrimination in machine learning from a visual analytics perspective and propose an interactive visualization tool, DiscriLens, to support a more comprehensive analysis. To reveal detailed information on algorithmic discrimination, DiscriLens identifies a collection of potentially discriminatory itemsets based on causal modeling and classification rules mining. By combining an extended Euler diagram with a matrix-based visualization, we develop a novel set visualization to facilitate the exploration and interpretation of discriminatory itemsets. A user study shows that users can interpret the visually encoded information in DiscriLens quickly and accurately. Use cases demonstrate that DiscriLens provides informative guidance in understanding and reducing algorithmic discrimination.
Phase Transition of the k-Majority Dynamics in Biased Communication Models
Venue: arXiv cs.DC 2023
Year: 2023

Consider a graph where each of the $n$ nodes is either in state $\mathcal{R}$ or $\mathcal{B}$. Herein, we analyze the \emph{synchronous $k$-Majority dynamics}, where in each discrete-time round nodes simultaneously sample $k$ neighbors uniformly at random with replacement and adopt the majority state among those of the nodes in the sample (breaking ties uniformly at random). Differently from previous work, we study the robustness of the $k$-Majority in \emph{maintaining a $\mathcal{R}$ majority}, when the dynamics is subject to two forms of \emph{bias} toward state $\mathcal{B}$. The bias models an external agent that attempts to subvert the initial majority by altering the communication between nodes, with a probability of success $p$ in each round: in the first form of bias, the agent tries to alter the communication links by transmitting state $\mathcal{B}$; in the second form of bias, the agent tries to corrupt nodes directly by making them update to $\mathcal{B}$. Our main result shows a \emph{sharp phase transition} in both forms of bias. By considering initial configurations in which every node has probability $q \in (\frac{1}{2},1]$ of being in state $\mathcal{R}$, we prove that for every $k\geq3$ there exists a critical value $p_{k,q}^*$ such that, with high probability, the external agent is able to subvert the initial majority either in $n^{ω(1)}$ rounds, if $p<p_{k,q}^*$, or in $O(1)$ rounds, if $p>p_{k,q}^*$. When $k<3$, instead, no phase transition phenomenon is observed and the disruption happens in $O(1)$ rounds for $p>0$.
Towards a new Social Choice Theory
Venue: arXiv cs.AI 2023
Year: 2023

Social choice is the theory about collective decision towards social welfare starting from individual opinions, preferences, interests or welfare. The field of Computational Social Welfare is somewhat recent and it is gaining impact in the Artificial Intelligence Community. Classical literature makes the assumption of single-peaked preferences, i.e. there exist a order in the preferences and there is a global maximum in this order. This year some theoretical results were published about Two-stage Approval Voting Systems (TAVs), Multi-winner Selection Rules (MWSR) and Incomplete (IPs) and Circular Preferences (CPs). The purpose of this paper is three-fold: Firstly, I want to introduced Social Choice Optimisation as a generalisation of TAVs where there is a max stage and a min stage implementing thus a Minimax, well-known Artificial Intelligence decision-making rule to minimize hindering towards a (Social) Goal. Secondly, I want to introduce, following my Open Standardization and Open Integration Theory (in refinement process) put in practice in my dissertation, the Open Standardization of Social Inclusion, as a global social goal of Social Choice Optimization.
vWitness: Certifying Web Page Interactions with Computer Vision
Venue: arXiv cs.CR 2023
Year: 2023

Web servers service client requests, some of which might cause the web server to perform security-sensitive operations (e.g. money transfer, voting). An attacker may thus forge or maliciously manipulate such requests by compromising a web client. Unfortunately, a web server has no way of knowing whether the client from which it receives a request has been compromised or not -- current "best practice" defenses such as user authentication or network encryption cannot aid a server as they all assume web client integrity. To address this shortcoming, we propose vWitness, which "witnesses" the interactions of a user with a web page and certifies whether they match a specification provided by the web server, enabling the web server to know that the web request is user-intended. The main challenge that vWitness overcomes is that even benign clients introduce unpredictable variations in the way they render web pages. vWitness differentiates between these benign variations and malicious manipulation using computer vision, allowing it to certify to the web server that 1) the web page user interface is properly displayed 2) observed user interactions are used to construct the web request. Our vWitness prototype achieves compatibility with modern web pages, is resilient to adversarial example attacks and is accurate and performant -- vWitness achieves 99.97% accuracy and adds 197ms of overhead to the entire interaction session in the average case.
A Survey on the Evolution of Stream Processing Systems
Venue: arXiv cs.DC 2023
Year: 2023

Stream processing has been an active research field for more than 20 years, but it is now witnessing its prime time due to recent successful efforts by the research community and numerous worldwide open-source communities. This survey provides a comprehensive overview of fundamental aspects of stream processing systems and their evolution in the functional areas of out-of-order data management, state management, fault tolerance, high availability, load management, elasticity, and reconfiguration. We review noteworthy past research findings, outline the similarities and differences between early ('00-'10) and modern ('11-'22) streaming systems, and discuss recent trends and open problems.
Verifying Tight Logic Programs with anthem and Vampire
Venue: arXiv cs.LO 2023
Year: 2023

This paper continues the line of research aimed at investigating the relationship between logic programs and first-order theories. We extend the definition of program completion to programs with input and output in a subset of the input language of the ASP grounder gringo, study the relationship between stable models and completion in this context, and describe preliminary experiments with the use of two software tools, anthem and vampire, for verifying the correctness of programs with input and output. Proofs of theorems are based on a lemma that relates the semantics of programs studied in this paper to stable models of first-order formulas. Under consideration for acceptance in TPLP.
Computation Offloading in Heterogeneous Vehicular Edge Networks: On-line and Off-policy Bandit Solutions
Venue: arXiv cs.NI 2023
Year: 2023

With the rapid advancement of Intelligent Transportation Systems (ITS) and vehicular communications, Vehicular Edge Computing (VEC) is emerging as a promising technology to support low-latency ITS applications and services. In this paper, we consider the computation offloading problem from mobile vehicles/users in a heterogeneous VEC scenario, and focus on the network- and base station selection problems, where different networks have different traffic loads. In a fast-varying vehicular environment, computation offloading experience of users is strongly affected by the latency due to the congestion at the edge computing servers co-located with the base stations. However, as a result of the non-stationary property of such an environment and also information shortage, predicting this congestion is an involved task. To address this challenge, we propose an on-line learning algorithm and an off-policy learning algorithm based on multi-armed bandit theory. To dynamically select the least congested network in a piece-wise stationary environment, these algorithms predict the latency that the offloaded tasks experience using the offloading history. In addition, to minimize the task loss due to the mobility of the vehicles, we develop a method for base station selection. Moreover, we propose a relaying mechanism for the selected network, which operates based on the sojourn time of the vehicles. Through intensive numerical analysis, we demonstrate that the proposed learning-based solutions adapt to the traffic changes of the network by selecting the least congested network, thereby reducing the latency of offloaded tasks. Moreover, we demonstrate that the proposed joint base station selection and the relaying mechanism minimize the task loss in a vehicular environment.
An Overview of Deep Learning Architectures in Few-Shot Learning Domain
Venue: arXiv cs.CV 2023
Year: 2023

Since 2012, Deep learning has revolutionized Artificial Intelligence and has achieved state-of-the-art outcomes in different domains, ranging from Image Classification to Speech Generation. Though it has many potentials, our current architectures come with the pre-requisite of large amounts of data. Few-Shot Learning (also known as one-shot learning) is a sub-field of machine learning that aims to create such models that can learn the desired objective with less data, similar to how humans learn. In this paper, we have reviewed some of the well-known deep learning-based approaches towards few-shot learning. We have discussed the recent achievements, challenges, and possibilities of improvement of few-shot learning based deep learning architectures. Our aim for this paper is threefold: (i) Give a brief introduction to deep learning architectures for few-shot learning with pointers to core references. (ii) Indicate how deep learning has been applied to the low-data regime, from data preparation to model training. and, (iii) Provide a starting point for people interested in experimenting and perhaps contributing to the field of few-shot learning by pointing out some useful resources and open-source code. Our code is available at Github: https://github.com/shruti-jadon/Hands-on-One-Shot-Learning.
Training Matters: Unlocking Potentials of Deeper Graph Convolutional Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

The performance limit of Graph Convolutional Networks (GCNs) and the fact that we cannot stack more of them to increase the performance, which we usually do for other deep learning paradigms, are pervasively thought to be caused by the limitations of the GCN layers, including insufficient expressive power, etc. However, if so, for a fixed architecture, it would be unlikely to lower the training difficulty and to improve performance by changing only the training procedure, which we show in this paper not only possible but possible in several ways. This paper first identify the training difficulty of GCNs from the perspective of graph signal energy loss. More specifically, we find that the loss of energy in the backward pass during training nullifies the learning of the layers closer to the input. Then, we propose several methodologies to mitigate the training problem by slightly modifying the GCN operator, from the energy perspective. After empirical validation, we confirm that these changes of operator lead to significant decrease in the training difficulties and notable performance boost, without changing the composition of parameters. With these, we conclude that the root cause of the problem is more likely the training difficulty than the others.
Machine Semiotics
Venue: arXiv cs.CL 2023
Year: 2023

Recognizing a basic difference between the semiotics of humans and machines presents a possibility to overcome the shortcomings of current speech assistive devices. For the machine, the meaning of a (human) utterance is defined by its own scope of actions. Machines, thus, do not need to understand the conventional meaning of an utterance. Rather, they draw conversational implicatures in the sense of (neo-)Gricean pragmatics. For speech assistive devices, the learning of machine-specific meanings of human utterances, i.e. the fossilization of conversational implicatures into conventionalized ones by trial and error through lexicalization appears to be sufficient. Using the quite trivial example of a cognitive heating device, we show that - based on dynamic semantics - this process can be formalized as the reinforcement learning of utterance-meaning pairs (UMP).
Learning Node Representations against Perturbations
Venue: arXiv cs.LG 2023
Year: 2023

Recent graph neural networks (GNN) has achieved remarkable performance in node representation learning. One key factor of GNN's success is the \emph{smoothness} property on node representations. Despite this, most GNN models are fragile to the perturbations on graph inputs and could learn unreliable node representations. In this paper, we study how to learn node representations against perturbations in GNN. Specifically, we consider that a node representation should remain stable under slight perturbations on the input, and node representations from different structures should be identifiable, which two are termed as the \emph{stability} and \emph{identifiability} on node representations, respectively. To this end, we propose a novel model called Stability-Identifiability GNN Against Perturbations (SIGNNAP) that learns reliable node representations in an unsupervised manner. SIGNNAP formalizes the \emph{stability} and \emph{identifiability} by a contrastive objective and preserves the \emph{smoothness} with existing GNN backbones. The proposed method is a generic framework that can be equipped with many other backbone models (e.g. GCN, GraphSage and GAT). Extensive experiments on six benchmarks under both transductive and inductive learning setups of node classification demonstrate the effectiveness of our method. Codes and data are available online:~\url{https://github.com/xuChenSJTU/SIGNNAP-master-online}