OpenRaiser/Intern-Atlas huggingface dataset:
KGEval: Estimating Accuracy of Automatically Constructed Knowledge Graphs
Venue: arXiv cs.AI 2016
Year: 2016

Automatic construction of large knowledge graphs (KG) by mining web-scale text datasets has received considerable attention recently. Estimating accuracy of such automatically constructed KGs is a challenging problem due to their size and diversity. This important problem has largely been ignored in prior research we fill this gap and propose KGEval. KGEval binds facts of a KG using coupling constraints and crowdsources the facts that infer correctness of large parts of the KG. We demonstrate that the objective optimized by KGEval is submodular and NP-hard, allowing guarantees for our approximation algorithm. Through extensive experiments on real-world datasets, we demonstrate that KGEval is able to estimate KG accuracy more accurately compared to other competitive baselines, while requiring significantly lesser number of human evaluations.
Automatic Image De-fencing System
Venue: arXiv cs.CV 2016
Year: 2016

Tourists and Wild-life photographers are often hindered in capturing their cherished images or videos by a fence that limits accessibility to the scene of interest. The situation has been exacerbated by growing concerns of security at public places and a need exists to provide a tool that can be used for post-processing such fenced videos to produce a de-fenced image. There are several challenges in this problem, we identify them as Robust detection of fence/occlusions and Estimating pixel motion of background scenes and Filling in the fence/occlusions by utilizing information in multiple frames of the input video. In this work, we aim to build an automatic post-processing tool that can efficiently rid the input video of occlusion artifacts like fences. Our work is distinguished by two major contributions. The first is the introduction of learning based technique to detect the fences patterns with complicated backgrounds. The second is the formulation of objective function and further minimization through loopy belief propagation to fill-in the fence pixels. We observe that grids of Histogram of oriented gradients descriptor using Support vector machines based classifier significantly outperforms detection accuracy of texels in a lattice. We present results of experiments using several real-world videos to demonstrate the effectiveness of the proposed fence detection and de-fencing algorithm.
Ripple Distribution for Nonlinear Fibre-Optic Channels
Venue: arXiv cs.IT 2016
Year: 2016

Since Shannon proved that Gaussian distribution is the optimum for a linear channel with additive white Gaussian noise and he calculated the corresponding channel capacity, it remains the most applied distribution in optical communications while the capacity result is celebrated as the seminal linear Shannon limit. Yet, when it is applied in nonlinear channels (e.g. fiber-optics) it has been shown to be non-optimum, yielding the same result as for uncoded transmission in the high nonlinear regime. This has led to the notion of nonlinear Shannon limit, which predicts vanishing capacity at high nonlinearity. However, recent findings indicate that non-Gaussian distribution may lead to improved capacity estimations, urging for an exciting search for novel methods in nonlinear optical communications. Here for the first time, we show that it is possible to transmit information above the existing limits by using a novel probabilistic shaping of the input signal, which we call ripple distribution
Optimal Control for Network Coding Broadcast
Venue: arXiv cs.SY 2016
Year: 2016

Random linear network coding (RLNC) has been shown to efficiently improve the network performance in terms of reducing transmission delays and increasing the throughput in broadcast and multicast communications. However, it can result in increased storage and computational complexity at the receivers end. In our previous work we considered the broadcast transmission of large file to N receivers. We showed that the storage and complexity requirements at the receivers end can be greatly reduced when segmenting the file into smaller blocks and applying RLNC to these blocks. To that purpose, we proposed a packet scheduling policy, namely the Least Received. In this work we will prove the optimality of our previously proposed policy, in terms of file transfer completion time, when N = 2. We will model our system as a Markov Decision Process and prove the optimality of the policy using Dynamic Programming. Our intuition is that the Least Received policy may be optimal regardless of the number of receivers. Towards that end, we will provide experimental results that verify that ntuition.
An Alternating Automaton for First-Order Linear Temporal Logic--Tech Report
Venue: arXiv cs.FL 2016
Year: 2016

In this paper we give automata-based representation of LTL-FO$^+$ properties. LTL-FO$^+$ is an extension of LTL that includes first-order quantification over bounded variable, thus greatly increasing the expressivity of the language. An automata representation of this formalism allows greater ease in writing and understanding properties, as well as in performing manipulations, such as negation or emptiness checking. The automata representation of an LTL-FO$^+$ formula has finite size regardless of the domain of quantified variables, and the number of states that is linear in the size of the property.
STEPS: Predicting place attributes via spatio-temporal analysis
Venue: arXiv cs.SI 2016
Year: 2016

In recent years, a vast amount of research has been conducted on learning people's interests from their actions. Yet their collective actions also allow us to learn something about the world, in particular, infer attributes of places people visit or interact with. Imagine classifying whether a hotel has a gym or a swimming pool, or whether a restaurant has a romantic atmosphere without ever asking its patrons. Algorithms we present can do just that. Many web applications rely on knowing attributes of places, for instance, whether a particular restaurant has WiFi or offers outdoor seating. Such data can be used to support a range of user experiences, from explicit query-driven search to personalized place recommendations. However, obtaining these attributes is generally difficult, with existing approaches relying on crowdsourcing or parsing online reviews, both of which are noisy, biased, and have limited coverage. Here we present a novel approach to classifying place attributes, which learns from patrons' visit patterns based on anonymous observational data. Our method, STEPS, learns from aggregated sequences of place visits. For example, if many people visit the restaurant on a Saturday evening, coming from a luxury hotel or theater, and stay for a long time, then this restaurant is more likely to have a romantic atmosphere. On the other hand, if most people visit the restaurant on weekdays, coming from work or a grocery store, then the restaurant is less likely to be romantic. We show that such transition features are highly predictive of place attributes. In an extensive empirical evaluation, STEPS nearly doubled the coverage of a state of the art approach thanks to learning from observational location data, which allowed our method to reason about many more places.
The Security of Hardware-Based Omega(n^2) Cryptographic One-Way Functions: Beyond Satisfiability and P=NP
Venue: arXiv cs.CC 2016
Year: 2016

We present a class of hardware-based cryptographic one-way functions that, in practice, would be hard to invert even if P=NP and linear-time satisfiability algorithms exist. Such functions use a hardware-based component with omega(n^2) size circuits, and omega(n^2) run time.
Template Matching Advances and Applications in Image Analysis
Venue: arXiv cs.CV 2016
Year: 2016

In most computer vision and image analysis problems, it is necessary to define a similarity measure between two or more different objects or images. Template matching is a classic and fundamental method used to score similarities between objects using certain mathematical algorithms. In this paper, we reviewed the basic concept of matching, as well as advances in template matching and applications such as invariant features or novel applications in medical image analysis. Additionally, deformable models and templates originating from classic template matching were discussed. These models have broad applications in image registration, and they are a fundamental aspect of novel machine vision or deep learning algorithms, such as convolutional neural networks (CNN), which perform shift and scale invariant functions followed by classification. In general, although template matching methods have restrictions which limit their application, they are recommended for use with other object recognition methods as pre- or post-processing steps. Combining a template matching technique such as normalized cross-correlation or dice coefficient with a robust decision-making algorithm yields a significant improvement in the accuracy rate for object detection and recognition.
Toward Personalized Training and Skill Assessment in Robotic Minimally Invasive Surgery
Venue: arXiv cs.RO 2016
Year: 2016

Despite the immense technology advancement in the surgeries the criteria of assessing the surgical skills still remains based on subjective standards. With the advent of robotic-assisted surgery, new opportunities for objective and autonomous skill assessment is introduced. Previous works in this area are mostly based on structured-based method such as Hidden Markov Model (HMM) which need enormous pre-processing. In this study, in contrast with them, we develop a new shaped-based framework for automatically skill assessment and personalized surgical training with minimum parameter tuning. Our work has addressed main aspects of skill evaluation; develop gesture recognition model directly on temporal kinematic signal of robotic-assisted surgery, and build automated personalized RMIS gesture training framework which . We showed that our method, with an average accuracy of 82% for suturing, 70% for needle passing and 85% for knot tying, performs better or equal than the state-of-the-art methods, while simultaneously needs minimum pre-processing, parameter tuning and provides surgeons with online feedback for their performance during training.
Bridging Neural Machine Translation and Bilingual Dictionaries
Venue: arXiv cs.CL 2016
Year: 2016

Neural Machine Translation (NMT) has become the new state-of-the-art in several language pairs. However, it remains a challenging problem how to integrate NMT with a bilingual dictionary which mainly contains words rarely or never seen in the bilingual training data. In this paper, we propose two methods to bridge NMT and the bilingual dictionaries. The core idea behind is to design novel models that transform the bilingual dictionaries into adequate sentence pairs, so that NMT can distil latent bilingual mappings from the ample and repetitive phenomena. One method leverages a mixed word/character model and the other attempts at synthesizing parallel sentences guaranteeing massive occurrence of the translation lexicon. Extensive experiments demonstrate that the proposed methods can remarkably improve the translation quality, and most of the rare words in the test sentences can obtain correct translations if they are covered by the dictionary.
Filter-based regularisation for impulse response modelling
Venue: arXiv cs.SY 2016
Year: 2016

In the last years, the success of kernel-based regularisation techniques in solving impulse response modelling tasks has revived the interest on linear system identification. In this work, an alternative perspective on the same problem is introduced. Instead of relying on a Bayesian framework to include assumptions about the system in the definition of the covariance matrix of the parameters, here the prior knowledge is injected at the cost function level. The key idea is to define the regularisation matrix as a filtering operation on the parameters, which allows for a more intuitive formulation of the problem from an engineering point of view. Moreover, this results in a unified framework to model low-pass, band-pass and high-pass systems, and systems with one or more resonances. The proposed filter-based approach outperforms the existing regularisation method based on the TC and DC kernels, as illustrated by means of Monte Carlo simulations on several linear modelling examples.
Possibilities of Recursive GPU Mapping for Discrete Orthogonal Simplices
Venue: arXiv cs.DC 2016
Year: 2016

The problem of parallel thread mapping is studied for the case of discrete orthogonal $m$-simplices. The possibility of a $O(1)$ time recursive block-space map $λ: \mathbb{Z}^m \mapsto \mathbb{Z}^m$ is analyzed from the point of view of parallel space efficiency and potential performance improvement. The $2$-simplex and $3$-simplex are analyzed as special cases, where constant time maps are found, providing a potential improvement of up to $2\times$ and $6\times$ more efficient than a bounding-box approach, respectively. For the general case it is shown that finding an efficient recursive parallel space for an $m$-simplex depends of the choice of two parameters, for which some insights are provided which can lead to a volume that matches the $m$-simplex for $n>n_0$, making parallel space approximately $m!$ times more efficient than a bounding-box.
Measurement-Based Wideband Analysis of Dynamic Multipath Propagation in Vehicular Communication Scenarios
Venue: arXiv cs.NI 2016
Year: 2016

Realistic propagation modeling requires a detailed understanding and characterization of the radio channel properties. This paper is based on channel sounder measurements with 1 GHz bandwidth at a carrier frequency of 5.7 GHz and particular tracking methods. We present statistical models for the number of, birth rate, lifetime, excess delay and relative Doppler frequency of individual multipath components (MPCs). Our findings are concluded from 72 measurement runs in eight relevant vehicular communication scenarios and reveal wide insights into the dynamic propagation process in vehicular communication scenarios.
Virtual Embodiment: A Scalable Long-Term Strategy for Artificial Intelligence Research
Venue: arXiv cs.AI 2016
Year: 2016

Meaning has been called the "holy grail" of a variety of scientific disciplines, ranging from linguistics to philosophy, psychology and the neurosciences. The field of Artifical Intelligence (AI) is very much a part of that list: the development of sophisticated natural language semantics is a sine qua non for achieving a level of intelligence comparable to humans. Embodiment theories in cognitive science hold that human semantic representation depends on sensori-motor experience; the abundant evidence that human meaning representation is grounded in the perception of physical reality leads to the conclusion that meaning must depend on a fusion of multiple (perceptual) modalities. Despite this, AI research in general, and its subdisciplines such as computational linguistics and computer vision in particular, have focused primarily on tasks that involve a single modality. Here, we propose virtual embodiment as an alternative, long-term strategy for AI research that is multi-modal in nature and that allows for the kind of scalability required to develop the field coherently and incrementally, in an ethically responsible fashion.
An Attempt to Design a Better Algorithm for the Uncapacitated Facility Location Problem
Venue: arXiv cs.DS 2016
Year: 2016

The uncapacitated facility location has always been an important problem due to its connection to operational research and infrastructure planning. Byrka obtained an algorithm that is parametrized by $γ$ and proved that it is optimal when $γ>1.6774$. He also proved that the algorithm achieved an approximation ratio of 1.50. A later work by Shi Li achieved an approximation factor of 1.488. In this research, we studied these algorithms and several related works. Although we didn't improve upon the algorithm of Shi Li, our work did provide some insight into the problem. We also reframed the problem as a vector game, which provided a framework to design balanced algorithms for this problem.
A 481pJ/decision 3.4M decision/s Multifunctional Deep In-memory Inference Processor using Standard 6T SRAM Array
Venue: arXiv cs.AR 2016
Year: 2016

This paper describes a multi-functional deep in-memory processor for inference applications. Deep in-memory processing is achieved by embedding pitch-matched low-SNR analog processing into a standard 6T 16KB SRAM array in 65 nm CMOS. Four applications are demonstrated. The prototype achieves up to 5.6X (9.7X estimated for multi-bank scenario) energy savings with negligible (<1%) accuracy degradation in all four applications as compared to the conventional architecture.
Automatic and Manual Segmentation of Hippocampus in Epileptic Patients MRI
Venue: arXiv cs.CV 2016
Year: 2016

The hippocampus is a seminal structure in the most common surgically-treated form of epilepsy. Accurate segmentation of the hippocampus aids in establishing asymmetry regarding size and signal characteristics in order to disclose the likely site of epileptogenicity. With sufficient refinement, it may ultimately aid in the avoidance of invasive monitoring with its expense and risk for the patient. To this end, a reliable and consistent method for segmentation of the hippocampus from magnetic resonance imaging (MRI) is needed. In this work, we present a systematic and statistical analysis approach for evaluation of automated segmentation methods in order to establish one that reliably approximates the results achieved by manual tracing of the hippocampus.
A new content format for immersive experiences
Venue: arXiv cs.HC 2016
Year: 2016

The arrival of head-mounted displays (HMDs) to the consumer market requires a novel content format that is, first, adapted to the specificities of immersive displays and, second, that takes into account the current reality of multi-display media consumption. We review the requirements for such content format and report on existing initiatives, some of our own, towards implementing such content format.
Sparse Hierarchical Tucker Factorization and its Application to Healthcare
Venue: arXiv cs.LG 2016
Year: 2016

We propose a new tensor factorization method, called the Sparse Hierarchical-Tucker (Sparse H-Tucker), for sparse and high-order data tensors. Sparse H-Tucker is inspired by its namesake, the classical Hierarchical Tucker method, which aims to compute a tree-structured factorization of an input data set that may be readily interpreted by a domain expert. However, Sparse H-Tucker uses a nested sampling technique to overcome a key scalability problem in Hierarchical Tucker, which is the creation of an unwieldy intermediate dense core tensor; the result of our approach is a faster, more space-efficient, and more accurate method. We extensively test our method on a real healthcare dataset, which is collected from 30K patients and results in an 18th order sparse data tensor. Unlike competing methods, Sparse H-Tucker can analyze the full data set on a single multi-threaded machine. It can also do so more accurately and in less time than the state-of-the-art: on a 12th order subset of the input data, Sparse H-Tucker is 18x more accurate and 7.5x faster than a previously state-of-the-art method. Even for analyzing low order tensors (e.g., 4-order), our method requires close to an order of magnitude less time and over two orders of magnitude less memory, as compared to traditional tensor factorization methods such as CP and Tucker. Moreover, we observe that Sparse H-Tucker scales nearly linearly in the number of non-zero tensor elements. The resulting model also provides an interpretable disease hierarchy, which is confirmed by a clinical expert.
Matroidal Structure of Skew Polynomial Rings with Application to Network Coding
Venue: arXiv cs.IT 2016
Year: 2016

Over a finite field $\mathbb{F}_{q^m}$, the evaluation of skew polynomials is intimately related to the evaluation of linearized polynomials. This connection allows one to relate the concept of polynomial independence defined for skew polynomials to the familiar concept of linear independence for vector spaces. This relation allows for the definition of a representable matroid called the $\mathbb{F}_{q^m}[x;σ]$-matroid, with rank function that makes it a metric space. Specific submatroids of this matroid are individually bijectively isometric to the projective geometry of $\mathbb{F}_{q^m}$ equipped with the subspace metric. This isometry allows one to use the $\mathbb{F}_{q^m}[x;σ]$-matroid in a matroidal network coding application.
Online Event Integration with StoryPivot
Venue: arXiv cs.DB 2016
Year: 2016

Modern data integration systems need to process large amounts of data from a variety of data sources and with real-time integration constraints. They are not only employed in enterprises for managing internal data but are also used for a variety of web services that use techniques such as entity resolution or data cleaning in live systems. In this work, we discuss a new generation of data integration systems that operate on (un-)structured data in an online setting, i.e., systems which process continuously modified datasets upon which the integration task is based. We use as an example of such a system an online event integration system called StoryPivot. It observes events extracted from news articles in data sources such as the 'Guardian' or the 'Washington Post' which are integrated to show users the evolution of real-world stories over time. The design decisions for StoryPivot are influenced by the trade-off between maintaining high quality integration results while at the same time building a system that processes and integrates events in near real-time. We evaluate our design decisions with experiments on two real-world datasets and generalize our findings to other data integration tasks that have a similar system setup.
A parallel framework for reverse search using mts
Venue: arXiv cs.DC 2016
Year: 2016

We describe mts, which is a generic framework for parallelizing certain types of tree search programs, that (a) provides a single common wrapper containing all of the parallelization, and (b) minimizes the changes needed to the existing single processor legacy code. The mts code was derived from ideas used to develop mplrs, a parallelization of the reverse search vertex enumeration code lrs. The tree search properties required for the use of mts are satisfied by any reverse search algorithm as well as other tree search methods such as backtracking and branch and bound. mts is programmed in C, uses the MPI parallel environment, and can be run on a network of computers. As examples we parallelize two simple existing reverse search codes: generating topological orderings and generating spanning trees of a graph. We give computational results comparing the parallel codes with state of the art sequential codes for the same problems.
Big Models for Big Data using Multi objective averaged one dependence estimators
Venue: arXiv cs.NE 2016
Year: 2016

Even though, many researchers tried to explore the various possibilities on multi objective feature selection, still it is yet to be explored with best of its capabilities in data mining applications rather than going for developing new ones. In this paper, multi-objective evolutionary algorithm ENORA is used to select the features in a multi-class classification problem. The fusion of AnDE (averaged n-dependence estimators) with n=1, a variant of naive Bayes with efficient feature selection by ENORA is performed in order to obtain a fast hybrid classifier which can effectively learn from big data. This method aims at solving the problem of finding optimal feature subset from full data which at present still remains to be a difficult problem. The efficacy of the obtained classifier is extensively evaluated with a range of most popular 21 real world dataset, ranging from small to big. The results obtained are encouraging in terms of time, Root mean square error, zero-one loss and classification accuracy.