OpenRaiser/Intern-Atlas huggingface dataset:
Safe Mutations for Deep and Recurrent Neural Networks through Output Gradients
Venue: arXiv cs.NE 2018
Year: 2018

While neuroevolution (evolving neural networks) has a successful track record across a variety of domains from reinforcement learning to artificial life, it is rarely applied to large, deep neural networks. A central reason is that while random mutation generally works in low dimensions, a random perturbation of thousands or millions of weights is likely to break existing functionality, providing no learning signal even if some individual weight changes were beneficial. This paper proposes a solution by introducing a family of safe mutation (SM) operators that aim within the mutation operator itself to find a degree of change that does not alter network behavior too much, but still facilitates exploration. Importantly, these SM operators do not require any additional interactions with the environment. The most effective SM variant capitalizes on the intriguing opportunity to scale the degree of mutation of each individual weight according to the sensitivity of the network's outputs to that weight, which requires computing the gradient of outputs with respect to the weights (instead of the gradient of error, as in conventional deep learning). This safe mutation through gradients (SM-G) operator dramatically increases the ability of a simple genetic algorithm-based neuroevolution method to find solutions in high-dimensional domains that require deep and/or recurrent neural networks (which tend to be particularly brittle to mutation), including domains that require processing raw pixels. By improving our ability to evolve deep neural networks, this new safer approach to mutation expands the scope of domains amenable to neuroevolution.
Dimensions of nonbinary antiprimitive BCH codes and some conjectures
Venue: arXiv cs.IT 2018
Year: 2018

Bose-Chaudhuri-Hocquenghem (BCH) codes have been intensively investigated. Even so, there is only a little known about primitive BCH codes, let alone non-primitive ones. In this paper, let $q>2$ be a prime power, the dimension of a family of non-primitive BCH codes of length $n=q^{m}+1$ (also called antiprimitive) is studied. These codes are also linear codes with complementary duals (called LCD codes). Through some approaches such as iterative algorithm, partition and scaling, all coset leaders of $C_{x}$ modulo $n$ with $q^{\lceil \frac{m}{2}\rceil}<x\leq 2q^{\lceil\frac{m}{2} \rceil}+2$ are given for $m\geq 4$. And for odd $m$ the first several largest coset leaders modulo $n$ are determined. Furthermore, a new kind of sequences is introduced to determine the second largest coset leader modulo $n$ with $m$ even and $q$ odd. Also, for even $m$ some conjectures about the first several coset leaders modulo $n$ are proposed, whose complete verification would wipe out the difficult problem to determine the first several coset leaders of antiprimitive BCH codes. After deriving the cardinalities of the coset leaders, we shall calculate exact dimensions of many antiprimitive LCD BCH codes.
An Analysis of Packet Fragmentation Impact in LPWAN
Venue: arXiv cs.NI 2018
Year: 2018

Packet fragmentation has mostly been addressed in the literature when referring to splitting data that does not fit a frame. It has received attention in the IoT community after the 6LoWPAN working group of IETF started studying the fragmentation headers to allow IPv6 1280 B MTU to be sent over IEEE 802.15.4 networks supporting a 127 B MTU. In this paper, and following some of the recent directions taken by the IETF LPWAN WG, an analysis of packet fragmentation in LPWANs has been done. We aim to identify the impact of sending the data in smaller fragments considering the restrictions of industrial duty-cycled networks. The analyzed parameters were the energy consumption, throughput, goodput and end to end delay introduced by fragmentation. The results of our analysis show that packet fragmentation can increase the reliability of the communication in duty-cycle restricted networks. This is of especial relevance when densifying the network. We observed relevant impact in energy consumption and extra latency, and identified the need for acknowledgements from the gateway/sink to exploit some of the benefits raised by fragmentation.
Mixin Composition Synthesis based on Intersection Types
Venue: arXiv cs.LO 2018
Year: 2018

We present a method for synthesizing compositions of mixins using type inhabitation in intersection types. First, recursively defined classes and mixins, which are functions over classes, are expressed as terms in a lambda calculus with records. Intersection types with records and record-merge are used to assign meaningful types to these terms without resorting to recursive types. Second, typed terms are translated to a repository of typed combinators. We show a relation between record types with record-merge and intersection types with constructors. This relation is used to prove soundness and partial completeness of the translation with respect to mixin composition synthesis. Furthermore, we demonstrate how a translated repository and goal type can be used as input to an existing framework for composition synthesis in bounded combinatory logic via type inhabitation. The computed result is a class typed by the goal type and generated by a mixin composition applied to an existing class.
Query-Efficient Black-box Adversarial Examples (superceded)
Venue: arXiv cs.CV 2018
Year: 2018

Note that this paper is superceded by "Black-Box Adversarial Attacks with Limited Queries and Information." Current neural network-based image classifiers are susceptible to adversarial examples, even in the black-box setting, where the attacker is limited to query access without access to gradients. Previous methods --- substitute networks and coordinate-based finite-difference methods --- are either unreliable or query-inefficient, making these methods impractical for certain problems. We introduce a new method for reliably generating adversarial examples under more restricted, practical black-box threat models. First, we apply natural evolution strategies to perform black-box attacks using two to three orders of magnitude fewer queries than previous methods. Second, we introduce a new algorithm to perform targeted adversarial attacks in the partial-information setting, where the attacker only has access to a limited number of target classes. Using these techniques, we successfully perform the first targeted adversarial attack against a commercially deployed machine learning system, the Google Cloud Vision API, in the partial information setting.
Intelligent Power Control for Spectrum Sharing in Cognitive Radios: A Deep Reinforcement Learning Approach
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of spectrum sharing in a cognitive radio system consisting of a primary user and a secondary user. The primary user and the secondary user work in a non-cooperative manner. Specifically, the primary user is assumed to update its transmit power based on a pre-defined power control policy. The secondary user does not have any knowledge about the primary user's transmit power, or its power control strategy. The objective of this paper is to develop a learning-based power control method for the secondary user in order to share the common spectrum with the primary user. To assist the secondary user, a set of sensor nodes are spatially deployed to collect the received signal strength information at different locations in the wireless environment. We develop a deep reinforcement learning-based method, which the secondary user can use to intelligently adjust its transmit power such that after a few rounds of interaction with the primary user, both users can transmit their own data successfully with required qualities of service. Our experimental results show that the secondary user can interact with the primary user efficiently to reach a goal state (defined as a state in which both users can successfully transmit their data) from any initial states within a few number of steps.
Efficiently Decodable Non-Adaptive Threshold Group Testing
Venue: arXiv cs.IT 2018
Year: 2018

We consider non-adaptive threshold group testing for identification of up to $d$ defective items in a set of $n$ items, where a test is positive if it contains at least $2 \leq u \leq d$ defective items, and negative otherwise. The defective items can be identified using $t = O \left( \left( \frac{d}{u} \right)^u \left( \frac{d}{d - u} \right)^{d-u} \left(u \log{\frac{d}{u}} + \log{\frac{1}ε} \right) \cdot d^2 \log{n} \right)$ tests with probability at least $1 - ε$ for any $ε> 0$ or $t = O \left( \left( \frac{d}{u} \right)^u \left( \frac{d}{d -u} \right)^{d - u} d^3 \log{n} \cdot \log{\frac{n}{d}} \right)$ tests with probability 1. The decoding time is $t \times \mathrm{poly}(d^2 \log{n})$. This result significantly improves the best known results for decoding non-adaptive threshold group testing: $O(n\log{n} + n \log{\frac{1}ε})$ for probabilistic decoding, where $ε> 0$, and $O(n^u \log{n})$ for deterministic decoding.
Differentially Private Federated Learning: A Client Level Perspective
Venue: arXiv cs.CR 2018
Year: 2018

Federated learning is a recent advance in privacy protection. In this context, a trusted curator aggregates parameters optimized in decentralized fashion by multiple clients. The resulting model is then distributed back to all clients, ultimately converging to a joint representative model without explicitly having to share the data. However, the protocol is vulnerable to differential attacks, which could originate from any party contributing during federated optimization. In such an attack, a client's contribution during training and information about their data set is revealed through analyzing the distributed model. We tackle this problem and propose an algorithm for client sided differential privacy preserving federated optimization. The aim is to hide clients' contributions during training, balancing the trade-off between privacy loss and model performance. Empirical studies suggest that given a sufficiently large number of participating clients, our proposed procedure can maintain client-level differential privacy at only a minor cost in model performance.
MATE robots simplifying my work: benefits and socio-ethical implications
Venue: arXiv cs.HC 2018
Year: 2018

With the increasing complexity of modern industrial automatic and robotic systems, an increasing burden is put on the operators, who are requested to supervise and interact with very complex systems, typically under challenging and stressful conditions. To overcome this issue, it is necessary to adopt a responsible approach based on the anthropocentric design methodology, such that machines adapt to the humans capabilities, and not vice versa. Moving along these lines, in this paper we consider an integrated methodological design approach, which we call MATE, consisting in devising complex automatic or robotic solutions that measure current operator's status, adapting the interaction accordingly, and providing her/him with proper training to improve the interaction and learn lacking skills and expertise. Accordingly, a MATE system is intended to be easily usable for all users, thus meeting the principles of inclusive design. Using such a MATE system gives rise to several ethical and social implications, which are discussed in this paper. Additionally, a discussion about which factors in the organization of companies are critical with respect to the introduction of a MATE system is presented.
A Deep Policy Inference Q-Network for Multi-Agent Systems
Venue: arXiv cs.AI 2018
Year: 2018

We present DPIQN, a deep policy inference Q-network that targets multi-agent systems composed of controllable agents, collaborators, and opponents that interact with each other. We focus on one challenging issue in such systems---modeling agents with varying strategies---and propose to employ "policy features" learned from raw observations (e.g., raw images) of collaborators and opponents by inferring their policies. DPIQN incorporates the learned policy features as a hidden vector into its own deep Q-network (DQN), such that it is able to predict better Q values for the controllable agents than the state-of-the-art deep reinforcement learning models. We further propose an enhanced version of DPIQN, called deep recurrent policy inference Q-network (DRPIQN), for handling partial observability. Both DPIQN and DRPIQN are trained by an adaptive training procedure, which adjusts the network's attention to learn the policy features and its own Q-values at different phases of the training process. We present a comprehensive analysis of DPIQN and DRPIQN, and highlight their effectiveness and generalizability in various multi-agent settings. Our models are evaluated in a classic soccer game involving both competitive and collaborative scenarios. Experimental results performed on 1 vs. 1 and 2 vs. 2 games show that DPIQN and DRPIQN demonstrate superior performance to the baseline DQN and deep recurrent Q-network (DRQN) models. We also explore scenarios in which collaborators or opponents dynamically change their policies, and show that DPIQN and DRPIQN do lead to better overall performance in terms of stability and mean scores.
Encoding CNN Activations for Writer Recognition
Venue: arXiv cs.CV 2018
Year: 2018

The encoding of local features is an essential part for writer identification and writer retrieval. While CNN activations have already been used as local features in related works, the encoding of these features has attracted little attention so far. In this work, we compare the established VLAD encoding with triangulation embedding. We further investigate generalized max pooling as an alternative to sum pooling and the impact of decorrelation and Exemplar SVMs. With these techniques, we set new standards on two publicly available datasets (ICDAR13, KHATT).
Wadge Degrees of $ω$-Languages of Petri Nets
Venue: arXiv cs.LO 2018
Year: 2018

We prove that $ω$-languages of (non-deterministic) Petri nets and $ω$-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of $ω$-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of $ω$-languages of (non-deterministic) Turing machines which also form the class of effective analytic sets. In particular, for each non-null recursive ordinal $α< ω\_1^{\rm CK} $ there exist some ${\bf Σ}^0\_α$-complete and some ${\bf Π}^0\_α$-complete $ω$-languages of Petri nets, and the supremum of the set of Borel ranks of $ω$-languages of Petri nets is the ordinal $γ\_2^1$, which is strictly greater than the first non-recursive ordinal $ω\_1^{\rm CK}$. We also prove that there are some ${\bf Σ}\_1^1$-complete, hence non-Borel, $ω$-languages of Petri nets, and that it is consistent with ZFC that there exist some $ω$-languages of Petri nets which are neither Borel nor ${\bf Σ}\_1^1$-complete. This answers the question of the topological complexity of $ω$-languages of (non-deterministic) Petri nets which was left open in [DFR14,FS14].
Recursive Programs for Document Spanners
Venue: arXiv cs.DB 2018
Year: 2018

A document spanner models a program for Information Extraction (IE) as a function that takes as input a text document (string over a finite alphabet) and produces a relation of spans (intervals in the document) over a predefined schema. A well studied language for expressing spanners is that of the regular spanners: relational algebra over regex formulas, which are obtained by adding capture variables to regular expressions. Equivalently, the regular spanners are the ones expressible in non-recursive Datalog over regex formulas (extracting relations that play the role of EDBs from the input document). In this paper, we investigate the expressive power of recursive Datalog over regex formulas. Our main result is that such programs capture precisely the document spanners computable in polynomial time. Additional results compare recursive programs to known formalisms such as the language of core spanners (that extends regular spanners by allowing to test for string equality) and its closure under difference. Finally, we extend our main result to a recently proposed framework that generalizes both the relational model and document spanners.
A Primal-Dual Method for Optimal Control and Trajectory Generation in High-Dimensional Systems
Venue: arXiv cs.SY 2018
Year: 2018

Presented is a method for efficient computation of the Hamilton-Jacobi (HJ) equation for time-optimal control problems using the generalized Hopf formula. Typically, numerical methods to solve the HJ equation rely on a discrete grid of the solution space and exhibit exponential scaling with dimension. The generalized Hopf formula avoids the use of grids and numerical gradients by formulating an unconstrained convex optimization problem. The solution at each point is completely independent, and allows a massively parallel implementation if solutions at multiple points are desired. This work presents a primal-dual method for efficient numeric solution and presents how the resulting optimal trajectory can be generated directly from the solution of the Hopf formula, without further optimization. Examples presented have execution times on the order of milliseconds and experiments show computation scales approximately polynomial in dimension with very small high-order coefficients.
Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers
Venue: arXiv cs.IT 2018
Year: 2018

We propose two coded schemes for the distributed computing problem of multiplying a matrix by a set of vectors. The first scheme is based on partitioning the matrix into submatrices and applying maximum distance separable (MDS) codes to each submatrix. For this scheme, we prove that up to a given number of partitions the communication load and the computational delay (not including the encoding and decoding delay) are identical to those of the scheme recently proposed by Li et al., based on a single, long MDS code. However, due to the use of shorter MDS codes, our scheme yields a significantly lower overall computational delay when the delay incurred by encoding and decoding is also considered. We further propose a second coded scheme based on Luby Transform (LT) codes under inactivation decoding. Interestingly, LT codes may reduce the delay over the partitioned scheme at the expense of an increased communication load. We also consider distributed computing under a deadline and show numerically that the proposed schemes outperform other schemes in the literature, with the LT code-based scheme yielding the best performance for the scenarios considered.
Interventions over Predictions: Reframing the Ethical Debate for Actuarial Risk Assessment
Venue: arXiv cs.LG 2018
Year: 2018

Actuarial risk assessments might be unduly perceived as a neutral way to counteract implicit bias and increase the fairness of decisions made at almost every juncture of the criminal justice system, from pretrial release to sentencing, parole and probation. In recent times these assessments have come under increased scrutiny, as critics claim that the statistical techniques underlying them might reproduce existing patterns of discrimination and historical biases that are reflected in the data. Much of this debate is centered around competing notions of fairness and predictive accuracy, resting on the contested use of variables that act as "proxies" for characteristics legally protected against discrimination, such as race and gender. We argue that a core ethical debate surrounding the use of regression in risk assessments is not simply one of bias or accuracy. Rather, it's one of purpose. If machine learning is operationalized merely in the service of predicting individual future crime, then it becomes difficult to break cycles of criminalization that are driven by the iatrogenic effects of the criminal justice system itself. We posit that machine learning should not be used for prediction, but rather to surface covariates that are fed into a causal model for understanding the social, structural and psychological drivers of crime. We propose an alternative application of machine learning and causal inference away from predicting risk scores to risk mitigation.
Intelligent Device Discovery in the Internet of Things - Enabling the Robot Society
Venue: arXiv cs.AI 2018
Year: 2018

The Internet of Things (IoT) is continuously growing to connect billions of smart devices anywhere and anytime in an Internet-like structure, which enables a variety of applications, services and interactions between human and objects. In the future, the smart devices are supposed to be able to autonomously discover a target device with desired features and generate a set of entirely new services and applications that are not supervised or even imagined by human beings. The pervasiveness of smart devices, as well as the heterogeneity of their design and functionalities, raise a major concern: How can a smart device efficiently discover a desired target device? In this paper, we propose a Social-Aware and Distributed (SAND) scheme that achieves a fast, scalable and efficient device discovery in the IoT. The proposed SAND scheme adopts a novel device ranking criteria that measures the device's degree, social relationship diversity, clustering coefficient and betweenness. Based on the device ranking criteria, the discovery request can be guided to travel through critical devices that stand at the major intersections of the network, and thus quickly reach the desired target device by contacting only a limited number of intermediate devices. With the help of such an intelligent device discovery as SAND, the IoT devices, as well as other computing facilities, software and data on the Internet, can autonomously establish new social connections with each other as human being do. They can formulate self-organized computing groups to perform required computing tasks, facilitate a fusion of a variety of computing service, network service and data to generate novel applications and services, evolve from the individual aritificial intelligence to the collaborative intelligence, and eventually enable the birth of a robot society.
Work Analysis with Resource-Aware Session Types
Venue: arXiv cs.PL 2018
Year: 2018

While there exist several successful techniques for supporting programmers in deriving static resource bounds for sequential code, analyzing the resource usage of message-passing concurrent processes poses additional challenges. To meet these challenges, this article presents an analysis for statically deriving worst-case bounds on the total work performed by message-passing processes. To decompose interacting processes into components that can be analyzed in isolation, the analysis is based on novel resource-aware session types, which describe protocols and resource contracts for inter-process communication. A key innovation is that both messages and processes carry potential to share and amortize cost while communicating. To symbolically express resource usage in a setting without static data structures and intrinsic sizes, resource contracts describe bounds that are functions of interactions between processes. Resource-aware session types combine standard binary session types and type-based amortized resource analysis in a linear type system. This type system is formulated for a core session-type calculus of the language SILL and proved sound with respect to a multiset-based operational cost semantics that tracks the total number of messages that are exchanged in a system. The effectiveness of the analysis is demonstrated by analyzing standard examples from amortized analysis and the literature on session types and by a comparative performance analysis of different concurrent programs implementing the same interface.