OpenRaiser/Intern-Atlas huggingface dataset:
The KIT Motion-Language Dataset
Venue: arXiv cs.RO 2018
Year: 2018

Linking human motion and natural language is of great interest for the generation of semantic representations of human activities as well as for the generation of robot activities based on natural language input. However, while there have been years of research in this area, no standardized and openly available dataset exists to support the development and evaluation of such systems. We therefore propose the KIT Motion-Language Dataset, which is large, open, and extensible. We aggregate data from multiple motion capture databases and include them in our dataset using a unified representation that is independent of the capture system or marker set, making it easy to work with the data regardless of its origin. To obtain motion annotations in natural language, we apply a crowd-sourcing approach and a web-based tool that was specifically build for this purpose, the Motion Annotation Tool. We thoroughly document the annotation process itself and discuss gamification methods that we used to keep annotators motivated. We further propose a novel method, perplexity-based selection, which systematically selects motions for further annotation that are either under-represented in our dataset or that have erroneous annotations. We show that our method mitigates the two aforementioned problems and ensures a systematic annotation process. We provide an in-depth analysis of the structure and contents of our resulting dataset, which, as of October 10, 2016, contains 3911 motions with a total duration of 11.23 hours and 6278 annotations in natural language that contain 52,903 words. We believe this makes our dataset an excellent choice that enables more transparent and comparable research in this important area.
Mechanism Design for Value Maximizers
Venue: arXiv cs.GT 2018
Year: 2018

In many settings, money is a tool of exchange with minimal inherent utility --- agents will spend it in a way that maximizes the value of goods received subject to reasonable constraints, giving only second-order consideration to the trade-off between value and price. While this perspective is commonly captured in consumer choice theory, market equilibrium theory, and other fields, it is markedly absent from the mechanism design literature --- agents strategizing in a mechanism with money are almost always assumed to incorporate money as an objective through quasilinear valuations. We study a simple model of value maximizers that captures online advertisers and other agents who may view money solely as a constraint, and study general questions of mechanism design for such agents. We show that the feasible and optimal points faced by a mechanism designer change dramatically from the quasilinear realm and lay a foundation for a broader study of value maximization in mechanism design. Along the way, we offer new insight into the generalized second price (GSP) auction commonly used in Internet advertising. Through the lens of value maximization, GSP metamorphosizes into a truthful auction, sound in its principles and elegant in its simplicity.
The recursion hierarchy for PCF is strict
Venue: arXiv cs.LO 2018
Year: 2018

We consider the sublanguages of Plotkin's PCF obtained by imposing some bound k on the levels of types for which fixed point operators are admitted. We show that these languages form a strict hierarchy, in the sense that a fixed point operator for a type of level k can never be defined (up to observational equivalence) using fixed point operators for lower types. This answers a question posed by Berger. Our proof makes substantial use of the theory of nested sequential procedures (also called PCF Böhm trees) as expounded in the recent book of Longley and Normann.
Distributed Algorithms for Robust Convex Optimization via the Scenario Approach
Venue: arXiv cs.DC 2018
Year: 2018

This paper proposes distributed algorithms to solve robust convex optimization (RCO) when the constraints are affected by nonlinear uncertainty. We adopt a scenario approach by randomly sampling the uncertainty set. To facilitate the computational task, instead of using a single centralized processor to obtain a "global solution" of the scenario problem (SP), we resort to {\it multiple interconnected processors} that are distributed among different nodes of a network to simultaneously solve the SP. Then, we propose a primal-dual sub-gradient algorithm and a random projection algorithm to distributedly solve the SP over undirected and directed graphs, respectively. Both algorithms are given in an explicit recursive form with simple iterations, which are especially suited for processors with limited computational capability. We show that, if the underlying graph is strongly connected, each node asymptotically computes a common optimal solution to the SP with a convergence rate $O(1/(\sum_{t=1}^kζ^t))$ where $\{ζ^t\}$ is a sequence of appropriately decreasing stepsizes. That is, the RCO is effectively solved in a distributed way. The relations with the existing literature on robust convex programs are thoroughly discussed and an example of robust system identification is included to validate the effectiveness of our distributed algorithms.
Inpainting of long audio segments with similarity graphs
Venue: arXiv cs.SD 2018
Year: 2018

We present a novel method for the compensation of long duration data loss in audio signals, in particular music. The concealment of such signal defects is based on a graph that encodes signal structure in terms of time-persistent spectral similarity. A suitable candidate segment for the substitution of the lost content is proposed by an intuitive optimization scheme and smoothly inserted into the gap, i.e. the lost or distorted signal region. Extensive listening tests show that the proposed algorithm provides highly promising results when applied to a variety of real-world music signals.
Profit-aware Online Vehicle-to-Grid Decentralized Scheduling under Multiple Charging Stations
Venue: arXiv cs.SY 2018
Year: 2018

Fluctuations in electricity tariffs induced by the sporadic nature of demand loads on power grids has initiated immense efforts to find optimal scheduling solutions for charging and discharging plug-in electric vehicles (PEVs) subject to different objective sets. In this paper, we consider vehicle-to-grid (V2G) scheduling at a geographically large scale in which PEVs have the flexibility of charging/discharging at multiple smart stations coordinated by individual aggregators. We first formulate the objective of maximizing the overall profit of both, demand and supply entities, by defining a weighting parameter. We then propose an online decentralized greedy algorithm for the formulated mixed integer non-linear programming (MINLP) problem, which incorporates efficient heuristics to practically guide each incoming vehicle to the most appropriate charging station (CS). The better performance of the presented algorithm compared to an alternative allocation strategy is demonstrated through simulations in terms of the overall achievable profit and flatness of the final electricity load. Moreover, the results of simulations reveal the existence of optimal number of deployed stations at which the overall profit can be maximized.
Strong Secrecy on a Class of Degraded Broadcast Channels Using Polar Codes
Venue: arXiv cs.IT 2018
Year: 2018

Different polar coding schemes are proposed for the memoryless degraded broadcast channel under different reliability and secrecy requirements: layered decoding and/or layered secrecy. In this setting, the transmitter wishes to send multiple messages to a set of legitimate receivers keeping them masked from a set of eavesdroppers. The layered decoding structure requires receivers with better channel quality to reliably decode more messages, while the layered secrecy structure requires eavesdroppers with worse channel quality to be kept ignorant of more messages. The implementation of the proposed polar coding schemes is discussed and their performance is evaluated by simulations for the symmetric degraded broadcast channel.
On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Venue: arXiv cs.CG 2018
Year: 2018

Every graph $G$ can be represented by a collection of equi-radii spheres in a $d$-dimensional metric $Δ$ such that there is an edge $uv$ in $G$ if and only if the spheres corresponding to $u$ and $v$ intersect. The smallest integer $d$ such that $G$ can be represented by a collection of spheres (all of the same radius) in $Δ$ is called the sphericity of $G$, and if the collection of spheres are non-overlapping, then the value $d$ is called the contact-dimension of $G$. In this paper, we study the sphericity and contact dimension of the complete bipartite graph $K_{n,n}$ in various $L^p$-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.
Generalized Lexicographic Products and the Index Coding Capacity
Venue: arXiv cs.IT 2018
Year: 2018

The index coding problem studies the fundamental limit on broadcasting multiple messages to their respective receivers with different sets of side information that are represented by a directed graph. The generalized lexicographic product structure in the side information graph is introduced as a natural condition under which the corresponding index coding problem can be decomposed into multiple interacting subproblems. The capacity region is characterized in terms of the subproblem capacity regions combined in the same product structure. The proof is based on dual uses of random coding---one for a new multiletter characterization of the capacity region of a general index coding problem via joint typicality decoding and the other for a construction of a new multiletter code of matching rates from a single-letter code via joint typicality encoding. Several special cases are discussed that recover and strengthen known structural properties of the index coding capacity region.
Accurate and Efficient Measurements of IP level Performance to Drive Interface Selection in Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2018
Year: 2018

Optimal interface selection is a key mobility management issue in heterogeneous wireless networks. Measuring the physical or link level performance on a given wireless access networks does not provide a reliable indication of the IP connectivity, delay and loss on the (bidirectional) paths from the Mobile Host to the node that is handling the mobility, over different heterogeneous networks. In this paper, we propose, implement and analyze mechanisms for connectivity check and performance (network delay and packet loss) monitoring over IP access networks. We evaluate the accuracy and timeliness of the performance estimates and provide guidelines for tuning up the parameters. From the implementation perspective, we show that using application level measurements is highly CPU intensive, while a kernel based implementation has comparably a very low CPU usage. The Linux kernel implementation results in an efficient use of batteries in Mobile Hosts and intermediate Mobility Management Nodes can scale up to monitoring thousands of flows. The proposed solutions have been implemented in the context of a specific mobility management solution, but the results are of general applicability. The Linux implementation is available as Open Source.
Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors
Venue: arXiv cs.CC 2018
Year: 2018

The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A binary CSP instance can be presented as a labelled graph encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of this graph. One type of restriction that has previously been considered is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture classes defined by language restrictions, or the well-known structural property of acyclicity. In this paper we extend the notion of pattern and introduce the notion of a topological minor of a binary CSP instance. By forbidding a finite set of patterns from occurring as topological minors we obtain a compact mechanism for expressing novel tractable subproblems of the binary CSP, including new generalisations of the class of acyclic instances. Forbidding a finite set of patterns as topological minors also captures all other tractable structural restrictions of the binary CSP. Moreover, we show that several patterns give rise to tractable subproblems if forbidden as topological minors but not if forbidden as sub-patterns. Finally, we introduce the idea of augmented patterns that allows for the identification of more tractable classes, including all language restrictions of the binary CSP.
Multivariate Cryptography with Mappings of Discrete Logarithms and Polynomials
Venue: arXiv cs.CR 2018
Year: 2018

In this paper, algorithms for multivariate public key cryptography and digital signature are described. Plain messages and encrypted messages are arrays, consisting of elements from a fixed finite ring or field. The encryption and decryption algorithms are based on multivariate mappings. The security of the private key depends on the difficulty of solving a system of parametric simultaneous multivariate equations involving polynomial or exponential mappings. The method is a general purpose utility for most data encryption, digital certificate or digital signature applications.
Efficient Training for Positive Unlabeled Learning
Venue: arXiv cs.LG 2018
Year: 2018

Positive unlabeled (PU) learning is useful in various practical situations, where there is a need to learn a classifier for a class of interest from an unlabeled data set, which may contain anomalies as well as samples from unknown classes. The learning task can be formulated as an optimization problem under the framework of statistical learning theory. Recent studies have theoretically analyzed its properties and generalization performance, nevertheless, little effort has been made to consider the problem of scalability, especially when large sets of unlabeled data are available. In this work we propose a novel scalable PU learning algorithm that is theoretically proven to provide the optimal solution, while showing superior computational and memory performance. Experimental evaluation confirms the theoretical evidence and shows that the proposed method can be successfully applied to a large variety of real-world problems involving PU learning.
Comparing Speech and Keyboard Text Entry for Short Messages in Two Languages on Touchscreen Phones
Venue: arXiv cs.HC 2018
Year: 2018

With the ubiquity of mobile touchscreen devices like smartphones, two widely used text entry methods have emerged: small touch-based keyboards and speech recognition. Although speech recognition has been available on desktop computers for years, it has continued to improve at a rapid pace, and it is currently unknown how today's modern speech recognizers compare to state-of-the-art mobile touch keyboards, which also have improved considerably since their inception. To discover both methods' "upper-bound performance," we evaluated them in English and Mandarin Chinese on an Apple iPhone 6 Plus in a laboratory setting. Our experiment was carried out using Baidu's Deep Speech 2, a deep learning-based speech recognition system, and the built-in Qwerty (English) or Pinyin (Mandarin) Apple iOS keyboards. We found that with speech recognition, the English input rate was 2.93 times faster (153 vs. 52 WPM), and the Mandarin Chinese input rate was 2.87 times faster (123 vs. 43 WPM) than the keyboard for short message transcription under laboratory conditions for both methods. Furthermore, although speech made fewer errors during entry (5.30% vs. 11.22% corrected error rate), it left slightly more errors in the final transcribed text (1.30% vs. 0.79% uncorrected error rate). Our results show that comparatively, under ideal conditions for both methods, upper-bound speech recognition performance has greatly improved compared to prior systems, and might see greater uptake in the future, although further study is required to quantify performance in non-laboratory settings for both methods.
"Sampling"' as a Baseline Optimizer for Search-based Software Engineering
Venue: arXiv cs.SE 2018
Year: 2018

Increasingly, Software Engineering (SE) researchers use search-based optimization techniques to solve SE problems with multiple conflicting objectives. These techniques often apply CPU-intensive evolutionary algorithms to explore generations of mutations to a population of candidate solutions. An alternative approach, proposed in this paper, is to start with a very large population and sample down to just the better solutions. We call this method "SWAY", short for "the sampling way". Sway is very simple to implement and, in studies with various software engineering models, this sampling approach was found to be competitive with corresponding state-of-the-art evolutionary algorithms while requiring far less computation cost. Considering the simplicity and effectiveness of Sway, we, therefore, propose this approach as a baseline method for search-based software engineering models, especially for models that are very slow to execute.
Finding Trends in Software Research
Venue: arXiv cs.SE 2018
Year: 2018

This paper explores the structure of research papers in software engineering. Using text mining, we study 35,391 software engineering (SE) papers from 34 leading SE venues over the last 25 years. These venues were divided, nearly evenly, between conferences and journals. An important aspect of this analysis is that it is fully automated and repeatable. To achieve that automation, we used a stable topic modeling technique called LDADE that fully automates parameter tuning in LDA. Using LDADE, we mine 11 topics that represent much of the structure of contemporary SE. The 11 topics presented here should not be "set in stone" as the only topics worthy of study in SE. Rather our goal is to report that (a) text mining methods can detect large scale trends within our community; (b) those topic change with time; so (c) it is important to have automatic agents that can update our understanding of our community whenever new data arrives.
What is Wrong with Topic Modeling? (and How to Fix it Using Search-based Software Engineering)
Venue: arXiv cs.SE 2018
Year: 2018

Context: Topic modeling finds human-readable structures in unstructured textual data. A widely used topic modeler is Latent Dirichlet allocation. When run on different datasets, LDA suffers from "order effects" i.e. different topics are generated if the order of training data is shuffled. Such order effects introduce a systematic error for any study. This error can relate to misleading results;specifically, inaccurate topic descriptions and a reduction in the efficacy of text mining classification results. Objective: To provide a method in which distributions generated by LDA are more stable and can be used for further analysis. Method: We use LDADE, a search-based software engineering tool that tunes LDA's parameters using DE (Differential Evolution). LDADE is evaluated on data from a programmer information exchange site (Stackoverflow), title and abstract text of thousands ofSoftware Engineering (SE) papers, and software defect reports from NASA. Results were collected across different implementations of LDA (Python+Scikit-Learn, Scala+Spark); across different platforms (Linux, Macintosh) and for different kinds of LDAs (VEM,or using Gibbs sampling). Results were scored via topic stability and text mining classification accuracy. Results: In all treatments: (i) standard LDA exhibits very large topic instability; (ii) LDADE's tunings dramatically reduce cluster instability; (iii) LDADE also leads to improved performances for supervised as well as unsupervised learning. Conclusion: Due to topic instability, using standard LDA with its "off-the-shelf" settings should now be depreciated. Also, in future, we should require SE papers that use LDA to test and (if needed) mitigate LDA topic instability. Finally, LDADE is a candidate technology for effectively and efficiently reducing that instability.
A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity
Venue: arXiv cs.IT 2018
Year: 2018

We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based upon Solomonoff-Levin's theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities e.g. as spotted by some popular lossless compression schemes. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object and to estimate an upper bound on the length of the shortest computer program that produces said original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we demonstrate the power of CTM on low algorithmic-randomness objects that are assigned maximal entropy (e.g. $π$) but whose numerical approximations are closer to the theoretical low algorithmic-randomness expectation. We also test the measure on larger objects including dual, isomorphic and cospectral graphs for which we know that algorithmic randomness is low. We also release implementations of the methods in most major programming languages---Wolfram Language (Mathematica), Matlab, R, Perl, Python, Pascal, C++, and Haskell---and a free online algorithmic complexity calculator.
On Gaussian MACs with Variable-Length Feedback and Non-Vanishing Error~Probabilities
Venue: arXiv cs.IT 2018
Year: 2018

We characterize the fundamental limits of transmission of information over a Gaussian multiple access channel (MAC) with the use of variable-length feedback codes and under a non-vanishing error probability formalism. We develop new achievability and converse techniques to handle the continuous nature of the channel and the presence of expected power constraints. We establish the $\varepsilon$-capacity regions and bounds on the second-order asymptotics of the Gaussian MAC with variable-length feedback with termination (VLFT) codes and stop-feedback codes. We show that the former outperforms the latter significantly. Due to the multi-terminal nature of the channel model, we leverage tools from renewal theory developed by Lai and Siegmund to bound the asymptotic behavior of the maximum of a finite number of stopping times.