OpenRaiser/Intern-Atlas huggingface dataset:
On the Relativized Alon Second Eigenvalue Conjecture I: Main Theorems, Examples, and Outline of Proof
Venue: arXiv cs.DM 2019
Year: 2019

This is the first in a series of six articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. Many of the techniques we develop hold whether or not the base graph is regular. Our first main theorem in this series of articles is that if the base graph is $d$-regular, then for any $ε>0$, as the degree, $n$, of the covering map tends to infinity, some new adjacency eigenvalue of the map is larger in absolute value that $2(d-1)^{1/2}+ε$ with probability at most order $1/n$. Our second main theorem is that if, in addition, the base graph is Ramanujan, then this probability is bounded above and below by $1/n$ to the power of a positive integer that we call the {\em tangle power} of the model, i.e., of the probability spaces of random covering maps of degree $n$. The tangle power is fairly easy to bound from below, and at times to compute exactly; it measures the probability that certain {\em tangles} appear in the random covering graph, where a {\em tangle} is a local event that forces the covering graph to have a new eigenvalue strictly larger than $2(d-1)^{1/2}$. Our main theorems are relativizations of Alon's conjecture on the second eigenvalue of random regular graphs of large degree. In this first article of the series, we introduce all the terminology needed in this series, motivate this terminology, precisely state all the results in the remaining articles, and make some remarks about their proofs. As such, this article provides an overview of the entire series of articles; furthermore, the rest of the articles in this series may be read independently of one another.
A Convergent Off-Policy Temporal Difference Algorithm
Venue: arXiv cs.LG 2019
Year: 2019

Learning the value function of a given policy (target policy) from the data samples obtained from a different policy (behavior policy) is an important problem in Reinforcement Learning (RL). This problem is studied under the setting of off-policy prediction. Temporal Difference (TD) learning algorithms are a popular class of algorithms for solving the prediction problem. TD algorithms with linear function approximation are shown to be convergent when the samples are generated from the target policy (known as on-policy prediction). However, it has been well established in the literature that off-policy TD algorithms under linear function approximation diverge. In this work, we propose a convergent on-line off-policy TD algorithm under linear function approximation. The main idea is to penalize the updates of the algorithm in a way as to ensure convergence of the iterates. We provide a convergence analysis of our algorithm. Through numerical evaluations, we further demonstrate the effectiveness of our algorithm.
A Generic Metaheuristic Approach to Sequential Security Games
Venue: arXiv cs.GT 2019
Year: 2019

The paper introduces a generic approach to solving Sequential Security Games (SGs) which utilizes Evolutionary Algorithms. Formulation of the method (named EASG) is general and largely game-independent, which allows for its application to a wide range of SGs with just little adjustments addressing game specificity. Comprehensive experiments performed on 3 different types of games (with 300 instances in total) demonstrate robustness and stability of EASG, manifested by repeatable achieving optimal or near-optimal solutions in the vast majority of the cases. The main advantage of EASG is time efficiency. The method scales visibly better than state-of-the-art approaches and consequently can be applied to SG instances which are beyond capabilities of the existing methods. Furthermore, due to anytime characteristics, EASG is very well suited for time-critical applications, as the method can be terminated at any moment and still provide a reasonably good solution - the best one found so far.
By the user, for the user: A user-centric approach to quantifying the privacy of websites
Venue: arXiv cs.CY 2019
Year: 2019

Third-party tracking is common on almost all commercially operated websites. Prior work has studied in detail the extent of third-party tracking on the web, detection of third-party trackers, and defending against third-party tracking. Existing research and tools have also attempted to inform web users of trackers and the extent of their privacy violations. However, existing tools do not take into account users' perceptions of and understanding of the extent of trackers on the web. Taking these factors into account is important for the usability of such tools so that users can be aware and protect themselves to a reasonable and necessary extent that aligns with their overall comfort with trackers. In this paper, we elicit user perceptions and preferences about different trackers on various websites through an online survey of 43 users. We use this data to bootstrap a privacy scoring system. This scoring system weights the usage of trackers and the dispersion of user data within a page to third parties, with the type of website being visited. Our work presents a proof-of-concept methodology and tool to calculate a user-centric privacy score with preliminary bootstrap user data. We conclude with concrete future directions.
Iterative method of generating artificial context-free grammars
Venue: arXiv cs.FL 2019
Year: 2019

Grammatical inference is a machine learning area, whose fundamentals are built around learning sets. At present, real-life data and examples from manually crafted grammars are used to test their learning performance. This paper aims to present a method of generating artificial context-free grammars with their optimal learning sets, which could be successfully applied as a benchmarking tool for empirical grammar inference methods.
Coarse-Refinement Dilemma: On Generalization Bounds for Data Clustering
Venue: arXiv cs.LG 2019
Year: 2019

The Data Clustering (DC) problem is of central importance for the area of Machine Learning (ML), given its usefulness to represent data structural similarities from input spaces. Differently from Supervised Machine Learning (SML), which relies on the theoretical frameworks of the Statistical Learning Theory (SLT) and the Algorithm Stability (AS), DC has scarce literature on general-purpose learning guarantees, affecting conclusive remarks on how those algorithms should be designed as well as on the validity of their results. In this context, this manuscript introduces a new concept, based on multidimensional persistent homology, to analyze the conditions on which a clustering model is capable of generalizing data. As a first step, we propose a more general definition of DC problem by relying on Topological Spaces, instead of metric ones as typically approached in the literature. From that, we show that the DC problem presents an analogous dilemma to the Bias-Variance one, which is here referred to as the Coarse-Refinement (CR) dilemma. CR is intended to clarify the contrast between: (i) highly-refined partitions and the clustering instability (overfitting); and (ii) over-coarse partitions and the lack of representativeness (underfitting); consequently, the CR dilemma suggests the need of a relaxation of Kleinberg's richness axiom. Experimental results were used to illustrate that multidimensional persistent homology support the measurement of divergences among DC models, leading to a consistency criterion.
Trustworthy Misinformation Mitigation with Soft Information Nudging
Venue: arXiv cs.CY 2019
Year: 2019

Research in combating misinformation reports many negative results: facts may not change minds, especially if they come from sources that are not trusted. Individuals can disregard and justify lies told by trusted sources. This problem is made even worse by social recommendation algorithms which help amplify conspiracy theories and information confirming one's own biases due to companies' efforts to optimize for clicks and watch time over individuals' own values and public good. As a result, more nuanced voices and facts are drowned out by a continuous erosion of trust in better information sources. Most misinformation mitigation techniques assume that discrediting, filtering, or demoting low veracity information will help news consumers make better information decisions. However, these negative results indicate that some news consumers, particularly extreme or conspiracy news consumers will not be helped. We argue that, given this background, technology solutions to combating misinformation should not simply seek facts or discredit bad news sources, but instead use more subtle nudges towards better information consumption. Repeated exposure to such nudges can help promote trust in better information sources and also improve societal outcomes in the long run. In this article, we will talk about technological solutions that can help us in developing such an approach, and introduce one such model called Trust Nudging.
On the Age of Information in Erasure Channels with Feedback
Venue: arXiv cs.IT 2019
Year: 2019

We consider a status updating system where having timely knowledge about the information source at the destination (monitor) is of utmost importance. By utilizing the age of information (AoI) metric, the freshness of status update over an erasure channel is investigated. Due to the erasure nature of the update transmission, an error-free feedback channel from the monitor to the source is necessary for reducing AoI. Each status update contains $K$ packets which can be sent through the channel one at a time. At each channel use, one status update is available from the information source. Depending on how many packets have been received successfully out of the $K$ packets, we need to decide whether to continue sending the current update or terminate it and start sending the newly generated update. In this paper, we find the optimal failure tolerance when the erasure probability ($ε$) is in the regime $ε\to 0$ and also provide a lower and an upper bound for the average AoI for all erasure probabilities. Moreover, for all $ε$, we provide a lower bound for failure tolerance to minimize peak AoI.
Motion Reasoning for Goal-Based Imitation Learning
Venue: arXiv cs.RO 2019
Year: 2019

We address goal-based imitation learning, where the aim is to output the symbolic goal from a third-person video demonstration. This enables the robot to plan for execution and reproduce the same goal in a completely different environment. The key challenge is that the goal of a video demonstration is often ambiguous at the level of semantic actions. The human demonstrators might unintentionally achieve certain subgoals in the demonstrations with their actions. Our main contribution is to propose a motion reasoning framework that combines task and motion planning to disambiguate the true intention of the demonstrator in the video demonstration. This allows us to robustly recognize the goals that cannot be disambiguated by previous action-based approaches. We evaluate our approach by collecting a dataset of 96 video demonstrations in a mockup kitchen environment. We show that our motion reasoning plays an important role in recognizing the actual goal of the demonstrator and improves the success rate by over 20%. We further show that by using the automatically inferred goal from the video demonstration, our robot is able to reproduce the same task in a real kitchen environment.
LiDAR ICPS-net: Indoor Camera Positioning based-on Generative Adversarial Network for RGB to Point-Cloud Translation
Venue: arXiv cs.CV 2019
Year: 2019

Indoor positioning aims at navigation inside areas with no GPS-data availability and could be employed in many applications such as augmented reality, autonomous driving specially inside closed areas and tunnels. In this paper, a deep neural network-based architecture has been proposed to address this problem. In this regard, a tandem set of convolutional neural networks, as well as a Pix2Pix GAN network have been leveraged to perform as the scene classifier, scene RGB image to point cloud converter, and position regressor, respectively. The proposed architecture outperforms the previous works, including our recent work, in the sense that it makes data generation task easier and more robust against scene small variations, whilst the accuracy of the positioning is remarkably well, for both Cartesian position and quaternion information of the camera.
Understanding the Disharmony between Weight Normalization Family and Weight Decay: $ε-$shifted $L_2$ Regularizer
Venue: arXiv cs.LG 2019
Year: 2019

The merits of fast convergence and potentially better performance of the weight normalization family have drawn increasing attention in recent years. These methods use standardization or normalization that changes the weight $\boldsymbol{W}$ to $\boldsymbol{W}'$, which makes $\boldsymbol{W}'$ independent to the magnitude of $\boldsymbol{W}$. Surprisingly, $\boldsymbol{W}$ must be decayed during gradient descent, otherwise we will observe a severe under-fitting problem, which is very counter-intuitive since weight decay is widely known to prevent deep networks from over-fitting. In this paper, we \emph{theoretically} prove that the weight decay term $\frac{1}{2}λ||{\boldsymbol{W}}||^2$ merely modulates the effective learning rate for improving objective optimization, and has no influence on generalization when the weight normalization family is compositely employed. Furthermore, we also expose several critical problems when introducing weight decay term to weight normalization family, including the missing of global minimum and training instability. To address these problems, we propose an $ε-$shifted $L_2$ regularizer, which shifts the $L_2$ objective by a positive constant $ε$. Such a simple operation can theoretically guarantee the existence of global minimum, while preventing the network weights from being too small and thus avoiding gradient float overflow. It significantly improves the training stability and can achieve slightly better performance in our practice. The effectiveness of $ε-$shifted $L_2$ regularizer is comprehensively validated on the ImageNet, CIFAR-100, and COCO datasets. Our codes and pretrained models will be released in https://github.com/implus/PytorchInsight.
SimVODIS: Simultaneous Visual Odometry, Object Detection, and Instance Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Intelligent agents need to understand the surrounding environment to provide meaningful services to or interact intelligently with humans. The agents should perceive geometric features as well as semantic entities inherent in the environment. Contemporary methods in general provide one type of information regarding the environment at a time, making it difficult to conduct high-level tasks. Moreover, running two types of methods and associating two resultant information requires a lot of computation and complicates the software architecture. To overcome these limitations, we propose a neural architecture that simultaneously performs both geometric and semantic tasks in a single thread: simultaneous visual odometry, object detection, and instance segmentation (SimVODIS). Training SimVODIS requires unlabeled video sequences and the photometric consistency between input image frames generates self-supervision signals. The performance of SimVODIS outperforms or matches the state-of-the-art performance in pose estimation, depth map prediction, object detection, and instance segmentation tasks while completing all the tasks in a single thread. We expect SimVODIS would enhance the autonomy of intelligent agents and let the agents provide effective services to humans.
Contextual Bandits Evolving Over Finite Time
Venue: arXiv cs.LG 2019
Year: 2019

Contextual bandits have the same exploration-exploitation trade-off as standard multi-armed bandits. On adding positive externalities that decay with time, this problem becomes much more difficult as wrong decisions at the start are hard to recover from. We explore existing policies in this setting and highlight their biases towards the inherent reward matrix. We propose a rejection based policy that achieves a low regret irrespective of the structure of the reward probability matrix.
Robust Parameter-Free Season Length Detection in Time Series
Venue: arXiv cs.LG 2019
Year: 2019

The in-depth analysis of time series has gained a lot of research interest in recent years, with the identification of periodic patterns being one important aspect. Many of the methods for identifying periodic patterns require time series' season length as input parameter. There exist only a few algorithms for automatic season length approximation. Many of these rely on simplifications such as data discretization and user defined parameters. This paper presents an algorithm for season length detection that is designed to be sufficiently reliable to be used in practical applications and does not require any input other than the time series to be analyzed. The algorithm estimates a time series' season length by interpolating, filtering and detrending the data. This is followed by analyzing the distances between zeros in the directly corresponding autocorrelation function. Our algorithm was tested against a comparable algorithm and outperformed it by passing 122 out of 165 tests, while the existing algorithm passed 83 tests. The robustness of our method can be jointly attributed to both the algorithmic approach and also to design decisions taken at the implementational level.
CMSN: Continuous Multi-stage Network and Variable Margin Cosine Loss for Temporal Action Proposal Generation
Venue: arXiv cs.CV 2019
Year: 2019

Accurately locating the start and end time of an action in untrimmed videos is a challenging task. One of the important reasons is the boundary of action is not highly distinguishable, and the features around the boundary are difficult to discriminate. To address this problem, we propose a novel framework for temporal action proposal generation, namely Continuous Multi-stage Network (CMSN), which divides a video that contains a complete action instance into six stages, namely Backgroud, Ready, Start, Confirm, End, Follow. To distinguish between Ready and Start, End and Follow more accurately, we propose a novel loss function, Variable Margin Cosine Loss (VMCL), which allows for different margins between different categories. Our experiments on THUMOS14 show that the proposed method for temporal proposal generation performs better than the state-of-the-art methods using the same network architecture and training dataset.
MML: Maximal Multiverse Learning for Robust Fine-Tuning of Language Models
Venue: arXiv cs.CL 2019
Year: 2019

Recent state-of-the-art language models utilize a two-phase training procedure comprised of (i) unsupervised pre-training on unlabeled text, and (ii) fine-tuning for a specific supervised task. More recently, many studies have been focused on trying to improve these models by enhancing the pre-training phase, either via better choice of hyperparameters or by leveraging an improved formulation. However, the pre-training phase is computationally expensive and often done on private datasets. In this work, we present a method that leverages BERT's fine-tuning phase to its fullest, by applying an extensive number of parallel classifier heads, which are enforced to be orthogonal, while adaptively eliminating the weaker heads during training. Our method allows the model to converge to an optimal number of parallel classifiers, depending on the given dataset at hand. We conduct an extensive inter- and intra-dataset evaluations, showing that our method improves the robustness of BERT, sometimes leading to a +9\% gain in accuracy. These results highlight the importance of a proper fine-tuning procedure, especially for relatively smaller-sized datasets. Our code is attached as supplementary and our models will be made completely public.
Probabilistic Similarity Networks
Venue: arXiv cs.AI 2019
Year: 2019

Normative expert systems have not become commonplace because they have been difficult to build and use. Over the past decade, however, researchers have developed the influence diagram, a graphical representation of a decision maker's beliefs, alternatives, and preferences that serves as the knowledge base of a normative expert system. Most people who have seen the representation find it intuitive and easy to use. Consequently, the influence diagram has overcome significantly the barriers to constructing normative expert systems. Nevertheless, building influence diagrams is not practical for extremely large and complex domains. In this book, I address the difficulties associated with the construction of the probabilistic portion of an influence diagram, called a knowledge map, belief network, or Bayesian network. I introduce two representations that facilitate the generation of large knowledge maps. In particular, I introduce the similarity network, a tool for building the network structure of a knowledge map, and the partition, a tool for assessing the probabilities associated with a knowledge map. I then use these representations to build Pathfinder, a large normative expert system for the diagnosis of lymph-node diseases (the domain contains over 60 diseases and over 100 disease findings). In an early version of the system, I encoded the knowledge of the expert using an erroneous assumption that all disease findings were independent, given each disease. When the expert and I attempted to build a more accurate knowledge map for the domain that would capture the dependencies among the disease findings, we failed. Using a similarity network, however, we built the knowledge-map structure for the entire domain in approximately 40 hours. Furthermore, the partition representation reduced the number of probability assessments required by the expert from 75,000 to 14,000.
The Isoperimetric Problem in a Lattice of $\mathbb{H}^3$
Venue: arXiv cs.CG 2019
Year: 2019

The isoperimetric problem is one of the oldest in geometry and it consists of finding a surface of minimum area that encloses a given volume $V$. It is particularly important in physics because of its strong relation with stability, and this also involves the study of phenomena in non-Euclidean spaces. Of course, such spaces cannot be customized for lab experiments but we can resort to computational simulations, and one of the mostly used softwares for this purpose is the Surface Evolver. In this paper we use it to study the isoperimetric problem in a lattice of the three dimensional hyperbolic space. More precisely: up to isometries, there exists a unique tesselation of $\mathbb{H}^3$ by non-ideal cubes $\mathcal{C}$. Now let $Ω$ be a connected isoperimetric region inside the non-ideal hyperbolic cube $\mathcal{C}$. Under weak assumptions on graph and symmetry we find all numerical solutions $Σ=\partialΩ$ of the isoperimetric problem in $\mathcal{C}$.