OpenRaiser/Intern-Atlas huggingface dataset:
On the Degree of Boolean Functions as Polynomials over $\mathbb{Z}_m$
Venue: arXiv cs.CC 2020
Year: 2020

Polynomial representations of Boolean functions over various rings such as $\mathbb{Z}$ and $\mathbb{Z}_m$ have been studied since Minsky and Papert (1969). From then on, they have been employed in a large variety of fields including communication complexity, circuit complexity, learning theory, coding theory and so on. For any integer $m\ge2$, each Boolean function has a unique multilinear polynomial representation over ring $\mathbb Z_m$. The degree of such polynomial is called modulo-$m$ degree, denoted as $\mathrm{deg}_m(\cdot)$. In this paper, we investigate the lower bound of modulo-$m$ degree of Boolean functions. When $m=p^k$ ($k\ge 1$) for some prime $p$, we give a tight lower bound that $\mathrm{deg}_m(f)\geq k(p-1)$ for any non-degenerated function $f:\{0,1\}^n\to\{0,1\}$, provided that $n$ is sufficient large. When $m$ contains two different prime factors $p$ and $q$, we give a nearly optimal lower bound for any symmetric function $f:\{0,1\}^n\to\{0,1\}$ that $\mathrm{deg}_m(f) \geq \frac{n}{2+\frac{1}{p-1}+\frac{1}{q-1}}$.
LUTNet: Learning FPGA Configurations for Highly Efficient Neural Network Inference
Venue: arXiv cs.LG 2020
Year: 2020

Research has shown that deep neural networks contain significant redundancy, and thus that high classification accuracy can be achieved even when weights and activations are quantized down to binary values. Network binarization on FPGAs greatly increases area efficiency by replacing resource-hungry multipliers with lightweight XNOR gates. However, an FPGA's fundamental building block, the K-LUT, is capable of implementing far more than an XNOR: it can perform any K-input Boolean operation. Inspired by this observation, we propose LUTNet, an end-to-end hardware-software framework for the construction of area-efficient FPGA-based neural network accelerators using the native LUTs as inference operators. We describe the realization of both unrolled and tiled LUTNet architectures, with the latter facilitating smaller, less power-hungry deployment over the former while sacrificing area and energy efficiency along with throughput. For both varieties, we demonstrate that the exploitation of LUT flexibility allows for far heavier pruning than possible in prior works, resulting in significant area savings while achieving comparable accuracy. Against the state-of-the-art binarized neural network implementation, we achieve up to twice the area efficiency for several standard network models when inferencing popular datasets. We also demonstrate that even greater energy efficiency improvements are obtainable.
Massive Access for Future Wireless Communication Systems
Venue: arXiv cs.IT 2020
Year: 2020

Multiple access technology played an important role in wireless communication in the last decades: it increases the capacity of the channel and allows different users to access the system simultaneously. However, the conventional multiple access technology, as originally designed for current human-centric wireless networks, is not scalable for future machine-centric wireless networks. Massive access (studied in the literature under such names as massive-device multiple access, unsourced massive random access, massive connectivity, massive machine-type communication, and many-access channels) exhibits a clean break with current networks by potentially supporting millions of devices in each cellular network. The tremendous growth in the number of connected devices requires a fundamental rethinking of the conventional multiple access technologies in favor of new schemes suited for massive random access. Among the many new challenges arising in this setting, the most relevant are: the fundamental limits of communication from a massive number of bursty devices transmitting simultaneously with short packets, the design of low complexity and energy-efficient massive access coding and communication schemes, efficient methods for the detection of a relatively small number of active users among a large number of potential user devices with sporadic transmission pattern, and the integration of massive access with massive MIMO and other important wireless communication technologies. This paper presents an overview of the concept of massive access wireless communication and of the contemporary research on this important topic.
Computer-supported Exploration of a Categorical Axiomatization of Modeloids
Venue: arXiv cs.LO 2020
Year: 2020

A modeloid, a certain set of partial bijections, emerges from the idea to abstract from a structure to the set of its partial automorphisms. It comes with an operation, called the derivative, which is inspired by Ehrenfeucht-Fraïssé games. In this paper we develop a generalization of a modeloid first to an inverse semigroup and then to an inverse category using an axiomatic approach to category theory. We then show that this formulation enables a purely algebraic view on Ehrenfeucht-Fraïssé games.
Hyperbolic Node Embedding for Signed Networks
Venue: arXiv cs.LG 2020
Year: 2020

Signed network embedding methods aim to learn vector representations of nodes in signed networks. However, existing algorithms only managed to embed networks into low-dimensional Euclidean spaces whereas many intrinsic features of signed networks are reported more suitable for non-Euclidean spaces. For instance, previous works did not consider the hierarchical structures of networks, which is widely witnessed in real-world networks. In this work, we answer an open question that whether the hyperbolic space is a better choice to accommodate signed networks and learn embeddings that can preserve the corresponding special characteristics. We also propose a non-Euclidean signed network embedding method based on structural balance theory and Riemannian optimization, which embeds signed networks into a Poincaré ball in a hyperbolic space. This space enables our approach to capture underlying hierarchy of nodes in signed networks because it can be seen as a continuous tree. We empirically compare our method against six Euclidean-based baselines in three tasks on seven real-world datasets, and the results show the effectiveness of our method.
JarKA: Modeling Attribute Interactions for Cross-lingual Knowledge Alignment
Venue: arXiv cs.CL 2020
Year: 2020

Abstract. Cross-lingual knowledge alignment is the cornerstone in building a comprehensive knowledge graph (KG), which can benefit various knowledge-driven applications. As the structures of KGs are usually sparse, attributes of entities may play an important role in aligning the entities. However, the heterogeneity of the attributes across KGs prevents from accurately embedding and comparing entities. To deal with the issue, we propose to model the interactions between attributes, instead of globally embedding an entity with all the attributes. We further propose a joint framework to merge the alignments inferred from the attributes and the structures. Experimental results show that the proposed model outperforms the state-of-art baselines by up to 38.48% HitRatio@1. The results also demonstrate that our model can infer the alignments between attributes, relationships and values, in addition to entities.
Predicting gait events from tibial acceleration in rearfoot running: a structured machine learning approach
Venue: arXiv cs.LG 2020
Year: 2020

Gait event detection of the initial contact and toe off is essential for running gait analysis, allowing the derivation of parameters such as stance time. Heuristic-based methods exist to estimate these key gait events from tibial accelerometry. However, these methods are tailored to very specific acceleration profiles, which may offer complications when dealing with larger data sets and inherent biological variability. Therefore, this paper investigates whether a structured machine learning approach can achieve a more accurate prediction of running gait event timings from tibial accelerometry. Force-based event detection acted as the criterion measure in order to assess the accuracy, repeatability and sensitivity of the predicted gait events. A heuristic method and two structured machine learning methods were employed to derive initial contact, toe off and stance time from tibial acceleration signals. Both a structured perceptron model (median absolute error of stance time estimation: 10.00 $\pm$ 8.73 ms) and a structured recurrent neural network model (median absolute error of stance time estimation: 6.50 $\pm$ 5.74 ms) significantly outperformed the existing heuristic approach (median absolute error of stance time estimation: 11.25 $\pm$ 9.52 ms) on data from 93 rearfoot runners. Thus, results indicate that a structured recurrent neural network machine learning model offers the most accurate and consistent estimation of the gait events and its derived stance time during level overground running. The machine learning methods seem less affected by intra- and inter-subject variation within the data, allowing for accurate and efficient automated data output during rearfoot overground running. Furthermore offering possibilities for real-time monitoring and biofeedback during prolonged measurements, even outside the laboratory.
Generalization of Reinforcement Learners with Working and Episodic Memory
Venue: arXiv cs.LG 2020
Year: 2020

Memory is an important aspect of intelligence and plays a role in many deep reinforcement learning models. However, little progress has been made in understanding when specific memory systems help more than others and how well they generalize. The field also has yet to see a prevalent consistent and rigorous approach for evaluating agent performance on holdout data. In this paper, we aim to develop a comprehensive methodology to test different kinds of memory in an agent and assess how well the agent can apply what it learns in training to a holdout set that differs from the training set along dimensions that we suggest are relevant for evaluating memory-specific generalization. To that end, we first construct a diverse set of memory tasks that allow us to evaluate test-time generalization across multiple dimensions. Second, we develop and perform multiple ablations on an agent architecture that combines multiple memory systems, observe its baseline models, and investigate its performance against the task suite.
Balancing Gaussian vectors in high dimension
Venue: arXiv cs.DM 2020
Year: 2020

Motivated by problems in controlled experiments, we study the discrepancy of random matrices with continuous entries where the number of columns $n$ is much larger than the number of rows $m$. Our first result shows that if $ω(1) = m = o(n)$, a matrix with i.i.d. standard Gaussian entries has discrepancy $Θ(\sqrt{n} \, 2^{-n/m})$ with high probability. This provides sharp guarantees for Gaussian discrepancy in a regime that had not been considered before in the existing literature. Our results also apply to a more general family of random matrices with continuous i.i.d entries, assuming that $m = O(n/\log{n})$. The proof is non-constructive and is an application of the second moment method. Our second result is algorithmic and applies to random matrices whose entries are i.i.d. and have a Lipschitz density. We present a randomized polynomial-time algorithm that achieves discrepancy $e^{-Ω(\log^2(n)/m)}$ with high probability, provided that $m = O(\sqrt{\log{n}})$. In the one-dimensional case, this matches the best known algorithmic guarantees due to Karmarkar--Karp. For higher dimensions $2 \leq m = O(\sqrt{\log{n}})$, this establishes the first efficient algorithm achieving discrepancy smaller than $O( \sqrt{m} )$.
Distributed Relay Selection in Presence of Dynamic Obstacles in Millimeter Wave D2D Communication
Venue: arXiv cs.NI 2020
Year: 2020

Millimeter wave (mmWave) device to device (D2D) communication is highly susceptible to obstacles due to severe penetration losses and requires almost a line of sight (LOS) communication path. D2D channel condition is local to devices/user equipments (UEs) and hence is \textit{not} directly visible to the base station (BS). Thus quality of the D2D channel needs to be propagated to BS by UEs which may incur some delay. Hence the solution provided by BS to UEs using this gathered channel information might become less useful to establish communication due to moving obstacles. These types of obstacles might not be known in advance and hence may cause unpredictable fluctuations to the D2D channel quality. Hence we seek to learn the D2D channels using the finite horizon partially observable Markov decision process (POMDP) framework to model the uncertainty in such kind of network environments with dynamic obstacles. The objective is to minimize delay when channel quality deteriorates, by making UEs choose locally the best possible decision between i) to continue on the current relay link on which communication is taking place or ii) to switch to another good relay by exploring other possible UEs in its locality. We derive an optimal threshold policy which tells the UE to take appropriate decision locally. Later, we give a simplified and easy to implement stationary threshold policy which counts the number of successive acknowledgement failures, based on which UE make appropriate decision locally. Through extensive simulation, we demonstrate that our approach outperforms recent algorithms.
ALERT: Accurate Learning for Energy and Timeliness
Venue: arXiv cs.PF 2020
Year: 2020

An increasing number of software applications incorporate runtime Deep Neural Networks (DNNs) to process sensor data and return inference results to humans. Effective deployment of DNNs in these interactive scenarios requires meeting latency and accuracy constraints while minimizing energy, a problem exacerbated by common system dynamics. Prior approaches handle dynamics through either (1) system-oblivious DNN adaptation, which adjusts DNN latency/accuracy tradeoffs, or (2) application-oblivious system adaptation, which adjusts resources to change latency/energy tradeoffs. In contrast, this paper improves on the state-of-the-art by coordinating application- and system-level adaptation. ALERT, our runtime scheduler, uses a probabilistic model to detect environmental volatility and then simultaneously select both a DNN and a system resource configuration to meet latency, accuracy, and energy constraints. We evaluate ALERT on CPU and GPU platforms for image and speech tasks in dynamic environments. ALERT's holistic approach achieves more than 13% energy reduction, and 27% error reduction over prior approaches that adapt solely at the application or system level. Furthermore, ALERT incurs only 3% more energy consumption and 2% higher DNN-inference error than an oracle scheme with perfect application and system knowledge.
Centroid Based Concept Learning for RGB-D Indoor Scene Classification
Venue: arXiv cs.CV 2020
Year: 2020

This paper contributes a novel cognitively-inspired method for RGB-D indoor scene classification. High intra-class variance and low inter-class variance make indoor scene classification an extremely challenging task. To cope with this problem, we propose a clustering approach inspired by the concept learning model of the hippocampus and the neocortex, to generate clusters and centroids for different scene categories. Test images depicting different scenes are classified by using their distance to the closest centroids (concepts). Modeling of RGB-D scenes as centroids not only leads to state-of-the-art classification performance on benchmark datasets (SUN RGB-D and NYU Depth V2), but also offers a method for inspecting and interpreting the space of centroids. Inspection of the centroids generated by our approach on RGB-D datasets leads us to propose a method for merging conceptually similar categories, resulting in improved accuracy for all approaches.
Generalized Speedy Q-learning
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we derive a generalization of the Speedy Q-learning (SQL) algorithm that was proposed in the Reinforcement Learning (RL) literature to handle slow convergence of Watkins' Q-learning. In most RL algorithms such as Q-learning, the Bellman equation and the Bellman operator play an important role. It is possible to generalize the Bellman operator using the technique of successive relaxation. We use the generalized Bellman operator to derive a simple and efficient family of algorithms called Generalized Speedy Q-learning (GSQL-w) and analyze its finite time performance. We show that GSQL-w has an improved finite time performance bound compared to SQL for the case when the relaxation parameter w is greater than 1. This improvement is a consequence of the contraction factor of the generalized Bellman operator being less than that of the standard Bellman operator. Numerical experiments are provided to demonstrate the empirical performance of the GSQL-w algorithm.
Explanation by Progressive Exaggeration
Venue: arXiv cs.LG 2020
Year: 2020

As machine learning methods see greater adoption and implementation in high stakes applications such as medical image diagnosis, the need for model interpretability and explanation has become more critical. Classical approaches that assess feature importance (e.g. saliency maps) do not explain how and why a particular region of an image is relevant to the prediction. We propose a method that explains the outcome of a classification black-box by gradually exaggerating the semantic effect of a given class. Given a query input to a classifier, our method produces a progressive set of plausible variations of that query, which gradually changes the posterior probability from its original class to its negation. These counter-factually generated samples preserve features unrelated to the classification decision, such that a user can employ our method as a "tuning knob" to traverse a data manifold while crossing the decision boundary. Our method is model agnostic and only requires the output value and gradient of the predictor with respect to its input.
Program Sketching with Live Bidirectional Evaluation
Venue: arXiv cs.PL 2020
Year: 2020

We present a system called Smyth for program sketching in a typed functional language whereby the concrete evaluation of ordinary assertions gives rise to input-output examples, which are then used to guide the search to complete the holes. The key innovation, called live bidirectional evaluation, propagates examples "backward" through partially evaluated sketches. Live bidirectional evaluation enables Smyth to (a) synthesize recursive functions without trace-complete sets of examples and (b) specify and solve interdependent synthesis goals. Eliminating the trace-completeness requirement resolves a significant limitation faced by prior synthesis techniques when given partial specifications in the form of input-output examples. To assess the practical implications of our techniques, we ran several experiments on benchmarks used to evaluate Myth, a state-of-the-art example-based synthesis tool. First, given expert examples (and no partial implementations), we find that Smyth requires on average 66% of the number of expert examples required by Myth. Second, we find that Smyth is robust to randomly-generated examples, synthesizing many tasks with relatively few more random examples than those provided by an expert. Third, we create a suite of small sketching tasks by systematically employing a simple sketching strategy to the Myth benchmarks; we find that user-provided sketches in Smyth often further reduce the total specification burden (i.e. the combination of partial implementations and examples). Lastly, we find that Leon and Synquid, two state-of-the-art logic-based synthesis tools, fail to complete several tasks on which Smyth succeeds.
InSpectre: Breaking and Fixing Microarchitectural Vulnerabilities by Formal Analysis
Venue: arXiv cs.CR 2020
Year: 2020

The recent Spectre attacks has demonstrated the fundamental insecurity of current computer microarchitecture. The attacks use features like pipelining, out-of-order and speculation to extract arbitrary information about the memory contents of a process. A comprehensive formal microarchitectural model capable of representing the forms of out-of-order and speculative behavior that can meaningfully be implemented in a high performance pipelined architecture has not yet emerged. Such a model would be very useful, as it would allow the existence and non-existence of vulnerabilities, and soundness of countermeasures to be formally established. In this paper we present such a model targeting single core processors. The model is intentionally very general and provides an infrastructure to define models of real CPUs. It incorporates microarchitectural features that underpin all known Spectre vulnerabilities. We use the model to elucidate the security of existing and new vulnerabilities, as well as to formally analyze the effectiveness of proposed countermeasures. Specifically, we discover three new (potential) vulnerabilities, including a new variant of Spectre v4, a vulnerability on speculative fetching, and a vulnerability on out-of-order execution, and analyze the effectiveness of three existing countermeasures: constant time, Retpoline, and ARM's Speculative Store Bypass Safe (SSBS).
Intelligent Reflecting Surface (IRS)-Enabled Covert Communications in Wireless Networks
Venue: arXiv cs.NI 2020
Year: 2020

With growing security threats to the evolving wireless systems, protecting user privacy becomes progressively challenging. Even if the transmitted information is encrypted and the potential wiretap channel is physically limited (e.g. through information-theoretic security approaches), the raw data itself, such as transmitter position and transmission pattern, could expose confidential information. In this context, covert communication that intends to hide the existence of transmission from an observant adversary by exploiting the physical characteristics of the wireless medium has been actively investigated. However, existing covertness techniques ineluctably consume additional resources such as bandwidth and energy, which burdens system deployment. In view of this concern, we propose an intelligent reflecting surface (IRS)-based approach to enhance communication covertness. The core idea is making use of a smartly controlled metasurface to reshape undesirable propagation conditions which could divulge secret messages. To facilitate the understanding of the proposed idea, we first provide an overview of the state-of-the-art covert communication techniques. Then, we introduce the fundamentals of IRS and elaborate on how an IRS can be integrated to benefit communication covertness. We also demonstrate a case study of the joint configuration of the IRS and the legitimate transmitter, which is of pivotal importance in designing an IRS-enhanced covert communication system. Finally, we shed light on some open research directions.
Inferring Lower Runtime Bounds for Integer Programs
Venue: arXiv cs.LO 2020
Year: 2020

We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symbolic representations of program executions using a framework for iterative, under-approximating program simplification. The core of this simplification is a method for (under-approximating) program acceleration based on recurrence solving and a variation of ranking functions. Afterwards, we deduce asymptotic lower bounds from the resulting simplified programs using a special-purpose calculus and an SMT encoding. We implemented our technique in our tool LoAT and show that it infers non-trivial lower bounds for a large class of examples.