OpenRaiser/Intern-Atlas huggingface dataset:
Mechanism Design for Perturbation Stable Combinatorial Auctions
Venue: arXiv cs.GT 2020
Year: 2020

Motivated by recent research on combinatorial markets with endowed valuations by (Babaioff et al., EC 2018) and (Ezra et al., EC 2020), we introduce a notion of perturbation stability in Combinatorial Auctions (CAs) and study the extend to which stability helps in social welfare maximization and mechanism design. A CA is $γ\textit{-stable}$ if the optimal solution is resilient to inflation, by a factor of $γ\geq 1$, of any bidder's valuation for any single item. On the positive side, we show how to compute efficiently an optimal allocation for 2-stable subadditive valuations and that a Walrasian equilibrium exists for 2-stable submodular valuations. Moreover, we show that a Parallel 2nd Price Auction (P2A) followed by a demand query for each bidder is truthful for general subadditive valuations and results in the optimal allocation for 2-stable submodular valuations. To highlight the challenges behind optimization and mechanism design for stable CAs, we show that a Walrasian equilibrium may not exist for $γ$-stable XOS valuations for any $γ$, that a polynomial-time approximation scheme does not exist for $(2-ε)$-stable submodular valuations, and that any DSIC mechanism that computes the optimal allocation for stable CAs and does not use demand queries must use exponentially many value queries. We conclude with analyzing the Price of Anarchy of P2A and Parallel 1st Price Auctions (P1A) for CAs with stable submodular and XOS valuations. Our results indicate that the quality of equilibria of simple non-truthful auctions improves only for $γ$-stable instances with $γ\geq 3$.
On the Learnability of Concepts: With Applications to Comparing Word Embedding Algorithms
Venue: arXiv cs.CL 2020
Year: 2020

Word Embeddings are used widely in multiple Natural Language Processing (NLP) applications. They are coordinates associated with each word in a dictionary, inferred from statistical properties of these words in a large corpus. In this paper we introduce the notion of "concept" as a list of words that have shared semantic content. We use this notion to analyse the learnability of certain concepts, defined as the capability of a classifier to recognise unseen members of a concept after training on a random subset of it. We first use this method to measure the learnability of concepts on pretrained word embeddings. We then develop a statistical analysis of concept learnability, based on hypothesis testing and ROC curves, in order to compare the relative merits of various embedding algorithms using a fixed corpora and hyper parameters. We find that all embedding methods capture the semantic content of those word lists, but fastText performs better than the others.
Vision-Aided Dynamic Blockage Prediction for 6G Wireless Communication Networks
Venue: arXiv cs.CV 2020
Year: 2020

Unlocking the full potential of millimeter-wave and sub-terahertz wireless communication networks hinges on realizing unprecedented low-latency and high-reliability requirements. The challenge in meeting those requirements lies partly in the sensitivity of signals in the millimeter-wave and sub-terahertz frequency ranges to blockages. One promising way to tackle that challenge is to help a wireless network develop a sense of its surrounding using machine learning. This paper attempts to do that by utilizing deep learning and computer vision. It proposes a novel solution that proactively predicts \textit{dynamic} link blockages. More specifically, it develops a deep neural network architecture that learns from observed sequences of RGB images and beamforming vectors how to predict possible future link blockages. The proposed architecture is evaluated on a publicly available dataset that represents a synthetic dynamic communication scenario with multiple moving users and blockages. It scores a link-blockage prediction accuracy in the neighborhood of 86\%, a performance that is unlikely to be matched without utilizing visual data.
Delta Schema Network in Model-based Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

This work is devoted to unresolved problems of Artificial General Intelligence - the inefficiency of transfer learning. One of the mechanisms that are used to solve this problem in the area of reinforcement learning is a model-based approach. In the paper we are expanding the schema networks method which allows to extract the logical relationships between objects and actions from the environment data. We present algorithms for training a Delta Schema Network (DSN), predicting future states of the environment and planning actions that will lead to positive reward. DSN shows strong performance of transfer learning on the classic Atari game environment.
You Only Spike Once: Improving Energy-Efficient Neuromorphic Inference to ANN-Level Accuracy
Venue: arXiv cs.NE 2020
Year: 2020

In the past decade, advances in Artificial Neural Networks (ANNs) have allowed them to perform extremely well for a wide range of tasks. In fact, they have reached human parity when performing image recognition, for example. Unfortunately, the accuracy of these ANNs comes at the expense of a large number of cache and/or memory accesses and compute operations. Spiking Neural Networks (SNNs), a type of neuromorphic, or brain-inspired network, have recently gained significant interest as power-efficient alternatives to ANNs, because they are sparse, accessing very few weights, and typically only use addition operations instead of the more power-intensive multiply-and-accumulate (MAC) operations. The vast majority of neuromorphic hardware designs support rate-encoded SNNs, where the information is encoded in spike rates. Rate-encoded SNNs could be seen as inefficient as an encoding scheme because it involves the transmission of a large number of spikes. A more efficient encoding scheme, Time-To-First-Spike (TTFS) encoding, encodes information in the relative time of arrival of spikes. While TTFS-encoded SNNs are more efficient than rate-encoded SNNs, they have, up to now, performed poorly in terms of accuracy compared to previous methods. Hence, in this work, we aim to overcome the limitations of TTFS-encoded neuromorphic systems. To accomplish this, we propose: (1) a novel optimization algorithm for TTFS-encoded SNNs converted from ANNs and (2) a novel hardware accelerator for TTFS-encoded SNNs, with a scalable and low-power design. Overall, our work in TTFS encoding and training improves the accuracy of SNNs to achieve state-of-the-art results on MNIST MLPs, while reducing power consumption by 1.46$\times$ over the state-of-the-art neuromorphic hardware.
ZKPs: Does This Make The Cut? Recent Advances and Success of Zero-Knowledge Security Protocols
Venue: arXiv cs.CR 2020
Year: 2020

How someone can get health insurance without sharing his health information? How you can get a loan without disclosing your credit score? There is a method to certify certain attributes of various data, either this is health metrics or finance information, without revealing the data itself or any other kind of personal data. This method is known as zero-knowledge proofs. Zero-Knowledge techniques are mathematical methods used to verify things without sharing or revealing underlying data. Zero-Knowledge protocols have vast applications from simple identity schemes and blockchains to defense research programs and nuclear arms control
Stochastic Network Utility Maximization with Unknown Utilities: Multi-Armed Bandits Approach
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we study a novel Stochastic Network Utility Maximization (NUM) problem where the utilities of agents are unknown. The utility of each agent depends on the amount of resource it receives from a network operator/controller. The operator desires to do a resource allocation that maximizes the expected total utility of the network. We consider threshold type utility functions where each agent gets non-zero utility if the amount of resource it receives is higher than a certain threshold. Otherwise, its utility is zero (hard real-time). We pose this NUM setup with unknown utilities as a regret minimization problem. Our goal is to identify a policy that performs as `good' as an oracle policy that knows the utilities of agents. We model this problem setting as a bandit setting where feedback obtained in each round depends on the resource allocated to the agents. We propose algorithms for this novel setting using ideas from Multiple-Play Multi-Armed Bandits and Combinatorial Semi-Bandits. We show that the proposed algorithm is optimal when all agents have the same utility. We validate the performance guarantees of our proposed algorithms through numerical experiments.
Adversarial Examples Detection and Analysis with Layer-wise Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

We present a mechanism for detecting adversarial examples based on data representations taken from the hidden layers of the target network. For this purpose, we train individual autoencoders at intermediate layers of the target network. This allows us to describe the manifold of true data and, in consequence, decide whether a given example has the same characteristics as true data. It also gives us insight into the behavior of adversarial examples and their flow through the layers of a deep neural network. Experimental results show that our method outperforms the state of the art in supervised and unsupervised settings.
Socially Fair k-Means Clustering
Venue: arXiv cs.LG 2020
Year: 2020

We show that the popular k-means clustering algorithm (Lloyd's heuristic), used for a variety of scientific data, can result in outcomes that are unfavorable to subgroups of data (e.g., demographic groups). Such biased clusterings can have deleterious implications for human-centric applications such as resource allocation. We present a fair k-means objective and algorithm to choose cluster centers that provide equitable costs for different groups. The algorithm, Fair-Lloyd, is a modification of Lloyd's heuristic for k-means, inheriting its simplicity, efficiency, and stability. In comparison with standard Lloyd's, we find that on benchmark datasets, Fair-Lloyd exhibits unbiased performance by ensuring that all groups have equal costs in the output k-clustering, while incurring a negligible increase in running time, thus making it a viable fair option wherever k-means is currently used.
Extensively Matching for Few-shot Learning Event Detection
Venue: arXiv cs.CL 2020
Year: 2020

Current event detection models under super-vised learning settings fail to transfer to newevent types. Few-shot learning has not beenexplored in event detection even though it al-lows a model to perform well with high gener-alization on new event types. In this work, weformulate event detection as a few-shot learn-ing problem to enable to extend event detec-tion to new event types. We propose two novelloss factors that matching examples in the sup-port set to provide more training signals to themodel. Moreover, these training signals can beapplied in many metric-based few-shot learn-ing models. Our extensive experiments on theACE-2005 dataset (under a few-shot learningsetting) show that the proposed method can im-prove the performance of few-shot learning
Interpreting the Latent Space of GANs via Correlation Analysis for Controllable Concept Manipulation
Venue: arXiv cs.CV 2020
Year: 2020

Generative adversarial nets (GANs) have been successfully applied in many fields like image generation, inpainting, super-resolution and drug discovery, etc., by now, the inner process of GANs is far from been understood. To get deeper insight of the intrinsic mechanism of GANs, in this paper, a method for interpreting the latent space of GANs by analyzing the correlation between latent variables and the corresponding semantic contents in generated images is proposed. Unlike previous methods that focus on dissecting models via feature visualization, the emphasis of this work is put on the variables in latent space, i.e. how the latent variables affect the quantitative analysis of generated results. Given a pretrained GAN model with weights fixed, the latent variables are intervened to analyze their effect on the semantic content in generated images. A set of controlling latent variables can be derived for specific content generation, and the controllable semantic content manipulation be achieved. The proposed method is testified on the datasets Fashion-MNIST and UT Zappos50K, experiment results show its effectiveness.
Self-supervised Learning on Graphs: Deep Insights and New Direction
Venue: arXiv cs.LG 2020
Year: 2020

The success of deep learning notoriously requires larger amounts of costly annotated data. This has led to the development of self-supervised learning (SSL) that aims to alleviate this limitation by creating domain specific pretext tasks on unlabeled data. Simultaneously, there are increasing interests in generalizing deep learning to the graph domain in the form of graph neural networks (GNNs). GNNs can naturally utilize unlabeled nodes through the simple neighborhood aggregation that is unable to thoroughly make use of unlabeled nodes. Thus, we seek to harness SSL for GNNs to fully exploit the unlabeled data. Different from data instances in the image and text domains, nodes in graphs present unique structure information and they are inherently linked indicating not independent and identically distributed (or i.i.d.). Such complexity is a double-edged sword for SSL on graphs. On the one hand, it determines that it is challenging to adopt solutions from the image and text domains to graphs and dedicated efforts are desired. On the other hand, it provides rich information that enables us to build SSL from a variety of perspectives. Thus, in this paper, we first deepen our understandings on when, why, and which strategies of SSL work with GNNs by empirically studying numerous basic SSL pretext tasks on graphs. Inspired by deep insights from the empirical studies, we propose a new direction SelfTask to build advanced pretext tasks that are able to achieve state-of-the-art performance on various real-world datasets. The specific experimental settings to reproduce our results can be found in \url{https://github.com/ChandlerBang/SelfTask-GNN}.
MIMICS: A Large-Scale Data Collection for Search Clarification
Venue: arXiv cs.IR 2020
Year: 2020

Search clarification has recently attracted much attention due to its applications in search engines. It has also been recognized as a major component in conversational information seeking systems. Despite its importance, the research community still feels the lack of a large-scale data for studying different aspects of search clarification. In this paper, we introduce MIMICS, a collection of search clarification datasets for real web search queries sampled from the Bing query logs. Each clarification in MIMICS is generated by a Bing production algorithm and consists of a clarifying question and up to five candidate answers. MIMICS contains three datasets: (1) MIMICS-Click includes over 400k unique queries, their associated clarification panes, and the corresponding aggregated user interaction signals (i.e., clicks). (2) MIMICS-ClickExplore is an exploration data that includes aggregated user interaction signals for over 60k unique queries, each with multiple clarification panes. (3) MIMICS-Manual includes over 2k unique real search queries. Each query-clarification pair in this dataset has been manually labeled by at least three trained annotators. It contains graded quality labels for the clarifying question, the candidate answer set, and the landing result page for each candidate answer. MIMICS is publicly available for research purposes, thus enables researchers to study a number of tasks related to search clarification, including clarification generation and selection, user engagement prediction for clarification, click models for clarification, and analyzing user interactions with search clarification.
Unsupervised Meta-Learning through Latent-Space Interpolation in Generative Models
Venue: arXiv cs.LG 2020
Year: 2020

Unsupervised meta-learning approaches rely on synthetic meta-tasks that are created using techniques such as random selection, clustering and/or augmentation. Unfortunately, clustering and augmentation are domain-dependent, and thus they require either manual tweaking or expensive learning. In this work, we describe an approach that generates meta-tasks using generative models. A critical component is a novel approach of sampling from the latent space that generates objects grouped into synthetic classes forming the training and validation data of a meta-task. We find that the proposed approach, LAtent Space Interpolation Unsupervised Meta-learning (LASIUM), outperforms or is competitive with current unsupervised learning baselines on few-shot classification tasks on the most widely used benchmark datasets. In addition, the approach promises to be applicable without manual tweaking over a wider range of domains than previous approaches.
Robust Unsupervised Learning of Temporal Dynamic Interactions
Venue: arXiv cs.LG 2020
Year: 2020

Robust representation learning of temporal dynamic interactions is an important problem in robotic learning in general and automated unsupervised learning in particular. Temporal dynamic interactions can be described by (multiple) geometric trajectories in a suitable space over which unsupervised learning techniques may be applied to extract useful features from raw and high-dimensional data measurements. Taking a geometric approach to robust representation learning for temporal dynamic interactions, it is necessary to develop suitable metrics and a systematic methodology for comparison and for assessing the stability of an unsupervised learning method with respect to its tuning parameters. Such metrics must account for the (geometric) constraints in the physical world as well as the uncertainty associated with the learned patterns. In this paper we introduce a model-free metric based on the Procrustes distance for robust representation learning of interactions, and an optimal transport based distance metric for comparing between distributions of interaction primitives. These distance metrics can serve as an objective for assessing the stability of an interaction learning algorithm. They are also used for comparing the outcomes produced by different algorithms. Moreover, they may also be adopted as an objective function to obtain clusters and representative interaction primitives. These concepts and techniques will be introduced, along with mathematical properties, while their usefulness will be demonstrated in unsupervised learning of vehicle-to-vechicle interactions extracted from the Safety Pilot database, the world's largest database for connected vehicles.
GNSS Spoofing Detection via Opportunistic IRIDIUM Signals
Venue: arXiv cs.CR 2020
Year: 2020

In this paper, we study the privately-own IRIDIUM satellite constellation, to provide a location service that is independent of the GNSS. In particular, we apply our findings to propose a new GNSS spoofing detection solution, exploiting unencrypted IRIDIUM Ring Alert (IRA) messages that are broadcast by IRIDIUM satellites. We firstly reverse-engineer many parameters of the IRIDIUM satellite constellation, such as the satellites speed, packet interarrival times, maximum satellite coverage, satellite pass duration, and the satellite beam constellation, to name a few. Later, we adopt the aforementioned statistics to create a detailed model of the satellite network. Subsequently, we propose a solution to detect unintended deviations of a target user from his path, due to GNSS spoofing attacks. We show that our solution can be used efficiently and effectively to verify the position estimated from standard GNSS satellite constellation, and we provide constraints and parameters to fit several application scenarios. All the results reported in this paper, while showing the quality and viability of our proposal, are supported by real data. In particular, we have collected and analyzed hundreds of thousands of IRA messages, thanks to a measurement campaign lasting several days. All the collected data ($1000+$ hours) have been made available to the research community. Our solution is particularly suitable for unattended scenarios such as deserts, rural areas, or open seas, where standard spoofing detection techniques resorting to crowd-sourcing cannot be used due to deployment limitations. Moreover, contrary to competing solutions, our approach does not resort to physical-layer information, dedicated hardware, or multiple receiving stations, while exploiting only a single receiving antenna and publicly-available IRIDIUM transmissions. Finally, novel research directions are also highlighted.
Quantifying Assurance in Learning-enabled Systems
Venue: arXiv cs.SE 2020
Year: 2020

Dependability assurance of systems embedding machine learning(ML) components---so called learning-enabled systems (LESs)---is a key step for their use in safety-critical applications. In emerging standardization and guidance efforts, there is a growing consensus in the value of using assurance cases for that purpose. This paper develops a quantitative notion of assurance that an LES is dependable, as a core component of its assurance case, also extending our prior work that applied to ML components. Specifically, we characterize LES assurance in the form of assurance measures: a probabilistic quantification of confidence that an LES possesses system-level properties associated with functional capabilities and dependability attributes. We illustrate the utility of assurance measures by application to a real world autonomous aviation system, also describing their role both in i) guiding high-level, runtime risk mitigation decisions and ii) as a core component of the associated dynamic assurance case.
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
Venue: arXiv cs.DS 2020
Year: 2020

A graph operation that {\em contracts edges} is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting $k$ edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this paper, we study the \textsc{$\cal F$-Contraction} problem, where $\cal F$ is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph $G$ and an integer $k$, \textsc{ $\cal F$-Contraction} asks whether there exists $X \subseteq E(G)$ such that $G/X \in \cal F$ and $|X| \leq k$. Here, $G/X$ is the graph obtained from $G$ by contracting edges in $X$. We obtain the following results for the \textsc{ $\cal F$-Contraction} problem. $(1)$ We show that \textsc{Clique Contraction} admits a polynomial-size approximate kernelization scheme (\textsf{PSAKS}). $(2)$ We give a $(2+ε)$-approximate polynomial kernel for \textsc{Split Contraction} (which also implies a factor $(2+ε)$-\FPT-approximation algorithm for \textsc{ Split Contraction}). Furthermore, we show that, assuming \textsf{ Gap-ETH}, there is no $\left(\frac{5}{4}-δ\right)$-\FPT-approximation algorithm for \textsc{Split Contraction}. Here, $ε, δ>0$ are fixed constants. $(3)$ \textsc{Chordal Contraction} is known to be \WTH. We complement this result by observing that the existing \textsf{W[2]-hardness} reduction can be adapted to show that, assuming \FPT $\neq$ \textsf{W[1]}, there is no $F(k)$-\FPT-approximation algorithm for \textsc{Chordal Contraction}. Here, $F(k)$ is an arbitrary function depending on $k$ alone.