OpenRaiser/Intern-Atlas huggingface dataset:
Non-Orthogonal Contention-Based Access for URLLC Devices with Frequency Diversity
Venue: arXiv cs.IT 2019
Year: 2019

We study coded multichannel random access schemes for ultra-reliable low-latency uplink transmissions. We concentrate on non-orthogonal access in the frequency domain, where users transmit over multiple orthogonal subchannels and inter-user collisions limit the available diversity. Two different models for contention-based random access over Rayleigh fading resources are investigated. First, a collision model is considered, in which the packet is replicated onto $K$ available resources, $K' \leq K$ of which are received without collision, and treated as diversity branches by a maximum-ratio combining (MRC) receiver. The resulting diversity degree $K'$ depends on the arrival process and coding strategy. In the second model, the slots subject to collisions are also used for MRC, such that the number of diversity branches $K$ is constant, but the resulting combined signal is affected by multiple access interference. In both models, the performance of random and deterministic repetition coding is compared. The results show that the deterministic coding approach can lead to a significantly superior performance when the arrival rate of the intermittent URLLC transmissions is low.
On the Separability of Parallel MISO Broadcast Channels Under Partial CSIT: A Degrees of Freedom Region Perspective
Venue: arXiv cs.IT 2019
Year: 2019

We study the $K$-user, $M$-subchannel parallel multiple-input-single-output (MISO) broadcast channel (BC) under arbitrary levels of partial channel state information at the transmitter (CSIT). We show that the parallel subchannels constituting this setting are separable from a degrees-of-freedom (DoF) region perspective if and only if the partial CSIT pattern is totally ordered. This total order condition corresponds to users abiding by the same order, with respect to their CSIT quality levels, in each of the parallel subchannels. For instance, let $α_{k}^{[l]}$ and $α_{j}^{[l]}$ be the CSIT quality parameters for users $k$ and $j$ over subchannel $l$. Under total order, having $α_{k}^{[l]} \geq α_{j}^{[l]}$ implies that $α_{k}^{[m]} \geq α_{j}^{[m]}$ holds for every subchannel $m$. In this case, the entire DoF region is achievable using simple separate coding, where a single-subchannel-type transmission scheme is employed in each subchannel. To show this separability result, we first derive an outer bound for the DoF region by extending the aligned image sets approach of Davoodi and Jafar to the considered setting. We then show that this outer bound coincides with the inner bound achieved through separate coding, given by the Minkowski sum of $M$ single-subchannel DoF regions, under the total order condition, hence settling the if part of the main theorem. To prove the only if part of the theorem, we identify a set of DoF tuples achievable through joint coding across subchannels, yet not achievable through separate coding whenever the total order condition is violated. Moreover, we also highlight the implications of our main result on the design of CSIT feedback schemes for multi-carrier multi-antenna wireless networks.
In Defense of Synthetic Data
Venue: arXiv cs.DB 2019
Year: 2019

Synthetic datasets have long been thought of as second-rate, to be used only when "real" data collected directly from the real world is unavailable. But this perspective assumes that raw data is clean, unbiased, and trustworthy, which it rarely is. Moreover, the benefits of synthetic data for privacy and for bias correction are becoming increasingly important in any domain that works with people. Curated synthetic datasets - synthetic data derived from minimal perturbations of real data - enable early stage product development and collaboration, protect privacy, afford reproducibility, increase dataset diversity in research, and protect disadvantaged groups from problematic inferences on the original data that reflects systematic discrimination. Rather than representing a departure from the true state of the world, in this paper we argue that properly generated synthetic data is a step towards responsible and equitable research and development of machine learning systems.
Agent based decision making for Integrated Air Defense system
Venue: arXiv cs.MA 2019
Year: 2019

This paper presents algorithms of decision making agents for an integrated air defense (IAD) system. The advantage of using agent based over conventional decision making system is its ability to automatically detect and track targets and if required allocate weapons to neutralize threat in an integrated mode. Such approach is particularly useful for futuristic network centric warfare. Two agents are presented here that perform the basic decisions making tasks of command and control (C2) like detection and action against jamming, threat assessment and weapons allocation, etc. The belief-desire-intension (BDI) architectures stay behind the building blocks of these agents. These agents decide their actions by meta level plan reasoning process. The proposed agent based IAD system runs without any manual inputs, and represents a state of art model for C2 autonomy.
Improved Metric Distortion for Deterministic Social Choice Rules
Venue: arXiv cs.GT 2019
Year: 2019

In this paper, we study the metric distortion of deterministic social choice rules that choose a winning candidate from a set of candidates based on voter preferences. Voters and candidates are located in an underlying metric space. A voter has cost equal to her distance to the winning candidate. Ordinal social choice rules only have access to the ordinal preferences of the voters that are assumed to be consistent with the metric distances. Our goal is to design an ordinal social choice rule with minimum distortion, which is the worst-case ratio, over all consistent metrics, between the social cost of the rule and that of the optimal omniscient rule with knowledge of the underlying metric space. The distortion of the best deterministic social choice rule was known to be between $3$ and $5$. It had been conjectured that any rule that only looks at the weighted tournament graph on the candidates cannot have distortion better than $5$. In our paper, we disprove it by presenting a weighted tournament rule with distortion of $4.236$. We design this rule by generalizing the classic notion of uncovered sets, and further show that this class of rules cannot have distortion better than $4.236$. We then propose a new voting rule, via an alternative generalization of uncovered sets. We show that if a candidate satisfying the criterion of this voting rule exists, then choosing such a candidate yields a distortion bound of $3$, matching the lower bound. We present a combinatorial conjecture that implies distortion of $3$, and verify it for small numbers of candidates and voters by computer experiments. Using our framework, we also show that selecting any candidate guarantees distortion of at most $3$ when the weighted tournament graph is cyclically symmetric.
Learning Functional Dependencies with Sparse Regression
Venue: arXiv cs.DB 2019
Year: 2019

We study the problem of discovering functional dependencies (FD) from a noisy dataset. We focus on FDs that correspond to statistical dependencies in a dataset and draw connections between FD discovery and structure learning in probabilistic graphical models. We show that discovering FDs from a noisy dataset is equivalent to learning the structure of a graphical model over binary random variables, where each random variable corresponds to a functional of the dataset attributes. We build upon this observation to introduce AutoFD a conceptually simple framework in which learning functional dependencies corresponds to solving a sparse regression problem. We show that our methods can recover true functional dependencies across a diverse array of real-world and synthetic datasets, even in the presence of noisy or missing data. We find that AutoFD scales to large data instances with millions of tuples and hundreds of attributes while it yields an average F1 improvement of 2 times against state-of-the-art FD discovery methods.
Clustering-aware Graph Construction: A Joint Learning Perspective
Venue: arXiv cs.LG 2019
Year: 2019

Graph-based clustering methods have demonstrated the effectiveness in various applications. Generally, existing graph-based clustering methods first construct a graph to represent the input data and then partition it to generate the clustering result. However, such a stepwise manner may make the constructed graph not fit the requirements for the subsequent decomposition, leading to compromised clustering accuracy. To this end, we propose a joint learning framework, which is able to learn the graph and the clustering result simultaneously, such that the resulting graph is tailored to the clustering task. The proposed model is formulated as a well-defined nonnegative and off-diagonal constrained optimization problem, which is further efficiently solved with convergence theoretically guaranteed. The advantage of the proposed model is demonstrated by comparing with 19 state-of-the-art clustering methods on 10 datasets with 4 clustering metrics.
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Venue: arXiv cs.DS 2019
Year: 2019

A sparsifier of a graph $G$ (Benczúr and Karger; Spielman and Teng) is a sparse weighted subgraph $\tilde G$ that approximately retains the cut structure of $G$. For general graphs, non-trivial sparsification is possible only by using weighted graphs in which different edges have different weights. Even for graphs that admit unweighted sparsifiers, there are no known polynomial time algorithms that find such unweighted sparsifiers. We study a weaker notion of sparsification suggested by Oveis Gharan, in which the number of edges in each cut $(S,\bar S)$ is not approximated within a multiplicative factor $(1+ε)$, but is, instead, approximated up to an additive term bounded by $ε$ times $d\cdot |S| + \text{vol}(S)$, where $d$ is the average degree, and $\text{vol}(S)$ is the sum of the degrees of the vertices in $S$. We provide a probabilistic polynomial time construction of such sparsifiers for every graph, and our sparsifiers have a near-optimal number of edges $O(ε^{-2} n {\rm polylog}(1/ε))$. We also provide a deterministic polynomial time construction that constructs sparsifiers with a weaker property having the optimal number of edges $O(ε^{-2} n)$. Our constructions also satisfy a spectral version of the ``additive sparsification'' property. Our construction of ``additive sparsifiers'' with $O_ε(n)$ edges also works for hypergraphs, and provides the first non-trivial notion of sparsification for hypergraphs achievable with $O(n)$ hyperedges when $ε$ and the rank $r$ of the hyperedges are constant. Finally, we provide a new construction of spectral hypergraph sparsifiers, according to the standard definition, with ${\rm poly}(ε^{-1},r)\cdot n\log n$ hyperedges, improving over the previous spectral construction (Soma and Yoshida) that used $\tilde O(n^3)$ hyperedges even for constant $r$ and $ε$.
A Joint Convolutional Neural Networks and Context Transfer for Street Scenes Labeling
Venue: arXiv cs.CV 2019
Year: 2019

Street scene understanding is an essential task for autonomous driving. One important step towards this direction is scene labeling, which annotates each pixel in the images with a correct class label. Although many approaches have been developed, there are still some weak points. Firstly, many methods are based on the hand-crafted features whose image representation ability is limited. Secondly, they can not label foreground objects accurately due to the dataset bias. Thirdly, in the refinement stage, the traditional Markov Random Filed (MRF) inference is prone to over smoothness. For improving the above problems, this paper proposes a joint method of priori convolutional neural networks at superpixel level (called as ``priori s-CNNs'') and soft restricted context transfer. Our contributions are threefold: (1) A priori s-CNNs model that learns priori location information at superpixel level is proposed to describe various objects discriminatingly; (2) A hierarchical data augmentation method is presented to alleviate dataset bias in the priori s-CNNs training stage, which improves foreground objects labeling significantly; (3) A soft restricted MRF energy function is defined to improve the priori s-CNNs model's labeling performance and reduce the over smoothness at the same time. The proposed approach is verified on CamVid dataset (11 classes) and SIFT Flow Street dataset (16 classes) and achieves competitive performance.
Stabilization of Bipedal Robot Motion based on Total Momentum
Venue: arXiv cs.RO 2019
Year: 2019

Bipedal robots adapt to the environment of the modern society due to the similarity of movement to humans, and therefore they are a good partner for humans. However, maintaining the stability of these robots during walking/running motion is a challenging issue that, despite the development of new technologies and the advancement of knowledge, does not yet have a satisfactory solution. In most of the proposed methods by researchers, to maintain the stability of walking bipedal robots, it has been tried to ensure the momentary stability of motion by limiting the motion to multiple constraints. Although these methods have good performance in sustaining stability, they leave the robot away from the natural movement of humans, with low efficiency and high energy consumption. Hence, many researchers have turned to the walking techniques that follow a certain motion limit cycle, in which we can consider the overall stability rather than momentary. In this paper, a method is proposed to maintain the stability of the limit cycle against disturbance. For this purpose, the dynamical model of the biped robot is extracted in the space of total momentum variables and, according to the desired step length and speed, the motion limit cycle is designed. Subsequently, a motion stabilizer is proposed based on the idea of length shift, which is a natural human strategy for sustaining the balance in case of impact. The simulations show that this technique has a good performance in maintaining the stability of motion and has similar responses to human response.
A Holomorphic Embedding Based Continuation Method for Identifying Multiple Power Flow Solutions
Venue: arXiv cs.SY 2019
Year: 2019

In this paper, we propose an efficient continuation method for locating multiple power flow solutions. We adopt the holomorphic embedding technique to represent solution curves as holomorphic functions in the complex plane. The holomorphicity, which provides global information of the curve at any regular point, enables large step sizes in the path-following procedure such that non-singular curve segments can be traversed with very few steps. When approaching singular points, we switch to the traditional predictor-corrector routine to pass through them and switch back afterward to the holomorphic embedding routine. We also propose a warm starter when switching to the predictor-corrector routine, i.e. a large initial step size based on the poles of the Padé approximation of the derived holomorphic function, since these poles reveal the locations of singularities on the curve. Numerical analysis and experiments on many standard IEEE test cases are presented, along with the comparison to the full predictor-corrector routine, confirming the efficiency of the method.
On the Controllability of Clustered Scale-Free Networks
Venue: arXiv cs.SY 2019
Year: 2019

In this paper, we compare the number of unmatched nodes and the size of dilations in two main random network models, the Scale-Free and Clustered Scale-Free networks. The number of unmatched nodes determines the necessary number of control inputs and is known to be a measure for network controllability, while the size of dilation is a measure of controllability recovery in case of control input failure. Our results show that clustered version of Scale-Free networks require fewer control inputs for controllability. Further, the average size of dilations is smaller in clustered Scale-Free networks, implying that potentially fewer options for controllability recovery are available.
Deep Video Inpainting
Venue: arXiv cs.CV 2019
Year: 2019

Video inpainting aims to fill spatio-temporal holes with plausible content in a video. Despite tremendous progress of deep neural networks for image inpainting, it is challenging to extend these methods to the video domain due to the additional time dimension. In this work, we propose a novel deep network architecture for fast video inpainting. Built upon an image-based encoder-decoder model, our framework is designed to collect and refine information from neighbor frames and synthesize still-unknown regions. At the same time, the output is enforced to be temporally consistent by a recurrent feedback and a temporal memory module. Compared with the state-of-the-art image inpainting algorithm, our method produces videos that are much more semantically correct and temporally smooth. In contrast to the prior video completion method which relies on time-consuming optimization, our method runs in near real-time while generating competitive video results. Finally, we applied our framework to video retargeting task, and obtain visually pleasing results.
SIF: A Framework for Solidity Code Instrumentation and Analysis
Venue: arXiv cs.SE 2019
Year: 2019

Solidity is an object-oriented and high-level language for writing smart contracts that are used to execute, verify and enforce credible transactions on permissionless blockchains. In the last few years, analysis of smart contracts has raised considerable interest and numerous techniques have been proposed to check the presence of vulnerabilities in them. Current techniques lack traceability in source code and have widely differing work flows. There is no single unifying framework for analysis, instrumentation, optimisation and code generation of Solidity contracts. In this paper, we present SIF, a comprehensive framework for Solidity contract analysis, query, instrumentation, and code generation. SIF provides support for Solidity contract developers and testers to build source level techniques for analysis, understanding, diagnostics, optimisations and code generation. We show feasibility and applicability of the framework by building practical tools on top of it and running them on 1838 real smart contracts deployed on the Ethereum network.
A Polynomial Time Algorithm for Fair Resource Allocation in Resource Exchange
Venue: arXiv cs.GT 2019
Year: 2019

The rapid growth of wireless and mobile Internet has led to wide applications of exchanging resources over network, in which how to fairly allocate resources has become a critical challenge. To motivate sharing, a BD Mechanism is proposed for resource allocation, which is based on a combinatorial structure called bottleneck decomposition. The mechanism has been shown with properties of fairness, economic efficiency [17], and truthfulness against two kinds of strategic behaviors [2,3]. Unfortunately, the crux on how to compute a bottleneck decomposition of any graph is remain untouched. In this paper, we focus on the computation of bottleneck decomposition to fill the blanks and prove that the bottleneck decomposition of a network $G = (V, E; w_v)$ can be computed in $O(n^6 log(nU))$, where $n = |V|$ and $U = max_{v\in V} w_v$. Based on the bottleneck decomposition, a fair allocation in resource exchange system can be obtained in polynomial time. In addition, our work completes the computation of a market equilibrium and its relationship to two concepts of fairness in resource exchange.
Multivariate Time Series Classification using Dilated Convolutional Neural Network
Venue: arXiv cs.LG 2019
Year: 2019

Multivariate time series classification is a high value and well-known problem in machine learning community. Feature extraction is a main step in classification tasks. Traditional approaches employ hand-crafted features for classification while convolutional neural networks (CNN) are able to extract features automatically. In this paper, we use dilated convolutional neural network for multivariate time series classification. To deploy dilated CNN, a multivariate time series is transformed into an image-like style and stacks of dilated and strided convolutions are applied to extract in and between features of variates in time series simultaneously. We evaluate our model on two human activity recognition time series, finding that the automatic features extracted for the time series can be as effective as hand-crafted features.
BVS Corpus: A Multilingual Parallel Corpus of Biomedical Scientific Texts
Venue: arXiv cs.CL 2019
Year: 2019

The BVS database (Health Virtual Library) is a centralized source of biomedical information for Latin America and Carib, created in 1998 and coordinated by BIREME (Biblioteca Regional de Medicina) in agreement with the Pan American Health Organization (OPAS). Abstracts are available in English, Spanish, and Portuguese, with a subset in more than one language, thus being a possible source of parallel corpora. In this article, we present the development of parallel corpora from BVS in three languages: English, Portuguese, and Spanish. Sentences were automatically aligned using the Hunalign algorithm for EN/ES and EN/PT language pairs, and for a subset of trilingual articles also. We demonstrate the capabilities of our corpus by training a Neural Machine Translation (OpenNMT) system for each language pair, which outperformed related works on scientific biomedical articles. Sentence alignment was also manually evaluated, presenting an average 96% of correctly aligned sentences across all languages. Our parallel corpus is freely available, with complementary information regarding article metadata.
Faster polytope rounding, sampling, and volume computation via a sublinear "Ball Walk"
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem of "isotropically rounding" a polytope $K\subset\mathbb{R}^n$, that is, computing a linear transformation which makes the uniform distribution on the polytope have roughly identity covariance matrix. We assume $K$ is defined by $m$ linear inequalities, with guarantee that $rB\subset K\subset RB$, where $B$ is the unit ball. We introduce a new variant of the ball walk Markov chain and show that, roughly, the expected number of arithmetic operations per-step of this Markov chain is $O(m)$ that is sublinear in the input size $mn$--the per-step time of all prior Markov chains. Subsequently, we give a rounding algorithm that succeeds with probability $1-\varepsilon$ in $\tilde{O}(mn^{4.5}\mbox{polylog}(\frac{1}{\varepsilon},\frac{R}{r}))$ arithmetic operations. This gives a factor of $\sqrt{n}$ improvement on the previous bound of $\tilde{O}(mn^5\mbox{polylog}(\frac{1}{\varepsilon},\frac{R}{r}))$ for rounding, which uses the hit-and-run algorithm. Since the rounding preprocessing step is in many cases the bottleneck in improving sampling or volume computation, our results imply these tasks can also be achieved in roughly $\tilde{O}(mn^{4.5}\mbox{polylog}(\frac{1}{\varepsilon},\frac{R}{r})+mn^4δ^{-2})$ operations for computing the volume of $K$ up to a factor $1+δ$ and $\tilde{O}(mn^{4.5}\mbox{polylog}(\frac{1}{\varepsilon},\frac{R}{r})))$ for uniformly sampling on $K$ with TV error $\varepsilon$. This improves on the previous bounds of $\tilde{O}(mn^5\mbox{polylog}(\frac{1}{\varepsilon},\frac{R}{r})+mn^4δ^{-2})$ for volume computation when roughly $m\geq n^{2.5}$, and $\tilde{O}(mn^5\mbox{polylog}(\frac{1}{\varepsilon},\frac{R}{r}))$ for sampling when roughly $m\geq n^{1.5}$. We achieve this improvement by a novel method of computing polytope membership, where one avoids checking inequalities estimated to have a very low probability of being violated.