OpenRaiser/Intern-Atlas huggingface dataset:
Semantic Image Based Geolocation Given a Map
Venue: arXiv cs.CV 2016
Year: 2016

The problem visual place recognition is commonly used strategy for localization. Most successful appearance based methods typically rely on a large database of views endowed with local or global image descriptors and strive to retrieve the views of the same location. The quality of the results is often affected by the density of the reference views and the robustness of the image representation with respect to viewpoint variations, clutter and seasonal changes. In this work we present an approach for geo-locating a novel view and determining camera location and orientation using a map and a sparse set of geo-tagged reference views. We propose a novel technique for detection and identification of building facades from geo-tagged reference view using the map and geometry of the building facades. We compute the likelihood of camera location and orientation of the query images using the detected landmark (building) identities from reference views, 2D map of the environment, and geometry of building facades. We evaluate our approach for building identification and geo-localization on a new challenging outdoors urban dataset exhibiting large variations in appearance and viewpoint.
State Estimation for Piecewise Affine State-Space Models
Venue: arXiv cs.SY 2016
Year: 2016

We propose a filter for piecewise affine state-space (PWASS) models. In each filtering recursion, the true filtering posterior distribution is a mixture of truncated normal distributions. The proposed filter approximates the mixture with a single normal distribution via moment matching. The proposed algorithm is compared with the extended Kalman filter (EKF) in a numerical simulation where the proposed method obtains, on average, better root mean square error (RMSE) than the EKF.
Label distribution based facial attractiveness computation by deep residual learning
Venue: arXiv cs.CV 2016
Year: 2016

Two challenges lie in the facial attractiveness computation research: the lack of true attractiveness labels (scores), and the lack of an accurate face representation. In order to address the first challenge, this paper recasts facial attractiveness computation as a label distribution learning (LDL) problem rather than a traditional single-label supervised learning task. In this way, the negative influence of the label incomplete problem can be reduced. Inspired by the recent promising work in face recognition using deep neural networks to learn effective features, the second challenge is expected to be solved from a deep learning point of view. A very deep residual network is utilized to enable automatic learning of hierarchical aesthetics representation. Integrating these two ideas, an end-to-end deep learning framework is established. Our approach achieves the best results on a standard benchmark SCUT-FBP dataset compared with other state-of-the-art work.
On Horizontal and Vertical Separation in Hierarchical Text Classification
Venue: arXiv cs.IR 2016
Year: 2016

Hierarchy is a common and effective way of organizing data and representing their relationships at different levels of abstraction. However, hierarchical data dependencies cause difficulties in the estimation of "separable" models that can distinguish between the entities in the hierarchy. Extracting separable models of hierarchical entities requires us to take their relative position into account and to consider the different types of dependencies in the hierarchy. In this paper, we present an investigation of the effect of separability in text-based entity classification and argue that in hierarchical classification, a separation property should be established between entities not only in the same layer, but also in different layers. Our main findings are the followings. First, we analyse the importance of separability on the data representation in the task of classification and based on that, we introduce a "Strong Separation Principle" for optimizing expected effectiveness of classifiers decision based on separation property. Second, we present Hierarchical Significant Words Language Models (HSWLM) which capture all, and only, the essential features of hierarchical entities according to their relative position in the hierarchy resulting in horizontally and vertically separable models. Third, we validate our claims on real-world data and demonstrate that how HSWLM improves the accuracy of classification and how it provides transferable models over time. Although discussions in this paper focus on the classification problem, the models are applicable to any information access tasks on data that has, or can be mapped to, a hierarchical structure.
Euclidean 1-center of a set of static and mobile points
Venue: arXiv cs.CG 2016
Year: 2016

In this paper, we consider the problem of computing the algebraic parametric equation of the Euclidean 1-center function in $\mathbb{R}^d$, $d \geq 2$, for a system of $n$ static points and $m$ mobile points having motion defined by rational parametric functions. We have shown that the corresponding Euclidean 1-center function is a piecewise differentiable function and have derived its exact parametric algebraic equation. If the positions of the static points and the rational parametric equations of the motion of the mobile points are given, we have proposed an algorithm that computes the parametric equation of the Euclidean 1-center function.
On unrooted and root-uncertain variants of several well-known phylogenetic network problems
Venue: arXiv cs.DS 2016
Year: 2016

The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an \emph{unrooted} phylogenetic network displays (i.e. embeds) an \emph{unrooted} phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the Tree Bisection and Reconnect (TBR) distance of the two unrooted trees. In the third part of the paper we consider the "root uncertain" variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees.
SynsetRank: Degree-adjusted Random Walk for Relation Identification
Venue: arXiv cs.CL 2016
Year: 2016

In relation extraction, a key process is to obtain good detectors that find relevant sentences describing the target relation. To minimize the necessity of labeled data for refining detectors, previous work successfully made use of BabelNet, a semantic graph structure expressing relationships between synsets, as side information or prior knowledge. The goal of this paper is to enhance the use of graph structure in the framework of random walk with a few adjustable parameters. Actually, a straightforward application of random walk degrades the performance even after parameter optimization. With the insight from this unsuccessful trial, we propose SynsetRank, which adjusts the initial probability so that high degree nodes influence the neighbors as strong as low degree nodes. In our experiment on 13 relations in the FB15K-237 dataset, SynsetRank significantly outperforms baselines and the plain random walk approach.
Transparent Clouds: An Enhancement to Abstraction
Venue: arXiv cs.NI 2016
Year: 2016

With the introduction of various hardware/software technologies such as Cloud Technologies or Virtualization technologies, there has been a great potential to reuse ICT artifacts thanks to Abstraction and also Exchangeability features achieved via these technologies. These technologies also provide various advantages with respect to sustainability including resource consumption reduction (in the use phase only or in the whole life cycle). However, there is an additional but untapped potential associated with the anonymization of resources introduced by both abstraction and exchangeability features. By realizing on this potential, we can improve cloud solutions and reduce their by-product opacity, which usually prevents leveraging on the specialized but tweakable (i.e., nonessential modifications without changing the main function) features of components that are captured in the component models. This is especially a challenge in the case heterogeneous/disaggregated infrastructure where developing models to cover everything is practically impossible. In this work, by leveraging on the concept of pathways, we develop a few mechanisms that enable transparency and therefore tweakability of features even in the presence of abstraction and heterogeneity. In particular, the layered-stack approach to system decomposition is considered because of its role in both software defined networking (SDN) and Network Function Virtualization (NFV) system decompositions. For a concrete example, the case of dynamic frequency scaling of processors is considered and it is shown that the associated consumption could be considerably reduced without requiring additional changes to the middle components.
Predicting Signed Edges with $O(n^{1+o(1)} \log{n})$ Queries
Venue: arXiv cs.DS 2016
Year: 2016

Social networks and interactions in social media involve both positive and negative relationships. Signed graphs capture both types of relationships: positive edges correspond to pairs of "friends", and negative edges to pairs of "foes". The {\em edge sign prediction problem}, which aims to predict whether an interaction between a pair of nodes will be positive or negative, is an important graph mining task for which many heuristics have recently been proposed \cite{leskovec2010predicting,leskovec2010signed}. Motivated by social balance theory, we model the edge sign prediction problem as a noisy correlation clustering problem with two clusters. We are allowed to query each pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability $0<q<\frac{1}{2}$. Let $c=\frac{1}{2}-q$ be the gap. We provide an algorithm that recovers the clustering with high probability in the presence of noise for any constant gap $c$ with $O(n^{1+\tfrac{1}{\log\log{n}}}\log{n})$ queries. Our algorithm uses simple breadth first search as its main algorithmic primitive. Finally, we provide a novel generalization to $k \geq 3$ clusters and prove that our techniques can recover the clustering if the gap is constant in this generalized setting.
Algorithms for Visualizing Phylogenetic Networks
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of visualizing phylogenetic networks, which are extensions of the Tree of Life in biology. We use a space filling visualization method, called DAGmaps, in order to obtain clear visualizations using limited space. In this paper, we restrict our attention to galled trees and galled networks and present linear time algorithms for visualizing them as DAGmaps.
Scalable Betweenness Centrality Maximization via Sampling
Venue: arXiv cs.SI 2016
Year: 2016

Betweenness centrality is a fundamental centrality measure in social network analysis. Given a large-scale network, how can we find the most central nodes? This question is of key importance to numerous important applications that rely on betweenness centrality, including community detection and understanding graph vulnerability. Despite the large amount of work on designing scalable approximation algorithms for betweenness centrality, estimating it on large-scale networks remains a computational challenge. In this paper, we study the Betweenness Centrality Maximization problem: given a graph $G=(V,E)$ and a positive integer $k$, find a set $S^* \subseteq V$ that maximizes betweenness centrality subject to the cardinality constraint $|S^*| \leq k$. We present an efficient randomized algorithm that provides a $(1-1/e-ε)$-approximation with high probability, where $ε>0$. Our results improve the current state-of-the-art result by Yoshida~\cite{yoshida2014almost}. Furthermore, we provide theoretical evidence for the validity of a crucial assumption in the literature of betweenness centrality estimation, namely that in real-world networks $O(|V|^2)$ shortest paths pass through the top-$k$ central nodes, where $k$ is a constant. On the experimental side, we perform an extensive experimental analysis of our method on real-world networks, demonstrate its accuracy and scalability, and study different properties of central nodes. Finally, we provide three graph mining applications of our method.
Information Measures, Inequalities and Performance Bounds for Parameter Estimation in Impulsive Noise Environments
Venue: arXiv cs.IT 2016
Year: 2016

Recent studies found that many channels are affected by additive noise that is impulsive in nature and is best explained by heavy-tailed symmetric alpha-stable distributions. Dealing with impulsive noise environments comes with an added complexity with respect to the standard Gaussian environment: the alpha-stable probability density functions have an infinite second moment and the "nice" Hilbert space structure of the space of random variables having a finite second moment is lost along with its tools and methodologies. This is indeed the case in estimation theory where classical tools to quantify performance of an estimator are tightly related to the assumption of finite variance variables. In alpha-stable environments, expressions such as the mean square error and the Cramer-Rao bound are hence problematic. In this work, we tackle the parameter estimation problem in impulsive noise environments and develop novel tools that are tailored to the alpha-stable and heavy-tailed noise environments, tools that coincide with the standard ones adopted in the Gaussian setup, namely a generalized "power" measure and a generalized Fisher information. We generalize known information inequalities commonly used in the Gaussian context: the de Bruijn's identity, the data processing inequality, the Fisher information inequality, the isoperimetric inequality for entropies and the Cramer-Rao bound. Additionally, we derive upper bounds on the differential entropy of independent sums having a stable component. Finally, the new "power" measure is used to shed some light on the additive alpha-stable noise channel capacity in a setup that generalizes the linear average power constrained AWGN channel. Our theoretical findings are paralleled with numerical evaluations of various quantities and bounds using developed {\em Matlab} packages.
Compatible and Usable Mandatory Access Control for Good-enough OS Security
Venue: arXiv cs.OS 2016
Year: 2016

OS compromise is one of the most serious computer security problems today, but still not being resolved. Although people proposed different kinds of methods, they could not be accepted by most users who are non-expert due to the lack of compatibility and usability. In this paper, we introduce a kind of new mandatory access control model, named CUMAC, that aims to achieve good-enough security, high compatibility and usability. It has two novel features. One is access control based on tracing potential intrusion that can reduce false negatives and facilitate security configuration, in order to improve both compatibility and usability; the other is automatically figuring out all of the compatibility exceptions that usually incurs incompatible problems. The experiments performed on the prototype show that CUMAC can defense attacks from network, mobile disk and local untrustable users while keeping good compatibility and usability.
A Probabilistic Optimum-Path Forest Classifier for Binary Classification Problems
Venue: arXiv cs.CV 2016
Year: 2016

Probabilistic-driven classification techniques extend the role of traditional approaches that output labels (usually integer numbers) only. Such techniques are more fruitful when dealing with problems where one is not interested in recognition/identification only, but also into monitoring the behavior of consumers and/or machines, for instance. Therefore, by means of probability estimates, one can take decisions to work better in a number of scenarios. In this paper, we propose a probabilistic-based Optimum Path Forest (OPF) classifier to handle with binary classification problems, and we show it can be more accurate than naive OPF in a number of datasets. In addition to being just more accurate or not, probabilistic OPF turns to be another useful tool to the scientific community.
Automated Mutual Explicit Induction Proof in Separation Logic
Venue: arXiv cs.LO 2016
Year: 2016

We present a sequent-based deductive system for automatically proving entailments in separation logic by using mathematical induction. Our technique, called mutual explicit induction proof, is an instance of Noetherian induction. Specifically, we propose a novel induction principle on a well-founded relation of separation logic model and follow the explicit induction methods to implement this principle as inference rules, so that it can be easily integrated into a deductive system. We also support mutual induction, a natural feature of implicit induction, where the goal entailment and other entailments derived during the proof search can be used as hypotheses to prove each other. We have implemented a prototype prover and evaluated it on a benchmark of handcrafted entailments as well as benchmarks from a separation logic competition.
A data mining-based solution for detecting suspicious money laundering cases in an investment bank
Venue: arXiv cs.DB 2016
Year: 2016

Today, money laundering poses a serious threat not only to financial institutions but also to the nation. This criminal activity is becoming more and more sophisticated and seems to have moved from the clichy of drug trafficking to financing terrorism and surely not forgetting personal gain. Most international financial institutions have been implementing anti-money laundering solutions to fight investment fraud. However, traditional investigative techniques consume numerous man-hours. Recently, data mining approaches have been developed and are considered as well-suited techniques for detecting money laundering activities. Within the scope of a collaboration project for the purpose of developing a new solution for the anti-money laundering Units in an international investment bank, we proposed a simple and efficient data mining-based solution for anti-money laundering. In this paper, we present this solution developed as a tool and show some preliminary experiment results with real transaction datasets.
Sparse recovery in Wigner-D basis expansion
Venue: arXiv cs.IT 2016
Year: 2016

We are concerned with the recovery of $s-$sparse Wigner-D expansions in terms of $N$ Wigner-D functions. Considered as a generalization of spherical harmonics, Wigner-D functions are eigenfunctions of Laplace-Beltrami operator and form an orthonormal system. However, since they are not uniformly bounded, the existing results on BOS do not apply. Using previously introduced preconditioning technique, a new orthonormal and bounded system is obtained for which RIP property can be established. We show that the number of sufficient samples for sparse recovery scales with ${N}^{1/6} \,s\, \log^3(s) \,\log(N)$. The phase transition diagram for this problem is also presented. We will also discuss the application of our results in the spherical near-field antenna measurement.
Sliding Window Spectrum Sensing for Full-Duplex Cognitive Radios with Low Access-Latency
Venue: arXiv cs.IT 2016
Year: 2016

In a cognitive radio system the failure of secondary user (SU) transceivers to promptly vacate the channel can introduce significant access-latency for primary or high-priority users (PU). In conventional cognitive radio systems, the backoff latency is exacerbated by frame structures that only allow sensing at periodic intervals. Concurrent transmission and sensing using self-interference suppression has been suggested to improve the performance of cognitive radio systems, allowing decisions to be taken at multiple points within the frame. In this paper, we extend this approach by proposing a sliding-window full-duplex model allowing decisions to be taken on a sample-by-sample basis. We also derive the access-latency for both the existing and the proposed schemes. Our results show that the access-latency of the sliding scheme is decreased by a factor of 2.6 compared to the existing slotted full-duplex scheme and by a factor of approximately 16 compared to a half-duplex cognitive radio system. Moreover, the proposed scheme is significantly more resilient to the destructive effects of residual self-interference compared to previous approaches.
The Player Kernel: Learning Team Strengths Based on Implicit Player Contributions
Venue: arXiv cs.LG 2016
Year: 2016

In this work, we draw attention to a connection between skill-based models of game outcomes and Gaussian process classification models. The Gaussian process perspective enables a) a principled way of dealing with uncertainty and b) rich models, specified through kernel functions. Using this connection, we tackle the problem of predicting outcomes of football matches between national teams. We develop a player kernel that relates any two football matches through the players lined up on the field. This makes it possible to share knowledge gained from observing matches between clubs (available in large quantities) and matches between national teams (available only in limited quantities). We evaluate our approach on the Euro 2008, 2012 and 2016 final tournaments.
Un caso de big data punta a punta: análisis de datos de transporte y su uso en el negocio
Venue: arXiv cs.CY 2016
Year: 2016

In this article we present the results of a data analysis project for a public-transport company. This project encompassed data preparation, analysis and visualization of three years of historical data. The data consisted in ticket purchases and GPS location of the vehicles. This work describes the project from start to end, including the incorporation of the results in the business process.
Análisis de resultados electorales: comparación de métodos y estimación de votos por franja etaria
Venue: arXiv cs.CY 2016
Year: 2016

The State and its citizens generate lots of data. Once stored and processed, data can help resolve questions in Social Sciences, where it is common to need data in a different level of aggregation than the data is presented. In election results, we would like to understand the decision of each voter or group of voters, but the data is only available at the polling-place level. This problem is known as ecological inference. In this work we compare two methods to estimate the share of votes for each party according to different age groups. This work is complemented with the analysis of votes between the first and second rounds, as well as a referendum during the first. This analysis was performed on the 2014 uruguayan presidential elections.
Involutions, Trace Maps, and Pseudorandom Numbers
Venue: arXiv cs.IT 2016
Year: 2016

Interesting properties of the partitions of a finite field $\mathbb F_q$ induced by the combination of involutions and trace maps are studied. The special features of involutions of the form $\frac{u}{z}$, $u$ being a fixed element of $\mathbb F_q$, are exploited to generate pseudorandom numbers, the randomness resting on the uniform distribution of the images of zero-trace elements among the sets of non-zero trace elements of $\mathbb F_q$.