OpenRaiser/Intern-Atlas huggingface dataset:
Gibberish Semantics: How Good is Russian Twitter in Word Semantic Similarity Task?
Venue: arXiv cs.CL 2016
Year: 2016

The most studied and most successful language models were developed and evaluated mainly for English and other close European languages, such as French, German, etc. It is important to study applicability of these models to other languages. The use of vector space models for Russian was recently studied for multiple corpora, such as Wikipedia, RuWac, lib.ru. These models were evaluated against word semantic similarity task. For our knowledge Twitter was not considered as a corpus for this task, with this work we fill the gap. Results for vectors trained on Twitter corpus are comparable in accuracy with other single-corpus trained models, although the best performance is currently achieved by combination of multiple corpora.
Proving completeness of logic programs with the cut
Venue: arXiv cs.LO 2016
Year: 2016

Completeness of a logic program means that the program produces all the answers required by its specification. The cut is an important construct of programming language Prolog. It prunes part of the search space, this may result in a loss of completeness. This paper proposes a way of proving completeness of programs with the cut. The semantics of the cut is formalized by describing how SLD-trees are pruned. A sufficient condition for completeness is presented, proved sound, and illustrated by examples.
Overshooting and $L^1$-Norms of a Class of Nyquist Filters
Venue: arXiv cs.IT 2016
Year: 2016

To tightly control the signal envelope, estimating the peak regrowth between FFT samples is an important sub-problem in multicarrier communications. While the problem is well-investigated for trigonometric polynomials (i.e. OFDM), the impact of an aperiodic transmit filter is important too and typically neglected in the peak regrowth analysis. In this paper, we provide new bounds on the overshooting between samples for general multicarrier signals improving on available bounds for small oversampling factors. In particular, we generalize a result of [1, Theorem 4.10]. Our results will be extended to bound overshooting of a class of Nyquist filters as well. Eventually, results are related to some respective $L^1$-properties of these filters with application to filter design.
Characterizing classes of regular languages using prefix codes of bounded synchronization delay
Venue: arXiv cs.FL 2016
Year: 2016

In this paper we continue a classical work of Schützenberger on codes with bounded synchronization delay. He was interested to characterize those regular languages where the groups in the syntactic monoid belong to a variety $H$. He allowed operations on the language side which are union, intersection, concatenation and modified Kleene-star involving a mapping of a prefix code of bounded synchronization delay to a group $G\in H$, but no complementation. In our notation this leads to the language classes $SD_G(A^\infty)$ and $SD_H(A^\infty$). Our main result shows that $SD_H(A^\infty)$ always corresponds to the languages having syntactic monoids where all subgroups are in $H$. Schützenberger showed this for a variety $H$ if $H$ contains Abelian groups, only. Our method shows the general result for all $H$ directly on finite and infinite words. Furthermore, we introduce the notion of local Rees products which refers to a simple type of classical Rees extensions. We give a decomposition of a monoid in terms of its groups and local Rees products. This gives a somewhat similar, but simpler decomposition than in Rhodes' synthesis theorem. Moreover, we need a singly exponential number of operations, only. Finally, our decomposition yields an answer to a question in a recent paper of Almeida and Klíma about varieties that are closed under Rees products.
Bounded Model Checking of Pointer Programs Revisited
Venue: arXiv cs.LO 2016
Year: 2016

Bounded model checking of pointer programs is a debugging technique for programs that manipulate dynamically allocated pointer structures on the heap. It is based on the following four observations. First, error conditions like dereference of a dangling pointer, are expressible in a~fragment of first-order logic with two-variables. Second, the fragment is closed under weakest preconditions wrt. finite paths. Third, data structures like trees, lists etc. are expressible by inductive predicates defined in a fragment of Datalog. Finally, the combination of the two fragments of the two-variable logic and Datalog is decidable. In this paper we improve this technique by extending the expressivity of the underlying logics. In a~sequence of examples we demonstrate that the new logic is capable of modeling more sophisticated data structures with more complex dependencies on heaps and more complex analyses.
Leveraging Synergy of 5G SDWN and Multi-Layer Resource Management for Network Optimization
Venue: arXiv cs.NI 2016
Year: 2016

Fifth-generation (5G) cellular wireless networks are envisioned to predispose service-oriented, flexible, and spectrum/energy-efficient edge-to-core infrastructure, aiming to offer diverse applications. Convergence of software-defined networking (SDN), software-defined radio (SDR) compatible with multiple radio access technologies (RATs), and virtualization on the concept of 5G software-defined wireless networking (5G-SDWN) is a promising approach to provide such a dynamic network. The principal technique behind the 5G-SDWN framework is the separation of the control and data planes, from the deep core entities to edge wireless access points (APs). This separation allows the abstraction of resources as transmission parameters of each user over the 5G-SDWN. In this user-centric and service-oriented environment, resource management plays a critical role to achieve efficiency and reliability. However, it is natural to wonder if 5G-SDWN can be leveraged to enable converged multi-layer resource management over the portfolio of resources, and reciprocally, if CML resource management can effectively provide performance enhancement and reliability for 5G-SDWN. We believe that replying to these questions and investigating this mutual synergy are not trivial, but multidimensional and complex for 5G-SDWN, which consists of different technologies and also inherits legacy generations of wireless networks. In this paper, we propose a flexible protocol structure based on three mentioned pillars for 5G-SDWN, which can handle all the required functionalities in a more crosslayer manner. Based on this, we demonstrate how the general framework of CML resource management can control the end user quality of experience. For two scenarios of 5G-SDWN, we investigate the effects of joint user-association and resource allocation via CML resource management to improve performance in a virtualized network.
2-Distance Colorings of Integer Distance Graphs
Venue: arXiv cs.DM 2016
Year: 2016

A 2-distance k-coloring of a graph G is a mapping from V (G) to the set of colors {1,. .. , k} such that every two vertices at distance at most 2 receive distinct colors. The 2-distance chromatic number $χ$ 2 (G) of G is then the mallest k for which G admits a 2-distance k-coloring. For any finite set of positive integers D = {d 1 ,. .. , d k }, the integer distance graph G = G(D) is the infinite graph defined by V (G) = Z and uv $\in$ E(G) if and only if |v -- u| $\in$ D. We study the 2-distance chromatic number of integer distance graphs for several types of sets D. In each case, we provide exact values or upper bounds on this parameter and characterize those graphs G(D) with $χ$ 2 (G(D)) = Δ(G(D)) + 1.
You Are What Apps You Use: Demographic Prediction Based on User's Apps
Venue: arXiv cs.SI 2016
Year: 2016

Understanding the demographics of app users is crucial, for example, for app developers, who wish to target their advertisements more effectively. Our work addresses this need by studying the predictability of user demographics based on the list of a user's apps which is readily available to many app developers. We extend previous work on the problem on three frontiers: (1) We predict new demographics (age, race, and income) and analyze the most informative apps for four demographic attributes included in our analysis. The most predictable attribute is gender (82.3 % accuracy), whereas the hardest to predict is income (60.3 % accuracy). (2) We compare several dimensionality reduction methods for high-dimensional app data, finding out that an unsupervised method yields superior results compared to aggregating the apps at the app category level, but the best results are obtained simply by the raw list of apps. (3) We look into the effect of the training set size and the number of apps on the predictability and show that both of these factors have a large impact on the prediction accuracy. The predictability increases, or in other words, a user's privacy decreases, the more apps the user has used, but somewhat surprisingly, after 100 apps, the prediction accuracy starts to decrease.
A Fast Distributed Algorithm for Large-Scale Demand Response Aggregation
Venue: arXiv cs.DC 2016
Year: 2016

A major challenge to implementing residential demand response is that of aligning the objectives of many households, each of which aims to minimize its payments and maximize its comfort level, while balancing this with the objectives of an aggregator that aims to minimize the cost of electricity purchased in a pooled wholesale market. This paper presents a fast distributed algorithm for aggregating a large number of households with a mixture of discrete and continuous energy levels. A distinctive feature of the method in this paper is that the nonconvex DR problem is decomposed in terms of households as opposed to devices, which allows incorporating more intricate couplings between energy storage devices, appliances and distributed energy resources. The proposed method is a fast distributed algorithm applied to the double smoothed dual function of the adopted DR model. The method is tested on systems with up to 2560 households, each with 10 devices on average. The proposed algorithm is designed to terminate in 60 iterations irrespective of system size, which can be ideal for an on-line version of this problem. Moreover, numerical results show that with minimal parameter tuning, the algorithm exhibits a very similar convergence behavior throughout the studied systems and converges to near-optimal solutions, which corroborates its scalability.
Broadcast Repair for Wireless Distributed Storage Systems
Venue: arXiv cs.IT 2016
Year: 2016

In wireless distributed storage systems, storage nodes are connected by wireless channels, which are broadcast in nature. This paper exploits this unique feature to design an efficient repair mechanism, called broadcast repair, for wireless distributed storage systems with multiple-node failures. Since wireless channels are typically bandwidth limited, we advocate a new measure on repair performance called repair-transmission bandwidth, which measures the average number of packets transmitted by helper nodes per failed node. The fundamental tradeoff between storage amount and repair-transmission bandwidth is obtained. It is shown that broadcast repair outperforms cooperative repair, which is the basic repair method for wired distributed storage systems with multiple-node failures, in terms of storage efficiency and repair-transmission bandwidth, thus yielding a better tradeoff curve.
Design and Analysis Framework for Sparse FIR Channel Shortening
Venue: arXiv cs.IT 2016
Year: 2016

A major performance and complexity limitation in broadband communications is the long channel delay spread which results in a highly-frequency-selective channel frequency response. Channel shortening equalizers (CSEs) are used to ensure that the cascade of a long channel impulse response (CIR) and the CSE is approximately equivalent to a target impulse response (TIR) with much shorter delay spread. In this paper, we propose a general framework that transforms the problems of design of sparse CSE and TIR finite impulse response (FIR) filters into the problem of sparsest-approximation of a vector in different dictionaries. In addition, we compare several choices of sparsifying dictionaries under this framework. Furthermore, the worst-case coherence of these dictionaries, which determines their sparsifying effectiveness, are analytically and/or numerically evaluated. Finally, the usefulness of the proposed framework for the design of sparse CSE and TIR filters is validated through numerical experiments.
Event Search and Analytics: Detecting Events in Semantically Annotated Corpora for Search and Analytics
Venue: arXiv cs.IR 2016
Year: 2016

In this article, I present the questions that I seek to answer in my PhD research. I posit to analyze natural language text with the help of semantic annotations and mine important events for navigating large text corpora. Semantic annotations such as named entities, geographic locations, and temporal expressions can help us mine events from the given corpora. These events thus provide us with useful means to discover the locked knowledge in them. I pose three problems that can help unlock this knowledge vault in semantically annotated text corpora: i. identifying important events; ii. semantic search; and iii. event analytics.
Component Based Modeling of Ultrasound Signals
Venue: arXiv cs.IT 2016
Year: 2016

This work proposes a component based model for the raw ultrasound signals acquired by the transducer elements. Based on this approach, before undergoing the standard digital processing chain, every sampled raw signal is first decomposed into a smooth background signal and a strong reflectors component. The decomposition allows for a suited processing scheme to be adjusted for each component individually. We demonstrate the potential benefit of this approach in image enhancement by suppressing side lobe artifacts, and in improvement of digital data compression. Applying our proposed processing schemes to real cardiac ultrasound data, we show that by separating the two components and compressing them individually, over twenty-fold reduction of the data size is achieved while retaining the image contents.
A Graph-Based Semantics Workbench for Concurrent Asynchronous Programs
Venue: arXiv cs.SE 2016
Year: 2016

A number of novel programming languages and libraries have been proposed that offer simpler-to-use models of concurrency than threads. It is challenging, however, to devise execution models that successfully realise their abstractions without forfeiting performance or introducing unintended behaviours. This is exemplified by SCOOP---a concurrent object-oriented message-passing language---which has seen multiple semantics proposed and implemented over its evolution. We propose a "semantics workbench" with fully and semi-automatic tools for SCOOP, that can be used to analyse and compare programs with respect to different execution models. We demonstrate its use in checking the consistency of semantics by applying it to a set of representative programs, and highlighting a deadlock-related discrepancy between the principal execution models of the language. Our workbench is based on a modular and parameterisable graph transformation semantics implemented in the GROOVE tool. We discuss how graph transformations are leveraged to atomically model intricate language abstractions, and how the visual yet algebraic nature of the model can be used to ascertain soundness.
Piecewise Testable Languages and Nondeterministic Automata
Venue: arXiv cs.FL 2016
Year: 2016

A regular language is $k$-piecewise testable if it is a finite boolean combination of languages of the form $Σ^* a_1 Σ^* \cdots Σ^* a_n Σ^*$, where $a_i\inΣ$ and $0\le n \le k$. Given a DFA $A$ and $k\ge 0$, it is an NL-complete problem to decide whether the language $L(A)$ is piecewise testable and, for $k\ge 4$, it is coNP-complete to decide whether the language $L(A)$ is $k$-piecewise testable. It is known that the depth of the minimal DFA serves as an upper bound on $k$. Namely, if $L(A)$ is piecewise testable, then it is $k$-piecewise testable for $k$ equal to the depth of $A$. In this paper, we show that some form of nondeterminism does not violate this upper bound result. Specifically, we define a class of NFAs, called ptNFAs, that recognize piecewise testable languages and show that the depth of a ptNFA provides an (up to exponentially better) upper bound on $k$ than the minimal DFA. We provide an application of our result, discuss the relationship between $k$-piecewise testability and the depth of NFAs, and study the complexity of $k$-piecewise testability for ptNFAs.
Easy-First Dependency Parsing with Hierarchical Tree LSTMs
Venue: arXiv cs.CL 2016
Year: 2016

We suggest a compositional vector representation of parse trees that relies on a recursive combination of recurrent-neural network encoders. To demonstrate its effectiveness, we use the representation as the backbone of a greedy, bottom-up dependency parser, achieving state-of-the-art accuracies for English and Chinese, without relying on external word embeddings. The parser's implementation is available for download at the first author's webpage.
Optimal Auctions for Negatively Correlated Items
Venue: arXiv cs.GT 2016
Year: 2016

We consider the problem of designing revenue-optimal auctions for selling two items and bidders' valuations are independent among bidders but negatively correlated among items. In this paper, we obtain the closed-form optimal auction for this setting, by directly addressing the two difficulties above. In particular, the first difficulty is that when pointwise maximizing virtual surplus under multi-dimensional feasibility (i.e., the Border feasibility), (1) neither the optimal interim allocation is trivially monotone in the virtual value, (2) nor the virtual value is monotone in the bidder's type. As a result, the optimal interim allocations resulting from virtual surplus maximization no longer guarantees BIC. To address (1), we prove a generalization of Border's theorem and show that optimal interim allocation is indeed monotone in the virtual value. To address (2), we adapt Myerson's ironing procedure to this setting by redefining the (ironed) virtual value as a function of the lowest utility point. The second difficulty, perhaps a more challenging one, is that the lowest utility type in general is no longer at the endpoints of the type interval. To address this difficulty, we show by construction that there exist an allocation rule and an induced lowest utility type such that they form a solution of the virtual surplus maximization and in the meanwhile guarantees IIR. In the single bidder case, the optimal auction consists of a randomized bundle menu and a deterministic bundle menu; while in the multiple bidder case, the optimal auction is a randomization between two extreme mechanisms. The optimal solutions of our setting can be implemented by a Bayesian IC and IR auction, however, perhaps surprisingly, the revenue of this auction cannot be achieved by any (dominant-strategy) IC and IR auction.
Asymptotic behavior of $\ell_p$-based Laplacian regularization in semi-supervised learning
Venue: arXiv cs.LG 2016
Year: 2016

Given a weighted graph with $N$ vertices, consider a real-valued regression problem in a semi-supervised setting, where one observes $n$ labeled vertices, and the task is to label the remaining ones. We present a theoretical study of $\ell_p$-based Laplacian regularization under a $d$-dimensional geometric random graph model. We provide a variational characterization of the performance of this regularized learner as $N$ grows to infinity while $n$ stays constant, the associated optimality conditions lead to a partial differential equation that must be satisfied by the associated function estimate $\hat{f}$. From this formulation we derive several predictions on the limiting behavior the $d$-dimensional function $\hat{f}$, including (a) a phase transition in its smoothness at the threshold $p = d + 1$, and (b) a tradeoff between smoothness and sensitivity to the underlying unlabeled data distribution $P$. Thus, over the range $p \leq d$, the function estimate $\hat{f}$ is degenerate and "spiky," whereas for $p\geq d+1$, the function estimate $\hat{f}$ is smooth. We show that the effect of the underlying density vanishes monotonically with $p$, such that in the limit $p = \infty$, corresponding to the so-called Absolutely Minimal Lipschitz Extension, the estimate $\hat{f}$ is independent of the distribution $P$. Under the assumption of semi-supervised smoothness, ignoring $P$ can lead to poor statistical performance, in particular, we construct a specific example for $d=1$ to demonstrate that $p=2$ has lower risk than $p=\infty$ due to the former penalty adapting to $P$ and the latter ignoring it. We also provide simulations that verify the accuracy of our predictions for finite sample sizes. Together, these properties show that $p = d+1$ is an optimal choice, yielding a function estimate $\hat{f}$ that is both smooth and non-degenerate, while remaining maximally sensitive to $P$.
Some essential skills and their combination in an architecture for a cognitive and interactive robot
Venue: arXiv cs.RO 2016
Year: 2016

The topic of joint actions has been deeply studied in the context of Human-Human interaction in order to understand how humans cooperate. Creating autonomous robots that collaborate with humans is a complex problem, where it is relevant to apply what has been learned in the context of Human-Human interaction. The question is what skills to implement and how to integrate them in order to build a cognitive architecture, allowing a robot to collaborate efficiently and naturally with humans. In this paper, we first list a set of skills that we consider essential for Joint Action, then we analyze the problem from the robot's point of view and discuss how they can be instantiated in human-robot scenarios. Finally, we open the discussion on how to integrate such skills into a cognitive architecture for human-robot collaborative problem solving and task achievement.
A Theorem on Multi-Objective Optimization Approach for Bit Allocation of Scalable Coding
Venue: arXiv cs.IT 2016
Year: 2016

In the current work, we have formulated the optimal bit-allocation problem for a scalable codec of images or videos as a constrained vector-valued optimization problem and demonstrated that there can be many optimal solutions, called Pareto optimal points. In practice, the Pareto points are derived via the weighted sum scalarization approach. An important question which arises is whether all the Pareto optimal points can be derived using the scalarization approach? The present paper provides a sufficient condition on the rate-distortion function of each resolution of a scalable codec to address the above question. The result indicated that if the rate-distortion function of each resolution is strictly decreasing and convex and the Pareto points form a continuous curve, then all the optimal Pareto points can be derived by using the scalarization method.
A Novel Interleaving Scheme for Polar Codes
Venue: arXiv cs.IT 2016
Year: 2016

It's known that the bit errors of polar codes with successive cancellation (SC) decoding are coupled. We call the coupled information bits the correlated bits. In this paper, concatenation schemes are studied for polar codes (as inner codes) and LDPC codes (as outer codes). In a conventional concatenation scheme, to achieve a better BER performance, one can divide all $N_l$ bits in a LDPC block into $N_l$ polar blocks to completely de-correlate the possible coupled errors. In this paper, we propose a novel interleaving scheme between a LDPC code and a polar code which breaks the correlation of the errors among the correlated bits. This interleaving scheme still keeps the simple SC decoding of polar codes while achieves a comparable BER performance at a much smaller delay compared with a $N_l$-block delay scheme.