OpenRaiser/Intern-Atlas huggingface dataset:
Uncoded Caching and Cross-level Coded Delivery for Non-uniform File Popularity
Venue: arXiv cs.IT 2021
Year: 2021

Proactive content caching at user devices and coded delivery is studied considering a non-uniform file popularity distribution. A novel centralized uncoded caching and coded delivery scheme, which can be applied to large file libraries, is proposed. The proposed cross-level coded delivery (CLCD) scheme is shown to achieve a lower average delivery rate than the state of art. In the proposed CLCD scheme, the same subpacketization is used for all the files in the library in order to prevent additional zero-padding in the delivery phase, and unlike the existing schemes in the literature, two users requesting files from different popularity groups can be served by the same multicast message in order to reduce the delivery rate. Simulation results indicate significant reduction in the average delivery rate for typical Zipf distribution parameter values.
Optimal Sequential Contests
Venue: arXiv cs.GT 2021
Year: 2021

I study sequential contests where the efforts of earlier players may be disclosed to later players by nature or by design. The model has a range of applications, including rent seeking, R&D, oligopoly, public goods provision, and tragedy of the commons. I show that information about other players' efforts increases the total effort. Thus, the total effort is maximized with full transparency and minimized with no transparency. I also show that in addition to the first-mover advantage, there is an earlier-mover advantage. Finally, I derive the limits for large contests.
A Diffusion Approximation Theory of Momentum SGD in Nonconvex Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Momentum Stochastic Gradient Descent (MSGD) algorithm has been widely applied to many nonconvex optimization problems in machine learning, e.g., training deep neural networks, variational Bayesian inference, and etc. Despite its empirical success, there is still a lack of theoretical understanding of convergence properties of MSGD. To fill this gap, we propose to analyze the algorithmic behavior of MSGD by diffusion approximations for nonconvex optimization problems with strict saddle points and isolated local optima. Our study shows that the momentum helps escape from saddle points, but hurts the convergence within the neighborhood of optima (if without the step size annealing or momentum annealing). Our theoretical discovery partially corroborates the empirical success of MSGD in training deep neural networks.
Multiclass Common Spatial Pattern for EEG based Brain Computer Interface with Adaptive Learning Classifier
Venue: arXiv cs.NE 2021
Year: 2021

In Brain Computer Interface (BCI), data generated from Electroencephalogram (EEG) is non-stationary with low signal to noise ratio and contaminated with artifacts. Common Spatial Pattern (CSP) algorithm has been proved to be effective in BCI for extracting features in motor imagery tasks, but it is prone to overfitting. Many algorithms have been devised to regularize CSP for two class problem, however they have not been effective when applied to multiclass CSP. Outliers present in data affect extracted CSP features and reduces performance of the system. In addition to this non-stationarity present in the features extracted from the CSP present a challenge in classification. We propose a method to identify and remove artifact present in the data during pre-processing stage, this helps in calculating eigenvectors which in turn generates better CSP features. To handle the non-stationarity, Self-Regulated Interval Type-2 Neuro-Fuzzy Inference System (SRIT2NFIS) was proposed in the literature for two class EEG classification problem. This paper extends the SRIT2NFIS to multiclass using Joint Approximate Diagonalization (JAD). The results on standard data set from BCI competition IV shows significant increase in the accuracies from the current state of the art methods for multiclass classification.
Learning Task-Specific Dynamics to Improve Whole-Body Control
Venue: arXiv cs.RO 2021
Year: 2021

In task-based inverse dynamics control, reference accelerations used to follow a desired plan can be broken down into feedforward and feedback trajectories. The feedback term accounts for tracking errors that are caused from inaccurate dynamic models or external disturbances. On underactuated, free-floating robots, such as humanoids, good tracking accuracy often necessitates high feedback gains, which leads to undesirable stiff behaviors. The magnitude of these gains is anyways often strongly limited by the control bandwidth. In this paper, we show how to reduce the required contribution of the feedback controller by incorporating learned task-space reference accelerations. Thus, we i) improve the execution of the given specific task, and ii) offer the means to reduce feedback gains, providing for greater compliance of the system. %With a systematic approach we also reduce heuristic tuning of the model parameters and feedback gains, often present in real-world experiments. In contrast to learning task-specific joint-torques, which might produce a similar effect but can lead to poor generalization, our approach directly learns the task-space dynamics of the center of mass of a humanoid robot. Simulated and real-world results on the lower part of the Sarcos Hermes humanoid robot demonstrate the applicability of the approach.
Institutional Metaphors for Designing Large-Scale Distributed AI versus AI Techniques for Running Institutions
Venue: arXiv cs.AI 2021
Year: 2021

Artificial Intelligence (AI) started out with an ambition to reproduce the human mind, but, as the sheer scale of that ambition became manifest, it quickly retreated into either studying specialized intelligent behaviours, or proposing over-arching architectural concepts for interfacing specialized intelligent behaviour components, conceived of as agents in a kind of organization. This agent-based modeling paradigm, in turn, proves to have interesting applications in understanding, simulating, and predicting the behaviour of social and legal structures on an aggregate level. For these reasons, this chapter examines a number of relevant cross-cutting concerns, conceptualizations, modeling problems and design challenges in large-scale distributed Artificial Intelligence, as well as in institutional systems, and identifies potential grounds for novel advances.
The Three Pillars of Machine Programming
Venue: arXiv cs.AI 2021
Year: 2021

In this position paper, we describe our vision of the future of machine programming through a categorical examination of three pillars of research. Those pillars are: (i) intention, (ii) invention, and(iii) adaptation. Intention emphasizes advancements in the human-to-computer and computer-to-machine-learning interfaces. Invention emphasizes the creation or refinement of algorithms or core hardware and software building blocks through machine learning (ML). Adaptation emphasizes advances in the use of ML-based constructs to autonomously evolve software.
Biblioranking fundamental physics
Venue: arXiv cs.DL 2021
Year: 2021

We propose measures of the impact of research that improve on existing ones such as counting of number of papers, citations and $h$-index. Since different papers and different fields have largely different average number of co-authors and of references we replace citations with individual citations, shared among co-authors. Next, we improve on citation counting applying the PageRank algorithm to citations among papers. Being time-ordered, this reduces to a weighted counting of citation descendants that we call PaperRank. Similarly, we compute an AuthorRank applying the PageRank algorithm to citations among authors. These metrics quantify the impact of an author or paper taking into account the impact of those authors that cite it. Finally, we show how self- and circular- citations can be eliminated by defining a closed market of citation-coins. We apply these metrics to the InSpire database that covers fundamental physics, ranking papers, authors, journals, institutes, towns, countries, continents, genders, for all-time and in recent time periods.
TacticToe: Learning to Prove with Tactics
Venue: arXiv cs.AI 2021
Year: 2021

We implement a automated tactical prover TacticToe on top of the HOL4 interactive theorem prover. TacticToe learns from human proofs which mathematical technique is suitable in each proof situation. This knowledge is then used in a Monte Carlo tree search algorithm to explore promising tactic-level proof paths. On a single CPU, with a time limit of 60 seconds, TacticToe proves 66.4 percent of the 7164 theorems in HOL4's standard library, whereas E prover with auto-schedule solves 34.5 percent. The success rate rises to 69.0 percent by combining the results of TacticToe and E prover.
Semantic Edge Detection with Diverse Deep Supervision
Venue: arXiv cs.CV 2021
Year: 2021

Semantic edge detection (SED), which aims at jointly extracting edges as well as their category information, has far-reaching applications in domains such as semantic segmentation, object proposal generation, and object recognition. SED naturally requires achieving two distinct supervision targets: locating fine detailed edges and identifying high-level semantics. Our motivation comes from the hypothesis that such distinct targets prevent state-of-the-art SED methods from effectively using deep supervision to improve results. To this end, we propose a novel fully convolutional neural network using diverse deep supervision (DDS) within a multi-task framework where bottom layers aim at generating category-agnostic edges, while top layers are responsible for the detection of category-aware semantic edges. To overcome the hypothesized supervision challenge, a novel information converter unit is introduced, whose effectiveness has been extensively evaluated on SBD and Cityscapes datasets.
DeepMiner: Discovering Interpretable Representations for Mammogram Classification and Explanation
Venue: arXiv cs.CV 2021
Year: 2021

We propose DeepMiner, a framework to discover interpretable representations in deep neural networks and to build explanations for medical predictions. By probing convolutional neural networks (CNNs) trained to classify cancer in mammograms, we show that many individual units in the final convolutional layer of a CNN respond strongly to diseased tissue concepts specified by the BI-RADS lexicon. After expert annotation of the interpretable units, our proposed method is able to generate explanations for CNN mammogram classification that are consistent with ground truth radiology reports on the Digital Database for Screening Mammography. We show that DeepMiner not only enables better understanding of the nuances of CNN classification decisions but also possibly discovers new visual knowledge relevant to medical diagnosis.
An Enhanced Binary Particle-Swarm Optimization (E-BPSO) Algorithm for Service Placement in Hybrid Cloud Platforms
Venue: arXiv cs.DC 2021
Year: 2021

Nowadays, hybrid cloud platforms stand as an attractive solution for organizations intending to implement combined private and public cloud applications, in order to meet their profitability requirements. However, this can only be achieved through the utilization of available resources while speeding up execution processes. Accordingly, deploying new applications entails dedicating some of these processes to a private cloud solution, while allocating others to the public cloud. In this context, the present work is set to help minimize relevant costs and deliver effective choices for an optimal service placement solution within minimal execution time. Several evolutionary algorithms have been applied to solve the service placement problem and are used when dealing with complex solution spaces to provide an optimal placement and often produce a short execution time. The standard BPSO algorithm is found to display a significant disadvantage, namely, of easily trapping into local optima, in addition to demonstrating a noticeable lack of robustness in dealing with service placement problems. Hence, to overcome critical shortcomings associated with the standard BPSO, an Enhanced Binary Particle Swarm Optimization (E-BPSO) algorithm is proposed, consisting of a modification of the particle position updating equation, initially inspired from the continuous PSO. Our proposed E-BPSO algorithm is shown to outperform state-of-the-art approaches in terms of both cost and execution time, using a real benchmark.
Segmentation of Photovoltaic Module Cells in Uncalibrated Electroluminescence Images
Venue: arXiv cs.CV 2021
Year: 2021

High resolution electroluminescence (EL) images captured in the infrared spectrum allow to visually and non-destructively inspect the quality of photovoltaic (PV) modules. Currently, however, such a visual inspection requires trained experts to discern different kinds of defects, which is time-consuming and expensive. Automated segmentation of cells is therefore a key step in automating the visual inspection workflow. In this work, we propose a robust automated segmentation method for extraction of individual solar cells from EL images of PV modules. This enables controlled studies on large amounts of data to understanding the effects of module degradation over time-a process not yet fully understood. The proposed method infers in several steps a high-level solar module representation from low-level edge features. An important step in the algorithm is to formulate the segmentation problem in terms of lens calibration by exploiting the plumbline constraint. We evaluate our method on a dataset of various solar modules types containing a total of 408 solar cells with various defects. Our method robustly solves this task with a median weighted Jaccard index of 94.47% and an $F_1$ score of 97.62%, both indicating a very high similarity between automatically segmented and ground truth solar cell masks.
Robot hazards: from safety to security
Venue: arXiv cs.CY 2021
Year: 2021

Robotics landscape is experiencing big changes. Robots are spreading and will soon be everywhere. Systems traditionally employed in industry are being replaced by collaborative robots, while more and more professional and consumer robots are introduced in people's daily activities. Robots are increasingly intertwined with other facets of IT and envisioned to get much more autonomy, interacting physically with humans. We claim that, following Personal Computers (PCs) and smartphones, robots are the next technological revolution and yet, robot security is being ignored by manufacturers. The present paper aims to alert about the need of dealing not only with safety but with robot security from the very beginning of the forthcoming technological era. We provide herein a document that reviews robot hazards and analyzes the consequences of not facing these issues. We advocate strongly for a security-first approach as a must to be implemented now.
Utility Design for Distributed Resource Allocation -- Part II: Applications to Submodular, Covering, and Supermodular Problems
Venue: arXiv cs.GT 2021
Year: 2021

A fundamental component of the game theoretic approach to distributed control is the design of local utility functions.Relative to resource allocation problems that are additive over the resources, Part I showed how to design local utilities so as to maximize the associated performance guarantees [Paccagnan et al., TAC 2019] which we measure by the price of anarchy. The purpose of the present manuscript is to specialize these results to the case of submodular, covering, and supermodular problems. In all these cases we obtain tight expressions for the price of anarchy that often match or improve the guarantees associated to state-of-the-art approximation algorithms. Two applications and corresponding numerics are presented: the vehicle-target assignment problem and a coverage problem arising in wireless data caching.
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees
Venue: arXiv cs.LG 2021
Year: 2021

Model-based reinforcement learning (RL) is considered to be a promising approach to reduce the sample complexity that hinders model-free RL. However, the theoretical understanding of such methods has been rather limited. This paper introduces a novel algorithmic framework for designing and analyzing model-based RL algorithms with theoretical guarantees. We design a meta-algorithm with a theoretical guarantee of monotone improvement to a local maximum of the expected reward. The meta-algorithm iteratively builds a lower bound of the expected reward based on the estimated dynamical model and sample trajectories, and then maximizes the lower bound jointly over the policy and the model. The framework extends the optimism-in-face-of-uncertainty principle to non-linear dynamical models in a way that requires \textit{no explicit} uncertainty quantification. Instantiating our framework with simplification gives a variant of model-based RL algorithms Stochastic Lower Bounds Optimization (SLBO). Experiments demonstrate that SLBO achieves state-of-the-art performance when only one million or fewer samples are permitted on a range of continuous control benchmark tasks.
Exact Distance Oracles for Planar Graphs with Failing Vertices
Venue: arXiv cs.DS 2021
Year: 2021

We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex $u$, a target vertex $v$ and a set $X$ of $k$ failed vertices, such an oracle returns the length of a shortest $u$-to-$v$ path that avoids all vertices in $X$. We propose oracles that can handle any number $k$ of failures. We show several tradeoffs between space, query time, and preprocessing time. In particular, for a directed weighted planar graph with $n$ vertices and any constant $k$, we show an $\tilde{\mathcal{O}}(n)$-size, $\tilde{\mathcal{O}}(\sqrt{n})$-query-time oracle. We then present a space vs. query time tradeoff: for any $q \in \lbrack 1,\sqrt n \rbrack$, we propose an oracle of size $n^{k+1+o(1)}/q^{2k}$ that answers queries in $\tilde{\mathcal{O}}(q)$ time. For single vertex failures ($k=1$), our $n^{2+o(1)}/q^2$-size, $\tilde{\mathcal{O}}(q)$-query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for $q \geq n^t$, for any $t \in (0,1/2]$. For multiple failures, no planarity exploiting results were previously known. A preliminary version of this work was presented in SODA 2019. In this version, we show improved space vs. query time tradeoffs relying on the recently proposed almost optimal distance oracles for planar graphs [Charalampopoulos et al., STOC 2019; Long and Pettie, SODA 2021].
A Metalanguage for Guarded Iteration
Venue: arXiv cs.LO 2021
Year: 2021

Notions of guardedness serve to delineate admissible recursive definitions in various settings in a compositional manner. In recent work, we have introduced an axiomatic notion of guardedness in symmetric monoidal categories, which serves as a unifying framework for various examples from program semantics, process algebra, and beyond. In the present paper, we propose a generic metalanguage for guarded iteration based on combining this notion with the fine-grain call-by-value paradigm, which we intend as a unifying programming language for guarded and unguarded iteration in the presence of computational effects. We give a generic (categorical) semantics of this language over a suitable class of strong monads supporting guarded iteration, and show it to be in touch with the standard operational behaviour of iteration by giving a concrete big-step operational semantics for a certain specific instance of the metalanguage and establishing soundness and (computational) adequacy for this case.
Dynamic Multi-level Privilege Control in Behavior-based Implicit Authentication Systems Leveraging Mobile Devices
Venue: arXiv cs.CR 2021
Year: 2021

Implicit authentication (IA) is gaining popularity over recent years due to its use of user behavior as the main input, relieving users from explicit actions such as remembering and entering passwords. However, such convenience comes with a cost of authentication accuracy and delay which we propose to improve in this paper. Authentication accuracy deteriorates as users' behaviors change as a result of mood, age, a change of routine, etc. Current authentication systems handle failed authentication attempts by locking the users out of their mobile devices. It is unsuitable for IA whose accuracy deterioration induces a high false reject rate, rendering the IA system unusable. Furthermore, existing IA systems leverage computationally expensive machine learning, which can introduce a large authentication delay. It is challenging to improve the authentication accuracy of these systems without sacrificing authentication delay. In this paper, we propose a multi-level privilege control (MPC) scheme that dynamically adjusts users' access privilege based on their behavior change. MPC increases the system's confidence in users' legitimacy even when their behaviors deviate from historical data, thus improving authentication accuracy. It is a lightweight feature added to the existing IA schemes that helps avoid frequent and expensive retraining of machine learning models, thus improving authentication delay. We demonstrate that MPC increases authentication accuracy by 18.63\% and reduces authentication delay by 7.02 minutes on average, using a public dataset that contains comprehensive user behavior data.
Multi-Output Convolution Spectral Mixture for Gaussian Processes
Venue: arXiv cs.LG 2021
Year: 2021

Multi-output Gaussian processes (MOGPs) are an extension of Gaussian Processes (GPs) for predicting multiple output variables (also called channels, tasks) simultaneously. In this paper we use the convolution theorem to design a new kernel for MOGPs, by modeling cross channel dependencies through cross convolution of time and phase delayed components in the spectral domain. The resulting kernel is called Multi-Output Convolution Spectral Mixture (MOCSM) kernel. Results of extensive experiments on synthetic and real-life datasets demonstrate the advantages of the proposed kernel and its state of the art performance. MOCSM enjoys the desirable property to reduce to the well known Spectral Mixture (SM) kernel when a single-channel is considered. A comparison with the recently introduced Multi-Output Spectral Mixture kernel reveals that this is not the case for the latter kernel, which contains quadratic terms that generate undesirable scale effects when the spectral densities of different channels are either very close or very far from each other in the frequency domain.
Algorithmic No-Cloning Theorem
Venue: arXiv cs.CC 2021
Year: 2021

We introduce the notions of algorithmic mutual information and rarity of quantum states. These definitions enjoy conservation inequalities over unitary transformations and partial traces. We show that a large majority of pure states have minute self algorithmic information. We provide an algorithmic variant to the no-cloning theorem, by showing that only a small minority of quantum pure states can clone a non negligible amount of algorithmic information. We also provide a chain rule inequality for quantum algorithmic entropy. We show that rarity does not increase under POVM measurements.