OpenRaiser/Intern-Atlas huggingface dataset:
An Empirical Analysis of Feature Engineering for Predictive Modeling
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning models, such as neural networks, decision trees, random forests, and gradient boosting machines, accept a feature vector, and provide a prediction. These models learn in a supervised fashion where we provide feature vectors mapped to the expected output. It is common practice to engineer new features from the provided feature set. Such engineered features will either augment or replace portions of the existing feature vector. These engineered features are essentially calculated fields based on the values of the other features. Engineering such features is primarily a manual, time-consuming task. Additionally, each type of model will respond differently to different kinds of engineered features. This paper reports empirical research to demonstrate what kinds of engineered features are best suited to various machine learning model types. We provide this recommendation by generating several datasets that we designed to benefit from a particular type of engineered feature. The experiment demonstrates to what degree the machine learning model can synthesize the needed feature on its own. If a model can synthesize a planned feature, it is not necessary to provide that feature. The research demonstrated that the studied models do indeed perform differently with various types of engineered features.
Deterministic Protocols in the SINR Model without Knowledge of Coordinates
Venue: arXiv cs.DC 2020
Year: 2020

Much work has been developed for studying the classical broadcasting problem in the SINR (Signal-to-Interference-plus-Noise-Ratio) model for wireless device transmission. The setting typically studied is when all radio nodes transmit a signal of the same strength. This work studies the challenging problem of devising a distributed algorithm for multi-broadcasting, assuming a subset of nodes are initially awake, for the SINR model when each device only has access to knowledge about the total number of nodes in the network $n$, the range from which each node's label is taken $\lbrace 1,\dots,N \rbrace$, and the label of the device itself. Specifically, we assume no knowledge of the physical coordinates of devices and also no knowledge of the neighborhood of each node. We present a deterministic protocol for this problem in $O(n \lg N \lg n)$ rounds. There is no known polynomial time deterministic algorithm in literature for this setting, and it remains the principle open problem in this domain. A lower bound of $Ω(n \lg N)$ rounds is known for deterministic broadcasting without local knowledge. In addition to the above result, we present algorithms to achieve multi-broadcast in $O(n \lg N)$ rounds and create a backbone in $O(n \lg N)$ rounds, assuming that all nodes are initially awake. For a given backbone, messages can be exchanged between every pair of connected nodes in the backbone in $O(\lg N)$ rounds and between any node and its designated contact node in the backbone in $O(Δ\lg N)$ rounds.
SLAM auto-complete: completing a robot map using an emergency map
Venue: arXiv cs.RO 2020
Year: 2020

In search and rescue missions, time is an important factor; fast navigation and quickly acquiring situation awareness might be matters of life and death. Hence, the use of robots in such scenarios has been restricted by the time needed to explore and build a map. One way to speed up exploration and mapping is to reason about unknown parts of the environment using prior information. While previous research on using external priors for robot mapping mainly focused on accurate maps or aerial images, such data are not always possible to get, especially indoor. We focus on emergency maps as priors for robot mapping since they are easy to get and already extensively used by firemen in rescue missions. However, those maps can be outdated, information might be missing, and the scales of rooms are typically not consistent. We have developed a formulation of graph-based SLAM that incorporates information from an emergency map. The graph-SLAM is optimized using a combination of robust kernels, fusing the emergency map and the robot map into one map, even when faced with scale inaccuracies and inexact start poses. We typically have more than 50% of wrong correspondences in the settings studied in this paper, and the method we propose correctly handles them. Experiments in an office environment show that we can handle up to 70% of wrong correspondences and still get the expected result. The robot can navigate and explore while taking into account places it has not yet seen. We demonstrate this in a test scenario and also show that the emergency map is enhanced by adding information not represented such as closed doors or new walls.
Intensionality, Intensional Recursion, and the Gödel-Löb axiom
Venue: arXiv cs.PL 2020
Year: 2020

The use of a necessity modality in a typed $λ$-calculus can be used to separate it into two regions. These can be thought of as intensional vs. extensional data: data in the first region, the modal one, are available as code, and their description can be examined. In contrast, data in the second region are only available as values up to ordinary equality. This allows us to add non-functional operations at modal types whilst maintaining consistency. In this setting, the Gödel-Löb axiom acquires a novel constructive reading: it affords the programmer the possibility of a very strong kind of recursion which enables them to write programs that have access to their own code. This is a type of computational reflection that is strongly reminiscent of Kleene's Second Recursion Theorem.
Approximation Algorithms for Maximin Fair Division
Venue: arXiv cs.GT 2020
Year: 2020

We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, that is defined to be the maximum value that an agent can ensure for herself, if she were to partition the goods into n bundles, and then receive a minimum valued bundle. Since maximin fair allocations (i.e., allocations in which each agent gets at least her maximin share) do not always exist, prior work has focused on approximation results that aim to find allocations in which the value of the bundle allocated to each agent is (multiplicatively) as close to her maximin share as possible. In particular, Procaccia and Wang (2014) along with Amanatidis et al. (2015) have shown that under additive valuations a 2/3-approximate maximin fair allocation always exists and can be found in polynomial time. We complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee. Furthermore, we initiate the study of approximate maximin fair division under submodular valuations. Specifically, we show that when the valuations of the agents are nonnegative, monotone, and submodular, then a 0.21-approximate maximin fair allocation is guaranteed to exist. In fact, we show that such an allocation can be efficiently found by using a simple round-robin algorithm. A technical contribution of the paper is to analyze the performance of this combinatorial algorithm by employing the concept of multilinear extensions.
Under-Optimized Smart Contracts Devour Your Money
Venue: arXiv cs.SE 2020
Year: 2020

Smart contracts are full-fledged programs that run on blockchains (e.g., Ethereum, one of the most popular blockchains). In Ethereum, gas (in Ether, a cryptographic currency like Bitcoin) is the execution fee compensating the computing resources of miners for running smart contracts. However, we find that under-optimized smart contracts cost more gas than necessary, and therefore the creators or users will be overcharged. In this work, we conduct the first investigation on Solidity, the recommended compiler, and reveal that it fails to optimize gas-costly programming patterns. In particular, we identify 7 gas-costly patterns and group them to 2 categories. Then, we propose and develop GASPER, a new tool for automatically locating gas-costly patterns by analyzing smart contracts' bytecodes. The preliminary results on discovering 3 representative patterns from 4,240 real smart contracts show that 93.5%, 90.1% and 80% contracts suffer from these 3 patterns, respectively.
Make Hawkes Processes Explainable by Decomposing Self-Triggering Kernels
Venue: arXiv cs.LG 2020
Year: 2020

Hawkes Processes capture self-excitation and mutual-excitation between events when the arrival of an event makes future events more likely to happen. Identification of such temporal covariance can reveal the underlying structure to better predict future events. In this paper, we present a new framework to decompose discrete events with a composition of multiple self-triggering kernels. The composition scheme allows us to decompose empirical covariance densities into the sum or the product of base kernels which are easily interpretable. Here, we present the first multiplicative kernel composition methods for Hawkes Processes. We demonstrate that the new automatic kernel decomposition procedure outperforms the existing methods on the prediction of discrete events in real-world data.
Walking Control Based on Step Timing Adaptation
Venue: arXiv cs.RO 2020
Year: 2020

Step adjustment can improve the gait robustness of biped robots, however the adaptation of step timing is often neglected as it gives rise to non-convex problems when optimized over several footsteps. In this paper, we argue that it is not necessary to optimize walking over several steps to ensure gait viability and show that it is sufficient to merely select the next step timing and location. Using this insight, we propose a novel walking pattern generator that optimally selects step location and timing at every control cycle. Our approach is computationally simple compared to standard approaches in the literature, yet guarantees that any viable state will remain viable in the future. We propose a swing foot adaptation strategy and integrate the pattern generator with an inverse dynamics controller that does not explicitly control the center of mass nor the foot center of pressure. This is particularly useful for biped robots with limited control authority over their foot center of pressure, such as robots with point feet or passive ankles. Extensive simulations on a humanoid robot with passive ankles demonstrate the capabilities of the approach in various walking situations, including external pushes and foot slippage, and emphasize the importance of step timing adaptation to stabilize walking.
A Popperian Falsification of Artificial Intelligence -- Lighthill Defended
Venue: arXiv cs.AI 2020
Year: 2020

The area of computation called artificial intelligence (AI) is falsified by describing a previous 1972 falsification of AI by British mathematical physicist James Lighthill. How Lighthill's arguments continue to apply to current AI is explained. It is argued that AI should use the Popperian scientific method in which it is the duty of scientists to attempt to falsify theories and if theories are falsified to replace or modify them. The paper describes the Popperian method and discusses Paul Nurse's application of the method to cell biology that also involves questions of mechanism and behavior. It is shown how Lighthill's falsifying arguments especially combinatorial explosion continue to apply to modern AI. Various skeptical arguments against the assumptions of AI mostly by physicists especially against Hilbert's philosophical programme that defined knowledge and truth as provable formal sentences. John von Neumann's arguments from natural complexity against neural networks and evolutionary algorithms are discussed. Next the game of chess is discussed to show how modern chess experts have reacted to computer chess programs. It is shown that currently chess masters can defeat any chess program using Kasperov's arguments from his 1997 Deep Blue match and aftermath. The game of 'go' and climate models are discussed to show computer applications where combinatorial explosion may not apply. The paper concludes by advocating studying computation as Peter Naur's Dataology.
GAR: An efficient and scalable Graph-based Activity Regularization for semi-supervised learning
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose a novel graph-based approach for semi-supervised learning problems, which considers an adaptive adjacency of the examples throughout the unsupervised portion of the training. Adjacency of the examples is inferred using the predictions of a neural network model which is first initialized by a supervised pretraining. These predictions are then updated according to a novel unsupervised objective which regularizes another adjacency, now linking the output nodes. Regularizing the adjacency of the output nodes, inferred from the predictions of the network, creates an easier optimization problem and ultimately provides that the predictions of the network turn into the optimal embedding. Ultimately, the proposed framework provides an effective and scalable graph-based solution which is natural to the operational mechanism of deep neural networks. Our results show comparable performance with state-of-the-art generative approaches for semi-supervised learning on an easier-to-train, low-cost framework.
Structural Compression of Convolutional Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Deep convolutional neural networks (CNNs) have been successful in many tasks in machine vision, however, millions of weights in the form of thousands of convolutional filters in CNNs makes them difficult for human intepretation or understanding in science. In this article, we introduce CAR, a greedy structural compression scheme to obtain smaller and more interpretable CNNs, while achieving close to original accuracy. The compression is based on pruning filters with the least contribution to the classification accuracy. We demonstrate the interpretability of CAR-compressed CNNs by showing that our algorithm prunes filters with visually redundant functionalities such as color filters. These compressed networks are easier to interpret because they retain the filter diversity of uncompressed networks with order of magnitude less filters. Finally, a variant of CAR is introduced to quantify the importance of each image category to each CNN filter. Specifically, the most and the least important class labels are shown to be meaningful interpretations of each filter.
Contextual Explanation Networks
Venue: arXiv cs.LG 2020
Year: 2020

Modern learning algorithms excel at producing accurate but complex models of the data. However, deploying such models in the real-world requires extra care: we must ensure their reliability, robustness, and absence of undesired biases. This motivates the development of models that are equally accurate but can be also easily inspected and assessed beyond their predictive performance. To this end, we introduce contextual explanation networks (CEN)---a class of architectures that learn to predict by generating and utilizing intermediate, simplified probabilistic models. Specifically, CENs generate parameters for intermediate graphical models which are further used for prediction and play the role of explanations. Contrary to the existing post-hoc model-explanation tools, CENs learn to predict and to explain simultaneously. Our approach offers two major advantages: (i) for each prediction valid, instance-specific explanation is generated with no computational overhead and (ii) prediction via explanation acts as a regularizer and boosts performance in data-scarce settings. We analyze the proposed framework theoretically and experimentally. Our results on image and text classification and survival analysis tasks demonstrate that CENs are not only competitive with the state-of-the-art methods but also offer additional insights behind each prediction, that can be valuable for decision support. We also show that while post-hoc methods may produce misleading explanations in certain cases, CENs are consistent and allow to detect such cases systematically.
The complexity of recognizing minimally tough graphs
Venue: arXiv cs.DM 2020
Year: 2020

A graph is called $t$-tough if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough if the toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. The complexity class DP is the set of all languages that can be expressed as the intersection of a language in NP and a language in coNP. In this paper, we prove that recognizing minimally $t$-tough graphs is DP-complete for any positive rational number $t$. We introduce a new notion called weighted toughness, which has a key role in our proof.
Global Convergence of the (1+1) Evolution Strategy
Venue: arXiv cs.NE 2020
Year: 2020

We establish global convergence of the (1+1) evolution strategy, i.e., convergence to a critical point independent of the initial state. More precisely, we show the existence of a critical limit point, using a suitable extension of the notion of a critical point to measurable functions. At its core, the analysis is based on a novel progress guarantee for elitist, rank-based evolutionary algorithms. By applying it to the (1+1) evolution strategy we are able to provide an accurate characterization of whether global convergence is guaranteed with full probability, or whether premature convergence is possible. We illustrate our results on a number of example applications ranging from smooth (non-convex) cases over different types of saddle points and ridge functions to discontinuous and extremely rugged problems.
Solving Integer Linear Programs with a Small Number of Global Variables and Constraints
Venue: arXiv cs.DM 2020
Year: 2020

Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understanding of which structural restrictions make ILP tractable. Here we study ILP instances consisting of a small number of "global" variables and/or constraints such that the remaining part of the instance consists of small and otherwise independent components; this is captured in terms of a structural measure we call fracture backdoors which generalizes, for instance, the well-studied class of N -fold ILP instances. Our main contributions can be divided into three parts. First, we formally develop fracture backdoors and obtain exact and approximation algorithms for computing these. Second, we exploit these backdoors to develop several new parameterized algorithms for ILP; the performance of these algorithms will naturally scale based on the number of global variables or constraints in the instance. Finally, we complement the developed algorithms with matching lower bounds. Altogether, our results paint a near-complete complexity landscape of ILP with respect to fracture backdoors.
On the relaxed maximum-likelihood blind MIMO channel estimation for orthogonal space-time block codes
Venue: arXiv cs.IT 2020
Year: 2020

This paper concerns the maximum-likelihood channel estimation for MIMO systems with orthogonal space-time block codes when the finite alphabet constraint of the signal constellation is relaxed. We study the channel coefficients estimation subspace generated by this method. We provide an algebraic characterisation of this subspace which turns the optimization problem into a purely algebraic one and more importantly, leads to several interesting analytical proofs. We prove that with probability one, the dimension of the estimation subspace for the channel coefficients is deterministic and it decreases by increasing the number of receive antennas up to a certain critical number of receive antennas, after which the dimension remains constant. In fact, we show that beyond this critical number of receive antennas, the estimation subspace for the channel coefficients is isometric to a fixed deterministic invariant space which can be easily computed for every specific OSTB code.
DroneCells: Improving 5G Spectral Efficiency using Drone-mounted Flying Base Stations
Venue: arXiv cs.NI 2020
Year: 2020

We study a cellular networking scenario, called DroneCells, where miniaturized base stations (BSs) are mounted on flying drones to serve mobile users. We propose that the drones never stop, and move continuously within the cell in a way that reduces the distance between the BS and the serving users, thus potentially improving the spectral efficiency of the network. By considering the practical mobility constraints of commercial drones, we design drone mobility algorithms to improve the spectral efficiency of DroneCells. As the optimal problem is NP-hard, we propose a range of practically realizable heuristics with varying complexity and performance. Simulations show that, using the existing consumer drones, the proposed algorithms can readily improve spectral efficiency by 34\% and the 5-percentile packet throughput by 50\% compared to the scenario, where drones hover over fixed locations. More significant gains can be expected with more agile drones in the future. A surprising outcome is that the drones need to fly only at minimal speeds to achieve these gains, avoiding any negative effect on drone battery lifetime. We further demonstrate that the optimal solution provides only modest improvements over the best heuristic algorithm, which employs Game Theory to make mobility decisions for drone BSs.
Random Walks on Small World Networks
Venue: arXiv cs.DM 2020
Year: 2020

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices $\{u,v\}$ with distance $d>1$ is added as a "long-range" edge with probability proportional to $d^{-r}$, where $r\geq 0$ is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is $O((\log n)^2)$ when $r=2$ and $n^{Ω(1)}$ when $r\neq 2$. Here, we prove that the random walk also undergoes a phase transition at $r=2$, but in this case the phase transition is of a different form. We establish that the mixing time is $Θ(\log n)$ for $r<2$, $O((\log n)^4)$ for $r=2$ and $n^{Ω(1)}$ for $r>2$.
Tailoring Artificial Neural Networks for Optimal Learning
Venue: arXiv cs.LG 2020
Year: 2020

As one of the most important paradigms of recurrent neural networks, the echo state network (ESN) has been applied to a wide range of fields, from robotics to medicine, finance, and language processing. A key feature of the ESN paradigm is its reservoir --- a directed and weighted network of neurons that projects the input time series into a high dimensional space where linear regression or classification can be applied. Despite extensive studies, the impact of the reservoir network on the ESN performance remains unclear. Combining tools from physics, dynamical systems and network science, we attempt to open the black box of ESN and offer insights to understand the behavior of general artificial neural networks. Through spectral analysis of the reservoir network we reveal a key factor that largely determines the ESN memory capacity and hence affects its performance. Moreover, we find that adding short loops to the reservoir network can tailor ESN for specific tasks and optimize learning. We validate our findings by applying ESN to forecast both synthetic and real benchmark time series. Our results provide a new way to design task-specific ESN. More importantly, it demonstrates the power of combining tools from physics, dynamical systems and network science to offer new insights in understanding the mechanisms of general artificial neural networks.