OpenRaiser/Intern-Atlas huggingface dataset:
Method of Tibetan Person Knowledge Extraction
Venue: arXiv cs.CL 2016
Year: 2016

Person knowledge extraction is the foundation of the Tibetan knowledge graph construction, which provides support for Tibetan question answering system, information retrieval, information extraction and other researches, and promotes national unity and social stability. This paper proposes a SVM and template based approach to Tibetan person knowledge extraction. Through constructing the training corpus, we build the templates based the shallow parsing analysis of Tibetan syntactic, semantic features and verbs. Using the training corpus, we design a hierarchical SVM classifier to realize the entity knowledge extraction. Finally, experimental results prove the method has greater improvement in Tibetan person knowledge extraction.
Breadth First Search Vectorization on the Intel Xeon Phi
Venue: arXiv cs.DC 2016
Year: 2016

Breadth First Search (BFS) is a building block for graph algorithms and has recently been used for large scale analysis of information in a variety of applications including social networks, graph databases and web searching. Due to its importance, a number of different parallel programming models and architectures have been exploited to optimize the BFS. However, due to the irregular memory access patterns and the unstructured nature of the large graphs, its efficient parallelization is a challenge. The Xeon Phi is a massively parallel architecture available as an off-the-shelf accelerator, which includes a powerful 512 bit vector unit with optimized scatter and gather functions. Given its potential benefits, work related to graph traversing on this architecture is an active area of research. We present a set of experiments in which we explore architectural features of the Xeon Phi and how best to exploit them in a top-down BFS algorithm but the techniques can be applied to the current state-of-the-art hybrid, top-down plus bottom-up, algorithms. We focus on the exploitation of the vector unit by developing an improved highly vectorized OpenMP parallel algorithm, using vector intrinsics, and understanding the use of data alignment and prefetching. In addition, we investigate the impact of hyperthreading and thread affinity on performance, a topic that appears under researched in the literature. As a result, we achieve what we believe is the fastest published top-down BFS algorithm on the version of Xeon Phi used in our experiments. The vectorized BFS top-down source code presented in this paper can be available on request as free-to-use software.
Joint Face Detection and Alignment using Multi-task Cascaded Convolutional Networks
Venue: arXiv cs.CV 2016
Year: 2016

Face detection and alignment in unconstrained environment are challenging due to various poses, illuminations and occlusions. Recent studies show that deep learning approaches can achieve impressive performance on these two tasks. In this paper, we propose a deep cascaded multi-task framework which exploits the inherent correlation between them to boost up their performance. In particular, our framework adopts a cascaded structure with three stages of carefully designed deep convolutional networks that predict face and landmark location in a coarse-to-fine manner. In addition, in the learning process, we propose a new online hard sample mining strategy that can improve the performance automatically without manual sample selection. Our method achieves superior accuracy over the state-of-the-art techniques on the challenging FDDB and WIDER FACE benchmark for face detection, and AFLW benchmark for face alignment, while keeps real time performance.
Reasoning about Data Repetitions with Counter Systems
Venue: arXiv cs.LO 2016
Year: 2016

We study linear-time temporal logics interpreted over data words with multiple attributes. We restrict the atomic formulas to equalities of attribute values in successive positions and to repetitions of attribute values in the future or past. We demonstrate correspondences between satisfiability problems for logics and reachability-like decision problems for counter systems. We show that allowing/disallowing atomic formulas expressing repetitions of values in the past corresponds to the reachability/coverability problem in Petri nets. This gives us 2EXPSPACE upper bounds for several satisfiability problems. We prove matching lower bounds by reduction from a reachability problem for a newly introduced class of counter systems. This new class is a succinct version of vector addition systems with states in which counters are accessed via pointers, a potentially useful feature in other contexts. We strengthen further the correspondences between data logics and counter systems by characterizing the complexity of fragments, extensions and variants of the logic. For instance, we precisely characterize the relationship between the number of attributes allowed in the logic and the number of counters needed in the counter system.
High Dimensional Random Walks and Colorful Expansion
Venue: arXiv cs.CC 2016
Year: 2016

Random walks on bounded degree expander graphs have numerous applications, both in theoretical and practical computational problems. A key property of these walks is that they converge rapidly to their stationary distribution. In this work we {\em define high order random walks}: These are generalizations of random walks on graphs to high dimensional simplicial complexes, which are the high dimensional analogues of graphs. A simplicial complex of dimension $d$ has vertices, edges, triangles, pyramids, up to $d$-dimensional cells. For any $0 \leq i < d$, a high order random walk on dimension $i$ moves between neighboring $i$-faces (e.g., edges) of the complex, where two $i$-faces are considered neighbors if they share a common $(i+1)$-face (e.g., a triangle). The case of $i=0$ recovers the well studied random walk on graphs. We provide a {\em local-to-global criterion} on a complex which implies {\em rapid convergence of all high order random walks} on it. Specifically, we prove that if the $1$-dimensional skeletons of all the links of a complex are spectral expanders, then for {\em all} $0 \le i < d$ the high order random walk on dimension $i$ converges rapidly to its stationary distribution. We derive our result through a new notion of high dimensional combinatorial expansion of complexes which we term {\em colorful expansion}. This notion is a natural generalization of combinatorial expansion of graphs and is strongly related to the convergence rate of the high order random walks. We further show an explicit family of {\em bounded degree} complexes which satisfy this criterion. Specifically, we show that Ramanujan complexes meet this criterion, and thus form an explicit family of bounded degree high dimensional simplicial complexes in which all of the high order random walks converge rapidly to their stationary distribution.
Demystifying Fixed k-Nearest Neighbor Information Estimators
Venue: arXiv cs.LG 2016
Year: 2016

Estimating mutual information from i.i.d. samples drawn from an unknown joint density function is a basic statistical problem of broad interest with multitudinous applications. The most popular estimator is one proposed by Kraskov and Stögbauer and Grassberger (KSG) in 2004, and is nonparametric and based on the distances of each sample to its $k^{\rm th}$ nearest neighboring sample, where $k$ is a fixed small integer. Despite its widespread use (part of scientific software packages), theoretical properties of this estimator have been largely unexplored. In this paper we demonstrate that the estimator is consistent and also identify an upper bound on the rate of convergence of the bias as a function of number of samples. We argue that the superior performance benefits of the KSG estimator stems from a curious "correlation boosting" effect and build on this intuition to modify the KSG estimator in novel ways to construct a superior estimator. As a byproduct of our investigations, we obtain nearly tight rates of convergence of the $\ell_2$ error of the well known fixed $k$ nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.
Detector Based Radio Tomographic Imaging
Venue: arXiv cs.ET 2016
Year: 2016

Received signal strength based radio tomographic imaging is a popular device-free indoor localization method which reconstructs the spatial loss field of the environment using measurements from a dense wireless network. Existing methods solve an associated inverse problem using algebraic or compressed sensing reconstruction algorithms. We propose an alternative imaging method that reconstructs spatial field of occupancy using a back-projection based reconstruction algorithm. The introduced system has the following advantages over the other imaging based methods: i.) significantly lower computational complexity such that no floating point multiplication is required; ii.) each link's measured data is compressed to a single bit, providing improved scalability; iii.) physically significant and repeatable parameters. The proposed method is validated using measurement data. Results show that the proposed method achieves the above advantages without loss of accuracy compared to the other available methods.
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Venue: arXiv cs.CC 2016
Year: 2016

We prove that with high probability over the choice of a random graph $G$ from the Erdős-Rényi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$. This yields a nearly tight $n^{1/2 - o(1)}$ bound on the value of this program for any degree $d = o(\log n)$. Moreover we introduce a new framework that we call \emph{pseudo-calibration} to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.
Shallow Parsing Pipeline for Hindi-English Code-Mixed Social Media Text
Venue: arXiv cs.CL 2016
Year: 2016

In this study, the problem of shallow parsing of Hindi-English code-mixed social media text (CSMT) has been addressed. We have annotated the data, developed a language identifier, a normalizer, a part-of-speech tagger and a shallow parser. To the best of our knowledge, we are the first to attempt shallow parsing on CSMT. The pipeline developed has been made available to the research community with the goal of enabling better text analysis of Hindi English CSMT. The pipeline is accessible at http://bit.ly/csmt-parser-api .
Automatic Parallelization: Executing Sequential Programs on a Task-Based Parallel Runtime
Venue: arXiv cs.PL 2016
Year: 2016

There are billions of lines of sequential code inside nowadays' software which do not benefit from the parallelism available in modern multicore architectures. Automatically parallelizing sequential code, to promote an efficient use of the available parallelism, has been a research goal for some time now. This work proposes a new approach for achieving such goal. We created a new parallelizing compiler that analyses the read and write instructions, and control-flow modifications in programs to identify a set of dependencies between the instructions in the program. Afterwards, the compiler, based on the generated dependencies graph, rewrites and organizes the program in a task-oriented structure. Parallel tasks are composed by instructions that cannot be executed in parallel. A work-stealing-based parallel runtime is responsible for scheduling and managing the granularity of the generated tasks. Furthermore, a compile-time granularity control mechanism also avoids creating unnecessary data-structures. This work focuses on the Java language, but the techniques are general enough to be applied to other programming languages. We have evaluated our approach on 8 benchmark programs against OoOJava, achieving higher speedups. In some cases, values were close to those of a manual parallelization. The resulting parallel code also has the advantage of being readable and easily configured to improve further its performance manually.
Fuzzy Logic Trajectory Tracking Controller for a Tanker
Venue: arXiv cs.SY 2016
Year: 2016

This paper proposes a fuzzy logic controller for design of autopilot of a ship. Triangular membership functions have been use for fuzzification and the centroid method for defuzzification. A nonlinear mathematical model of an oil tanker has been considered whose parameters vary with the depth of water. The performance of proposed controller has been tested under both course changing and trajectory keeping mode of operations. It has been demonstrated that the performance is robust in shallow as well as deep waters.
Separating Sets of Strings by Finding Matching Patterns is Almost Always Hard
Venue: arXiv cs.CC 2016
Year: 2016

We study the complexity of the problem of searching for a set of patterns that separate two given sets of strings. This problem has applications in a wide variety of areas, most notably in data mining, computational biology, and in understanding the complexity of genetic algorithms. We show that the basic problem of finding a small set of patterns that match one set of strings but do not match any string in a second set is difficult (NP-complete, W[2]-hard when parameterized by the size of the pattern set, and APX-hard). We then perform a detailed parameterized analysis of the problem, separating tractable and intractable variants. In particular we show that parameterizing by the size of pattern set and the number of strings, and the size of the alphabet and the number of strings give FPT results, amongst others.
Thesis: Multiple Kernel Learning for Object Categorization
Venue: arXiv cs.CV 2016
Year: 2016

Object Categorization is a challenging problem, especially when the images have clutter background, occlusions or different lighting conditions. In the past, many descriptors have been proposed which aid object categorization even in such adverse conditions. Each descriptor has its own merits and de-merits. Some descriptors are invariant to transformations while the others are more discriminative. Past research has shown that, employing multiple descriptors rather than any single descriptor leads to better recognition. The problem of learning the optimal combination of the available descriptors for a particular classification task is studied. Multiple Kernel Learning (MKL) framework has been developed for learning an optimal combination of descriptors for object categorization. Existing MKL formulations often employ block l-1 norm regularization which is equivalent to selecting a single kernel from a library of kernels. Since essentially a single descriptor is selected, the existing formulations maybe sub- optimal for object categorization. A MKL formulation based on block l-infinity norm regularization has been developed, which chooses an optimal combination of kernels as opposed to selecting a single kernel. A Composite Multiple Kernel Learning(CKL) formulation based on mixed l-infinity and l-1 norm regularization has been developed. These formulations end in Second Order Cone Programs(SOCP). Other efficient alter- native algorithms for these formulation have been implemented. Empirical results on benchmark datasets show significant improvement using these new MKL formulations.
Attributes as Semantic Units between Natural Language and Visual Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Impressive progress has been made in the fields of computer vision and natural language processing. However, it remains a challenge to find the best point of interaction for these very different modalities. In this chapter we discuss how attributes allow us to exchange information between the two modalities and in this way lead to an interaction on a semantic level. Specifically we discuss how attributes allow using knowledge mined from language resources for recognizing novel visual categories, how we can generate sentence description about images and video, how we can ground natural language in visual content, and finally, how we can answer natural language questions about images.
Relative Coobservability in Decentralized Supervisory Control of Discrete-Event Systems
Venue: arXiv cs.SY 2016
Year: 2016

We study the new concept of relative coobservability in decentralized supervisory control of discrete-event systems under partial observation. This extends our previous work on relative observability from a centralized setup to a decentralized one. A fundamental concept in decentralized supervisory control is coobservability (and its several variations); this property is not, however, closed under set union, and hence there generally does not exist the supremal element. Our proposed relative coobservability, although stronger than coobservability, is algebraically well-behaved, and the supremal relatively coobservable sublanguage of a given language exists. We present an algorithm to compute this supremal sublanguage. Moreover, relative coobservability is weaker than conormality, which is also closed under set union; unlike conormality, relative coobservability imposes no constraint on disabling unobservable controllable events.
The Right Mutation Strength for Multi-Valued Decision Variables
Venue: arXiv cs.NE 2016
Year: 2016

The most common representation in evolutionary computation are bit strings. This is ideal to model binary decision variables, but less useful for variables taking more values. With very little theoretical work existing on how to use evolutionary algorithms for such optimization problems, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over $Ω= \{0, 1, \dots, r-1\}^n$. More precisely, we regard a variety of problem classes requesting the component-wise minimization of the distance to an unknown target vector $z \in Ω$. For such problems we see a crucial difference in how we extend the standard-bit mutation operator to these multi-valued domains. While it is natural to select each position of the solution vector to be changed independently with probability $1/n$, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of $Θ(nr \log n)$. If we change each selected position by either $+1$ or $-1$ (random choice), the optimization time reduces to $Θ(nr + n\log n)$. If we use a random mutation strength $i \in \{0,1,\ldots,r-1\}^n$ with probability inversely proportional to $i$ and change the selected position by either $+i$ or $-i$ (random choice), then the optimization time becomes $Θ(n \log(r)(\log(n)+\log(r)))$, bringing down the dependence on $r$ from linear to polylogarithmic. One of our results depends on a new variant of the lower bounding multiplicative drift theorem.
Channel Parameter Estimation for LOS MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we consider the estimation of channel coefficients and frequency offsets for LOS MIMO systems. We propose that by exploiting the structure of the channel matrix, which is present due to the geometrical nature of the channel, the estimation process can be enhanced. If a single oscillator setup is used at transmitter and receiver, respectively, this structure is preserved and can be exploited. Some methods using this fact are discussed and their performance is evaluated with respect to estimation accuracy, revealing that with relatively short training sequences, estimation results close to the fundamental bounds can be achieved.
A sharp bound on RIC in generalized orthogonal matching pursuit
Venue: arXiv cs.IT 2016
Year: 2016

Generalized orthogonal matching pursuit (gOMP) algorithm has received much attention in recent years as a natural extension of orthogonal matching pursuit. It is used to recover sparse signals in compressive sensing. In this paper, a new bound is obtained for the exact reconstruction of every $K$-sparse signal via the gOMP algorithm in the noiseless case. That is, if the restricted isometry constant (RIC) $δ_{NK+1}$ of the sensing matrix $A$ satisfies \begin{eqnarray*} δ_{NK+1}<\frac{1}{\sqrt{\frac{K}{N}+1}}, \end{eqnarray*} then the gOMP can perfectly recover every $K$-sparse signal $x$ from $y=Ax$. Furthermore, the bound is proved to be sharp in the following sense. For any given positive integer $K$, we construct a matrix $A$ with the RIC \begin{eqnarray*} δ_{NK+1}=\frac{1}{\sqrt{\frac{K}{N}+1}} \end{eqnarray*} such that the gOMP may fail to recover some $K$-sparse signal $x$. In the noise case, an extra condition on the minimum magnitude of the nonzero components of every $K-$sparse signal combining with the above bound on RIC of the sensing matrix $A$ is sufficient to recover the true support of every $K$-sparse signal by the gOMP.
Joint Device Positioning and Clock Synchronization in 5G Ultra-Dense Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this article, we address the prospects and key enabling technologies for highly efficient and accurate device positioning and tracking in 5G radio access networks. Building on the premises of ultra-dense networks as well as on the adoption of multicarrier waveforms and antenna arrays in the access nodes (ANs), we first formulate extended Kalman filter (EKF)-based solutions for computationally efficient joint estimation and tracking of the time of arrival (ToA) and direction of arrival (DoA) of the user nodes (UNs) using uplink reference signals. Then, a second EKF stage is proposed in order to fuse the individual DoA/ToA estimates from one or several ANs into a UN position estimate. Since all the processing takes place at the network side, the computing complexity and energy consumption at the UN side are kept to a minimum. The cascaded EKFs proposed in this article also take into account the unavoidable relative clock offsets between UNs and ANs, such that reliable clock synchronization of the access-link is obtained as a valuable by-product. The proposed cascaded EKF scheme is then revised and extended to more general and challenging scenarios where not only the UNs have clock offsets against the network time, but also the ANs themselves are not mutually synchronized in time. Finally, comprehensive performance evaluations of the proposed solutions on a realistic 5G network setup, building on the METIS project based outdoor Madrid map model together with complete ray tracing based propagation modeling, are provided. The obtained results clearly demonstrate that by using the developed methods, sub-meter scale positioning and tracking accuracy of moving devices is indeed technically feasible in future 5G radio access networks operating at sub-6GHz frequencies, despite the realistic assumptions related to clock offsets and potentially even under unsynchronized network elements.
Fundamental Limits of Simultaneous Energy and Information Transmission
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, existing results regarding the fundamental limits of simultaneous energy and information transmission in wireless networks are reviewed. In point-to-point channels, the fundamental limits on the information rate given a minimum energy rate constraint are fully characterized by the notion of information-energy capacity function introduced by Varshney in 2008. In a centralized multi-user channel, the fundamental limits on the information rates given a minimum energy rate constraint are described by the notion of information-energy capacity region introduced by Fouladgar and Simeone in 2012. Alternatively, in a decentralized multi-user channel, the authors have recently introduced the notion of information-energy Nash region to describe these fundamental limits. All these fundamental limits reveal the intrinsic trade-off between the two conflicting tasks of information and energy transmission.