OpenRaiser/Intern-Atlas huggingface dataset:
e-Distance Weighted Support Vector Regression
Venue: arXiv cs.LG 2016
Year: 2016

We propose a novel support vector regression approach called e-Distance Weighted Support Vector Regression (e-DWSVR).e-DWSVR specifically addresses two challenging issues in support vector regression: first, the process of noisy data; second, how to deal with the situation when the distribution of boundary data is different from that of the overall data. The proposed e-DWSVR optimizes the minimum margin and the mean of functional margin simultaneously to tackle these two issues. In addition, we use both dual coordinate descent (CD) and averaged stochastic gradient descent (ASGD) strategies to make e-DWSVR scalable to large scale problems. We report promising results obtained by e-DWSVR in comparison with existing methods on several benchmark datasets.
Edge Coloring with Minimum Reload/Changeover Costs
Venue: arXiv cs.DS 2016
Year: 2016

In an edge-colored graph, a traversal cost occurs at a vertex along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only on the colors of the traversed edges. This concept leads to two global cost measures, namely the \emph{reload cost} and the \emph{changeover cost}, that have been studied in the literature and have various applications in telecommunications, transportation networks, and energy distribution networks. Previous work focused on problems with an edge-colored graph being part of the input. In this paper, we formulate and focus on two pairs of problems that aim to find an edge coloring of a graph so as to minimize the reload and changeover costs. The first pair of problems aims to find a proper edge coloring so that the reload/changeover cost of a set of paths is minimized. The second pair of problems aim to find a proper edge coloring and a spanning tree so that the reload/changeover cost is minimized. We present several hardness results as well as polynomial-time solvable special cases.
An ensemble learning method for scene classification based on Hidden Markov Model image representation
Venue: arXiv cs.CV 2016
Year: 2016

Low level images representation in feature space performs poorly for classification with high accuracy since this level of representation is not able to project images into the discriminative feature space. In this work, we propose an efficient image representation model for classification. First we apply Hidden Markov Model (HMM) on ordered grids represented by different type of image descriptors in order to include causality of local properties existing in image for feature extraction and then we train up a separate classifier for each of these features sets. Finally we ensemble these classifiers efficiently in a way that they can cancel out each other errors for obtaining higher accuracy. This method is evaluated on 15 natural scene dataset. Experimental results show the superiority of the proposed method in comparison to some current existing methods
CFGs-2-NLU: Sequence-to-Sequence Learning for Mapping Utterances to Semantics and Pragmatics
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we present a novel approach to natural language understanding that utilizes context-free grammars (CFGs) in conjunction with sequence-to-sequence (seq2seq) deep learning. Specifically, we take a CFG authored to generate dialogue for our target application for NLU, a videogame, and train a long short-term memory (LSTM) recurrent neural network (RNN) to map the surface utterances that it produces to traces of the grammatical expansions that yielded them. Critically, this CFG was authored using a tool we have developed that supports arbitrary annotation of the nonterminal symbols in the grammar. Because we already annotated the symbols in this grammar for the semantic and pragmatic considerations that our game's dialogue manager operates over, we can use the grammatical trace associated with any surface utterance to infer such information. During gameplay, we translate player utterances into grammatical traces (using our RNN), collect the mark-up attributed to the symbols included in that trace, and pass this information to the dialogue manager, which updates the conversation state accordingly. From an offline evaluation task, we demonstrate that our trained RNN translates surface utterances to grammatical traces with great accuracy. To our knowledge, this is the first usage of seq2seq learning for conversational agents (our game's characters) who explicitly reason over semantic and pragmatic considerations.
A Human Computer Interaction Solution for Radiology Reporting: Evaluation of the Factors of Variation
Venue: arXiv cs.HC 2016
Year: 2016

The purpose of this research is to evaluate the human and technical factors required to create a human-computer interface (HCI) for a structured reporting solution based on eye-gaze and speech signals. Gaze and speech signals from radiologists acquired during simulated image interpretation and dictation sessions were analyzed to determine a) variation of temporal relationship between eye gaze and speech in a dictation environment, and b) variation in eye movements for a particular image interpretation task among radiologists. Knowledge of these factors provides information regarding the complexity of the image interpretation or dictation task, and provides information that can be used to design a HCI for use in diagnostic radiology. Our ultimate goal is to use these data to create an HCI to automate the generation of a particular type of structured radiology report. Our data indicate that the a) temporal relationships between eye gaze and speech and b) scan paths substantially vary among radiologists, thus implying that an HCI system based on eye gaze and speech for automating the capture of data for structured reporting processes should be customized for each user. The image resolution and layout, image content, and order of targets during an image interpretation session are not relevant factors to consider when designing an HCI. Our findings can be applied to the design of other HCI solutions for radiological applications that involve visual inspection and verbal descriptions of image findings.
Analysis of SINR Outage in Large-Scale Cellular Networks Using Campbell's Theorem and Cumulant Generating Functions
Venue: arXiv cs.IT 2016
Year: 2016

The signal-to-noise-plus-interference ratio (SINR) outage probability is one of the key performance parameters of a wireless cellular network, and its analytical as well as numerical evaluation has occupied many researchers. Recently, the introduction of stochastic geometric modeling of cellular networks has brought the outage problem to the forefront again. A popular and powerful approach is to exploit the available moment generating function (or Laplace transform) of received signal and interference, whenever it exists, by applying the Gil-Pelaez inversion formula. However, with the stochastic geometric modeling, the moment generating function may either be too complicated to exist in closed-form or at worst may not exist. Toward this end, in this paper, we study two alternate ways of evaluating the SINR outage. In the first case, we emphasize the significance of calculating cumulants over moments and exploit the fact that the cumulants of point processes are easily calculable using Campbell's theorem. The SINR outage is then analytically characterized by Charlier expansion based on Gaussian and Student's $t$-distributions and their associated Hermite and Krishnamoorthy polynomials. In the second case, we exploit the saddle point method, which gives a semi-analytical method of calculating the SINR outage, whenever the cumulant generating function of received signal and interference exists. For the purpose of demonstration, we apply these techniques on a downlink cellular network model where a typical user experiences a coordinated multi-point transmission, and the base stations are modeled by homogeneous Poisson point process. For the convenience of readers, we also provide a brief overview of moments, cumulants, their generating functions, and Campbell's theorem, without invoking measure theory. Numerical results illustrate the accuracy of the proposed mathematical approaches.
Sound Static Deadlock Analysis for C/Pthreads (Extended Version)
Venue: arXiv cs.PL 2016
Year: 2016

We present a static deadlock analysis approach for C/pthreads. The design of our method has been guided by the requirement to analyse real-world code. Our approach is sound (i.e., misses no deadlocks) for programs that have defined behaviour according to the C standard, and precise enough to prove deadlock-freedom for a large number of programs. The method consists of a pipeline of several analyses that build on a new context- and thread-sensitive abstract interpretation framework. We further present a lightweight dependency analysis to identify statements relevant to deadlock analysis and thus speed up the overall analysis. In our experimental evaluation, we succeeded to prove deadlock-freedom for 262 programs from the Debian GNU/Linux distribution with in total 2.6 MLOC in less than 11 hours.
Authorship attribution via network motifs identification
Venue: arXiv cs.CL 2016
Year: 2016

Concepts and methods of complex networks can be used to analyse texts at their different complexity levels. Examples of natural language processing (NLP) tasks studied via topological analysis of networks are keyword identification, automatic extractive summarization and authorship attribution. Even though a myriad of network measurements have been applied to study the authorship attribution problem, the use of motifs for text analysis has been restricted to a few works. The goal of this paper is to apply the concept of motifs, recurrent interconnection patterns, in the authorship attribution task. The absolute frequencies of all thirteen directed motifs with three nodes were extracted from the co-occurrence networks and used as classification features. The effectiveness of these features was verified with four machine learning methods. The results show that motifs are able to distinguish the writing style of different authors. In our best scenario, 57.5% of the books were correctly classified. The chance baseline for this problem is 12.5%. In addition, we have found that function words play an important role in these recurrent patterns. Taken together, our findings suggest that motifs should be further explored in other related linguistic tasks.
Kinematic-Layout-aware Random Forests for Depth-based Action Recognition
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we tackle the problem of 24 hours-monitoring patient actions in a ward such as "stretching an arm out of the bed", "falling out of the bed", where temporal movements are subtle or significant. In the concerned scenarios, the relations between scene layouts and body kinematics (skeletons) become important cues to recognize actions; however they are hard to be secured at a testing stage. To address this problem, we propose a kinematic-layout-aware random forest which takes into account the kinematic-layout (\ie layout and skeletons), to maximize the discriminative power of depth image appearance. We integrate the kinematic-layout in the split criteria of random forests to guide the learning process by 1) determining the switch to either the depth appearance or the kinematic-layout information, and 2) implicitly closing the gap between two distributions obtained by the kinematic-layout and the appearance, when the kinematic-layout appears useful. The kinematic-layout information is not required for the test data, thus called "privileged information prior". The proposed method has also been testified in cross-view settings, by the use of view-invariant features and enforcing the consistency among synthetic-view data. Experimental evaluations on our new dataset PATIENT, CAD-60 and UWA3D (multiview) demonstrate that our method outperforms various state-of-the-arts.
Interactive Learning from Multiple Noisy Labels
Venue: arXiv cs.LG 2016
Year: 2016

Interactive learning is a process in which a machine learning algorithm is provided with meaningful, well-chosen examples as opposed to randomly chosen examples typical in standard supervised learning. In this paper, we propose a new method for interactive learning from multiple noisy labels where we exploit the disagreement among annotators to quantify the easiness (or meaningfulness) of an example. We demonstrate the usefulness of this method in estimating the parameters of a latent variable classification model, and conduct experimental analyses on a range of synthetic and benchmark datasets. Furthermore, we theoretically analyze the performance of perceptron in this interactive learning framework.
Autonomous Ingress of a UAV through a window using Monocular Vision
Venue: arXiv cs.CV 2016
Year: 2016

The use of autonomous UAVs for surveillance purposes and other reconnaissance tasks is increasingly becoming popular and convenient.These tasks requires the ability to successfully ingress through the rectangular openings or windows of the target structure.In this paper, a method to robustly detect the window in the surrounding using basic image processing techniques and efficient distance measure, is proposed.Furthermore, a navigation scheme which incorporates this detection method for performing navigation task has also been proposed.The whole navigation task is performed and tested in the simulation environment GAZEBO.
On the edge capacitated Steiner tree problem
Venue: arXiv cs.DM 2016
Year: 2016

Given a graph G = (V,E) with a root r in V, positive capacities {c(e)|e in E}, and non-negative lengths {l(e)|e in E}, the minimum-length (rooted) edge capacitated Steiner tree problem is to find a tree in G of minimum total length, rooted at r, spanning a given subset T of vertices, and such that, for each e in E, there are at most c(e) paths, linking r to vertices in T, that contain e. We study the complexity and approximability of the problem, considering several relevant parameters such as the number of terminals, the edge lengths and the minimum and maximum edge capacities. For all but one combinations of assumptions regarding these parameters, we settle the question, giving a complete characterization that separates tractable cases from hard ones. The only remaining open case is proved to be equivalent to a long-standing open problem. We also prove close relations between our problem and classical Steiner tree as well as vertex-disjoint paths problems.
On the Hourglass Model
Venue: arXiv cs.NI 2016
Year: 2016

The hourglass model is a widely used as a means of describing the design of the Internet, and can be found in the introduction of many modern textbooks. It arguably also applies to the design of other successful spanning layers, notably the Unix operating system kernel interface, meaning the primitive system calls and the interactions between user processes and the kernel. The impressive success of the Internet has led to a wider interest in using the hourglass model in other layered systems, with the goal of achieving similar results. However, application of the hourglass model has often led to controversy, perhaps in part because the language in which it has been expressed has been informal, and arguments for its validity have not been precise. Making a start on formalizing such an argument is the goal of this paper.
Topological Interference Management with User Admission Control via Riemannian Optimization
Venue: arXiv cs.IT 2016
Year: 2016

Topological interference management (TIM) provides a promising way to manage interference only based on the network connectivity information. Previous works on the TIM problem mainly focus on using the index coding approach and graph theory to establish conditions of network topologies to achieve the feasibility of topological interference management. In this paper, we propose a novel user admission control approach via sparse and low-rank optimization to maximize the number of admitted users for achieving the feasibility of topological interference management. To assist efficient algorithms design for the formulated rank-constrained (i.e., degrees-of-freedom (DoF) allocation) l0-norm maximization (i.e., user capacity maximization) problem, we propose a regularized smoothed l1- norm minimization approach to induce sparsity pattern, thereby guiding the user selection. We further develop a Riemannian trust-region algorithm to solve the resulting rank-constrained smooth optimization problem via exploiting the quotient manifold of fixed-rank matrices. Simulation results demonstrate the effectiveness and near-optimal performance of the proposed Riemannian algorithm to maximize the number of admitted users for topological interference management.
A Statistical Test for Joint Distributions Equivalence
Venue: arXiv cs.LG 2016
Year: 2016

We provide a distribution-free test that can be used to determine whether any two joint distributions $p$ and $q$ are statistically different by inspection of a large enough set of samples. Following recent efforts from Long et al. [1], we rely on joint kernel distribution embedding to extend the kernel two-sample test of Gretton et al. [2] to the case of joint probability distributions. Our main result can be directly applied to verify if a dataset-shift has occurred between training and test distributions in a learning framework, without further assuming the shift has occurred only in the input, in the target or in the conditional distribution.
Validation of Information Fusion
Venue: arXiv cs.AI 2016
Year: 2016

We motivate and offer a formal definition of validation as it applies to information fusion systems. Common definitions of validation compare the actual state of the world with that derived by the fusion process. This definition conflates properties of the fusion system with properties of systems that intervene between the world and the fusion system. We propose an alternative definition where validation of an information fusion system references a standard fusion device, such as recognized human experts. We illustrate the approach by describing the validation process implemented in RAID, a program conducted by DARPA and focused on information fusion in adversarial, deceptive environments.
Seeing the Forest from the Trees in Two Looks: Matrix Sketching by Cascaded Bilateral Sampling
Venue: arXiv cs.LG 2016
Year: 2016

Matrix sketching is aimed at finding close approximations of a matrix by factors of much smaller dimensions, which has important applications in optimization and machine learning. Given a matrix A of size m by n, state-of-the-art randomized algorithms take O(m * n) time and space to obtain its low-rank decomposition. Although quite useful, the need to store or manipulate the entire matrix makes it a computational bottleneck for truly large and dense inputs. Can we sketch an m-by-n matrix in O(m + n) cost by accessing only a small fraction of its rows and columns, without knowing anything about the remaining data? In this paper, we propose the cascaded bilateral sampling (CABS) framework to solve this problem. We start from demonstrating how the approximation quality of bilateral matrix sketching depends on the encoding powers of sampling. In particular, the sampled rows and columns should correspond to the code-vectors in the ground truth decompositions. Motivated by this analysis, we propose to first generate a pilot-sketch using simple random sampling, and then pursue more advanced, "follow-up" sampling on the pilot-sketch factors seeking maximal encoding powers. In this cascading process, the rise of approximation quality is shown to be lower-bounded by the improvement of encoding powers in the follow-up sampling step, thus theoretically guarantees the algorithmic boosting property. Computationally, our framework only takes linear time and space, and at the same time its performance rivals the quality of state-of-the-art algorithms consuming a quadratic amount of resources. Empirical evaluations on benchmark data fully demonstrate the potential of our methods in large scale matrix sketching and related areas.
A Non-Parametric Control Chart For High Frequency Multivariate Data
Venue: arXiv cs.LG 2016
Year: 2016

Support Vector Data Description (SVDD) is a machine learning technique used for single class classification and outlier detection. SVDD based K-chart was first introduced by Sun and Tsung for monitoring multivariate processes when underlying distribution of process parameters or quality characteristics depart from Normality. The method first trains a SVDD model on data obtained from stable or in-control operations of the process to obtain a threshold $R^2$ and kernel center a. For each new observation, its Kernel distance from the Kernel center a is calculated. The kernel distance is compared against the threshold $R^2$ to determine if the observation is within the control limits. The non-parametric K-chart provides an attractive alternative to the traditional control charts such as the Hotelling's $T^2$ charts when distribution of the underlying multivariate data is either non-normal or is unknown. But there are challenges when K-chart is deployed in practice. The K-chart requires calculating kernel distance of each new observation but there are no guidelines on how to interpret the kernel distance plot and infer about shifts in process mean or changes in process variation. This limits the application of K-charts in big-data applications such as equipment health monitoring, where observations are generated at a very high frequency. In this scenario, the analyst using the K-chart is inundated with kernel distance results at a very high frequency, generally without any recourse for detecting presence of any assignable causes of variation. We propose a new SVDD based control chart, called as $K_T$ chart, which addresses challenges encountered when using K-chart for big-data applications. The $K_T$ charts can be used to simultaneously track process variation and central tendency. We illustrate the successful use of $K_T$ chart using the Tennessee Eastman process data.
Verso folio: Diversified Ranking for Large Graphs with Context-Aware Considerations
Venue: arXiv cs.IR 2016
Year: 2016

This work is pertaining to the diversified ranking of web-resources and interconnected documents that rely on a network-like structure, e.g. web-pages. A practical example of this would be a query for the k most relevant web-pages that are also in the same time as dissimilar with each other as possible. Relevance and dissimilarity are quantified using an aggregation of network distance and context similarity. For example, for a specific configuration of the problem, we might be interested in web-pages that are similar with the query in terms of their textual description but distant from each other in terms of the web-graph, e.g. many clicks away. In retrospect, a dearth of work can be found in the literature addressing this problem taking the network structure formed by the document links into consideration. In this work, we propose a hill-climbing approach that is seeded with a document collection which is generated using greedy heuristics to diversify initially. More importantly, we tackle the problem in the context of web-pages where there is an underlying network structure connecting the available documents and resources. This is a significant difference to the majority of works that tackle the problem in terms of either content definitions, or the graph structure of the data, but never addressing both aspects simultaneously. To the best of our knowledge, this is the very first effort that can be found to combine both aspects of this important problem in an elegant fashion by also allowing a great degree of flexibility on how to configure the trade-offs of (i) document relevance over result-items' dissimilarity, and (ii) network distance over content relevance or dissimilarity. Last but not least, we present an extensive evaluation of our methods that demonstrate the effectiveness and efficiency thereof.