OpenRaiser/Intern-Atlas huggingface dataset:
Reward Advancement: Transforming Policy under Maximum Causal Entropy Principle
Venue: arXiv cs.AI 2019
Year: 2019

Many real-world human behaviors can be characterized as a sequential decision making processes, such as urban travelers choices of transport modes and routes (Wu et al. 2017). Differing from choices controlled by machines, which in general follows perfect rationality to adopt the policy with the highest reward, studies have revealed that human agents make sub-optimal decisions under bounded rationality (Tao, Rohde, and Corcoran 2014). Such behaviors can be modeled using maximum causal entropy (MCE) principle (Ziebart 2010). In this paper, we define and investigate a general reward trans-formation problem (namely, reward advancement): Recovering the range of additional reward functions that transform the agent's policy from original policy to a predefined target policy under MCE principle. We show that given an MDP and a target policy, there are infinite many additional reward functions that can achieve the desired policy transformation. Moreover, we propose an algorithm to further extract the additional rewards with minimum "cost" to implement the policy transformation.
Walking Randomly, Massively, and Efficiently
Venue: arXiv cs.DS 2019
Year: 2019

We introduce a set of techniques that allow for efficiently generating many independent random walks in the Massive Parallel Computation (MPC) model with space per machine strongly sublinear in the number of vertices. In this space-per-machine regime, many natural approaches to graph problems struggle to overcome the $Θ(\log n)$ MPC round complexity barrier. Our techniques enable breaking this barrier for PageRank---one of the most important applications of random walks---even in more challenging directed graphs, and for approximate bipartiteness and expansion testing. In the undirected case, we start our random walks from the stationary distribution, which implies that we approximately know the empirical distribution of their next steps. This allows for preparing continuations of random walks in advance and applying a doubling approach. As a result we can generate multiple random walks of length $l$ in $Θ(\log l)$ rounds on MPC. Moreover, we show that under the popular 1-vs.-2-Cycles conjecture, this round complexity is asymptotically tight. For directed graphs, our approach stems from our treatment of the PageRank Markov chain. We first compute the PageRank for the undirected version of the input graph and then slowly transition towards the directed case, considering convex combinations of the transition matrices in the process. For PageRank, we achieve the following round complexities for damping factor equal to $1 - ε$: * in $O(\log \log n + \log 1 / ε)$ rounds for undirected graphs (with $\tilde O(m / ε^2)$ total space), * in $\tilde O(\log^2 \log n + \log^2 1/ε)$ rounds for directed graphs (with $\tilde O((m+n^{1+o(1)}) / poly\, ε)$ total space).
Generalized Mutual Information
Venue: arXiv cs.IT 2019
Year: 2019

Mutual information is one of the essential building blocks of information theory. Yet, it is only finitely defined for distributions with fast decaying tails on a countable joint alphabet of two random elements. The unboundedness of mutual information over the general class of all distributions on a joint alphabet prevents its potential utility to be fully realized. This is in fact a void in the foundation of information theory that needs to be filled. This article proposes a family of generalized mutual information all of whose members 1) are finitely defined for each and every distribution of two random elements on a joint countable alphabet, except the one by Shannon, and 2) enjoy all utilities of a finite Shannon's mutual information.
Entropy Estimation of Physically Unclonable Functions via Chow Parameters
Venue: arXiv cs.IT 2019
Year: 2019

A physically unclonable function (PUF) is an electronic circuit that produces an intrinsic identifier in response to a challenge. These identifiers depend on uncontrollable variations of the manufacturing process, which make them hard to predict or to replicate. Various security protocols leverage on such intrinsic randomness for authentification, cryptographic key generation, anti-counterfeiting, etc. Evaluating the entropy of PUFs (for all possible challenges) allows one to assess the security properties of such protocols. In this paper, we estimate the probability distribution of certain kinds of PUFs composed of $n$ delay elements. This is used to evaluate relevant Rényi entropies and determine how they increase with $n$. Such a problem was known to have extremely high complexity (in the order of $2^{2^n}$) and previous entropy estimations were carried out up to $n=7$. Making the link with the theory of Boolean threshold functions, we leverage on the representation by Chow parameters to estimate probability distributions up to $n=10$. The resulting Shannon entropy of the PUF is close to the max-entropy, which is asymptotically quadratic in $n$.
A Federated Lightweight Authentication Protocol for the Internet of Things
Venue: arXiv cs.CR 2019
Year: 2019

Considering the world's IoT development and market, it is necessary to guarantee the security of the developed IoT applications as well as the privacy of their end users. In this sense, Federated Identity Management (FIdM) systems can be of great help as they improve user authentication and privacy. In this paper, we claim that traditional FIdM are mostly cumbersome and then ill-suited for IoT. As a solution to this problem, we come up with a federated identity authentication protocol exclusively tailored to IoT. Federated Lightweight Authentication of Things (FLAT), our solution, replaces weighty protocols and asymmetric cryptographic primitives used in traditional FIdM by lighter ones. For instance, FLAT synergistically combines symmetric cryptosystems and Implicit Certificates. The results show that FLAT can reduce the data exchange overhead by around 31% when compared to a baseline solution. FLAT's Client is also more efficient than the baseline solution in terms of data transmitted, data received, total data exchange, and computation time. Our results indicate that FLAT runs efficiently even on top of resource-constrained devices like Arduino.
Tiny-Inception-ResNet-v2: Using Deep Learning for Eliminating Bonded Labors of Brick Kilns in South Asia
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes to employ a Inception-ResNet inspired deep learning architecture called Tiny-Inception-ResNet-v2 to eliminate bonded labor by identifying brick kilns within "Brick-Kiln-Belt" of South Asia. The framework is developed by training a network on the satellite imagery consisting of 11 different classes of South Asian region. The dataset developed during the process includes the geo-referenced images of brick kilns, houses, roads, tennis courts, farms, sparse trees, dense trees, orchards, parking lots, parks and barren lands. The dataset is made publicly available for further research. Our proposed network architecture with very fewer learning parameters outperforms all state-of-the-art architectures employed for recognition of brick kilns. Our proposed solution would enable regional monitoring and evaluation mechanisms for the Sustainable Development Goals.
Non-Orthogonal Multiple Access in UAV-to-Everything (U2X) Networks
Venue: arXiv cs.IT 2019
Year: 2019

This article investigates the non-orthogonal multiple access (NOMA) enhanced unmanned aerial vehicle (UAV)-to-Everything (U2X) frameworks. A novel 3-Dimension framework for providing wireless services to randomly roaming NOMA receivers (Rxs) in the sphere space is proposed by utilizing stochastic geometry tools. In an effort to evaluate the performance of the proposed framework, we first derive closed-form expressions for the outage probability and the ergodic rate of paired NOMA Rxs. For obtaining more insights, we investigate the diversity order and the high signal-to-noise (SNR) slope of NOMA enhanced U2X frameworks. We also derive the spectrum efficiency in both NOMA and orthogonal multiple access (OMA) enhanced U2X frameworks. Our analytical results demonstrate that the diversity order and the high SNR slope of the proposed framework are $m$ and one, respectively. Numerical results are provided to confirm that: i) the proposed NOMA enhanced U2X frameworks have superior outage performance and spectrum efficiency compared with the OMA-enhanced U2X frameworks; and ii) for the case of fixed LoS probability, the outage performance of paired NOMA Rxs mainly depends on users with poor channel conditions.
Beamforming Design in Multiple-Input-Multiple-Output Symbiotic Radio Backscatter Systems
Venue: arXiv cs.IT 2019
Year: 2019

Symbiotic radio (SR) backscatter systems are possible techniques for the future low-power wireless communications for Internet of Things devices. In this paper, we propose a multiple-input-multiple-output (MIMO) SR backscatter system, where the secondary multi-antenna transmission from the backscatter device (BD) to the receiver is riding on the primary multi-antenna transmission from the transmitter to the receiver. We investigate the beamforming design optimization problem which maximizes the achievable rate of secondary transmission under the achievable rate constraint of primary transmission. In the MIMO SR backscatter system, each antenna of the SR BD reflects its received ambient radio frequency signals from all the transmitting antennas of the transmitter, which causes the globally optimal solution is difficult to obtain. In this paper, we propose a method to obtain the achievable rate upper bound. Furthermore, considering both primary and secondary transmissions, we propose an exact penalty method based locally optimal solution. Simulation results illustrate that our proposed exact penalty method based locally optimal solution performs close to the upper bound.
Concolic Testing Heap-Manipulating Programs
Venue: arXiv cs.PL 2019
Year: 2019

Concolic testing is a test generation technique which works effectively by integrating random testing generation and symbolic execution. Existing concolic testing engines focus on numeric programs. Heap-manipulating programs make extensive use of complex heap objects like trees and lists. Testing such programs is challenging due to multiple reasons. Firstly, test inputs for such program are required to satisfy non-trivial constraints which must be specified precisely. Secondly, precisely encoding and solving path conditions in such programs are challenging and often expensive. In this work, we propose the first concolic testing engine called CSF for heap-manipulating programs based on separation logic. CSF effectively combines specification-based testing and concolic execution for test input generation. It is evaluated on a set of challenging heap-manipulating programs. The results show that CSF generates valid test inputs with high coverage efficiently. Furthermore, we show that CSF can be potentially used in combination with precondition inference tools to reduce the user effort.
Augmenting Type Signatures for Program Synthesis
Venue: arXiv cs.PL 2019
Year: 2019

Effective program synthesis requires a way to minimise the number of candidate programs being searched. A type signature, for example, places some small restrictions on the structure of potential candidates. We introduce and motivate a distilled program synthesis problem where a type signature is the only machine-readable information available, but does not sufficiently minimise the search space. To address this, we develop a system of property relations that can be used to flexibly encode and query information that was not previously available to the synthesiser. Our experience using these tools has been positive: by encoding simple properties and by using a minimal set of synthesis primitives, we have been able to synthesise complex programs in novel contexts
Saliency Maps Generation for Automatic Text Summarization
Venue: arXiv cs.LG 2019
Year: 2019

Saliency map generation techniques are at the forefront of explainable AI literature for a broad range of machine learning applications. Our goal is to question the limits of these approaches on more complex tasks. In this paper we apply Layer-Wise Relevance Propagation (LRP) to a sequence-to-sequence attention model trained on a text summarization dataset. We obtain unexpected saliency maps and discuss the rightfulness of these "explanations". We argue that we need a quantitative way of testing the counterfactual case to judge the truthfulness of the saliency maps. We suggest a protocol to check the validity of the importance attributed to the input and show that the saliency maps obtained sometimes capture the real use of the input features by the network, and sometimes do not. We use this example to discuss how careful we need to be when accepting them as explanation.
Mercem: Method Name Recommendation Based on Call Graph Embedding
Venue: arXiv cs.SE 2019
Year: 2019

Comprehensibility of source code is strongly affected by identifier names, therefore software developers need to give good (e.g. meaningful but short) names to identifiers. On the other hand, giving a good name is sometimes a difficult and time-consuming task even for experienced developers. To support naming identifiers, several techniques for recommending identifier name candidates have been proposed. These techniques, however, still have challenges on the goodness of suggested candidates and limitations on applicable situations. This paper proposes a new approach to recommending method names by applying graph embedding techniques to the method call graph. The evaluation experiment confirms that the proposed technique can suggest more appropriate method name candidates in difficult situations than the state of the art approach.
Automated Word Stress Detection in Russian
Venue: arXiv cs.CL 2019
Year: 2019

In this study we address the problem of automated word stress detection in Russian using character level models and no part-speech-taggers. We use a simple bidirectional RNN with LSTM nodes and achieve the accuracy of 90% or higher. We experiment with two training datasets and show that using the data from an annotated corpus is much more efficient than using a dictionary, since it allows us to take into account word frequencies and the morphological context of the word.
Elastic properties of isotropic discrete systems: Connections between geometric structure and Poisson's ratio
Venue: arXiv cs.CE 2019
Year: 2019

The use of discrete material representation in numerical models is advantageous due to the straightforward way it takes into account material heterogeneity and randomness, and the discrete and orientated nature of cracks. Unfortunately, it also restricts the macroscopic Poisson's ratio and therefore narrows its applicability. The paper studies the Poisson's ratio of a discrete model analytically. It derives theoretical limits for cases where the geometry of the model is completely arbitrary, but isotropic in the statistical sense. It is shown that the widest limits are obtained for models where normal directions of contacts between discrete units are parallel with the vectors connecting these units. Any deviation from parallelism causes the limits to shrink. A comparison of the derived equations to the results of the actual numerical model is presented. It shows relatively large deviations from the theory because the fundamental assumptions behind the theoretical derivations are largely violated in systems with complex geometry. The real shrinking of the Poisson's ratio limit is less severe compared to that which is theoretically derived.
Signal Conditioning for Learning in the Wild
Venue: arXiv cs.NE 2019
Year: 2019

The mammalian olfactory system learns rapidly from very few examples, presented in unpredictable online sequences, and then recognizes these learned odors under conditions of substantial interference without exhibiting catastrophic forgetting. We have developed a brain-mimetic algorithm that replicates these properties, provided that sensory inputs adhere to a common statistical structure. However, in natural, unregulated environments, this constraint cannot be assured. We here present a series of signal conditioning steps, inspired by the mammalian olfactory system, that transform diverse sensory inputs into a regularized statistical structure to which the learning network can be tuned. This pre-processing enables a single instantiated network to be applied to widely diverse classification tasks and datasets - here including gas sensor data, remote sensing from spectral characteristics, and multi-label hierarchical identification of wild species - without adjusting network hyperparameters.
A General Decoupled Learning Framework for Parameterized Image Operators
Venue: arXiv cs.CV 2019
Year: 2019

Many different deep networks have been used to approximate, accelerate or improve traditional image operators. Among these traditional operators, many contain parameters which need to be tweaked to obtain the satisfactory results, which we refer to as parameterized image operators. However, most existing deep networks trained for these operators are only designed for one specific parameter configuration, which does not meet the needs of real scenarios that usually require flexible parameters settings. To overcome this limitation, we propose a new decoupled learning algorithm to learn from the operator parameters to dynamically adjust the weights of a deep network for image operators, denoted as the base network. The learned algorithm is formed as another network, namely the weight learning network, which can be end-to-end jointly trained with the base network. Experiments demonstrate that the proposed framework can be successfully applied to many traditional parameterized image operators. To accelerate the parameter tuning for practical scenarios, the proposed framework can be further extended to dynamically change the weights of only one single layer of the base network while sharing most computation cost. We demonstrate that this cheap parameter-tuning extension of the proposed decoupled learning framework even outperforms the state-of-the-art alternative approaches.
An Exploratory Study of Live-Streamed Programming
Venue: arXiv cs.SE 2019
Year: 2019

In live-streamed programming, developers broadcast their development work on open source projects using streaming media such as YouTube or Twitch. Sessions are first announced by a developer acting as the streamer, inviting other developers to join and interact as watchers using chat. To better understand the characteristics, motivations, and challenges in live-streamed programming, we analyzed 20 hours of live-streamed programming videos and surveyed 7 streamers about their experiences. The results reveal that live-streamed programming shares some of the characteristics and benefits of pair programming, but differs in the nature of the relationship between the streamer and watchers. We also found that streamers are motivated by knowledge sharing, socializing, and building an online identity, but face challenges with tool limitations and maintaining engagement with watchers. We discuss the implications of these findings, identify limitations with current tools, and propose design recommendations for new forms of tools to better supporting live-streamed programming.
Efficient average-case population recovery in the presence of insertions and deletions
Venue: arXiv cs.DS 2019
Year: 2019

Several recent works have considered the \emph{trace reconstruction problem}, in which an unknown source string $x\in\{0,1\}^n$ is transmitted through a probabilistic channel which may randomly delete coordinates or insert random bits, resulting in a \emph{trace} of $x$. The goal is to reconstruct the original string~$x$ from independent traces of $x$. While the best algorithms known for worst-case strings use $\exp(O(n^{1/3}))$ traces \cite{DOS17,NazarovPeres17}, highly efficient algorithms are known \cite{PZ17,HPP18} for the \emph{average-case} version, in which $x$ is uniformly random. We consider a generalization of this average-case trace reconstruction problem, which we call \emph{average-case population recovery in the presence of insertions and deletions}. In this problem, there is an unknown distribution $\cal{D}$ over $s$ unknown source strings $x^1,\dots,x^s \in \{0,1\}^n$, and each sample is independently generated by drawing some $x^i$ from $\cal{D}$ and returning an independent trace of $x^i$. Building on \cite{PZ17} and \cite{HPP18}, we give an efficient algorithm for this problem. For any support size $s \leq \smash{\exp(Θ(n^{1/3}))}$, for a $1-o(1)$ fraction of all $s$-element support sets $\{x^1,\dots,x^s\} \subset \{0,1\}^n$, for every distribution $\cal{D}$ supported on $\{x^1,\dots,x^s\}$, our algorithm efficiently recovers ${\cal D}$ up to total variation distance $ε$ with high probability, given access to independent traces of independent draws from $\cal{D}$. The algorithm runs in time poly$(n,s,1/ε)$ and its sample complexity is poly$(s,1/ε,\exp(\log^{1/3}n)).$ This polynomial dependence on the support size $s$ is in sharp contrast with the \emph{worst-case} version (when $x^1,\dots,x^s$ may be any strings in $\{0,1\}^n$), in which the sample complexity of the most efficient known algorithm \cite{BCFSS19} is doubly exponential in $s$.
Resolvability of Hamming Graphs
Venue: arXiv cs.DM 2019
Year: 2019

A subset of vertices in a graph is called resolving when the geodesic distances to those vertices uniquely distinguish every vertex in the graph. Here, we characterize the resolvability of Hamming graphs in terms of a constrained linear system and deduce a novel but straightforward characterization of resolvability for hypercubes. We propose an integer linear programming method to assess resolvability rapidly, and provide a more costly but definite method based on Gröbner bases to determine whether or not a set of vertices resolves an arbitrary Hamming graph. As proof of concept, we identify a resolving set of size 77 in the metric space of all octapeptides (i.e., proteins composed of eight amino acids) with respect to the Hamming distance; in particular, any octamer may be readily represented as a 77-dimensional real-vector. Representing k-mers as low-dimensional numerical vectors may enable new applications of machine learning algorithms to symbolic sequences.