OpenRaiser/Intern-Atlas huggingface dataset:
PTAS for MAP Assignment on Pairwise Markov Random Fields in Planar Graphs
Venue: arXiv cs.DM 2015
Year: 2015

We present a PTAS for computing the maximum a posteriori assignment on Pairwise Markov Random Fields with non-negative weights in planar graphs. This algorithm is practical and not far behind state-of-the-art techniques in image processing. MAP on Pairwise Markov Random Fields with (possibly) negative weights cannot be approximated unless P = NP, even on planar graphs. We also show via reduction that this yields a PTAS for one scoring function of Correlation Clustering in planar graphs.
A Survey of P2P Network Security
Venue: arXiv cs.CR 2015
Year: 2015

This paper presents a review of peer-to-peer network security. Popular for sharing of multimedia files, these networks carry risks and vulnerabilities relating to data integrity, spyware, adware, and unwanted files. Further attacks include those of forgery, pollution, repudiation, membership and Eclipse attacks, neighbor selection attacks, Sybil, DoS, and omission attacks. We review some protection mechanisms that have been devised.
Preprint Big City 3D Visual Analysis
Venue: arXiv cs.GR 2015
Year: 2015

This is the preprint version of our paper on EUROGRAPHICS 2015. A big city visual analysis platform based on Web Virtual Reality Geographical Information System (WEBVRGIS) is presented. Extensive model editing functions and spatial analysis functions are available, including terrain analysis, spatial analysis, sunlight analysis, traffic analysis, population analysis and community analysis.
Knowledge driven Offline to Online Script Conversion
Venue: arXiv cs.CV 2015
Year: 2015

The problem of offline to online script conversion is a challenging and an ill-posed problem. The interest in offline to online conversion exists because there are a plethora of robust algorithms in online script literature which can not be used on offline scripts. In this paper, we propose a method, based on heuristics, to extract online script information from offline bitmap image. We show the performance of the proposed method on a real sample signature offline image, whose online information is known.
On-line Handwritten Devanagari Character Recognition using Fuzzy Directional Features
Venue: arXiv cs.CV 2015
Year: 2015

This paper describes a new feature set for use in the recognition of on-line handwritten Devanagari script based on Fuzzy Directional Features. Experiments are conducted for the automatic recognition of isolated handwritten character primitives (sub-character units). Initially we describe the proposed feature set, called the Fuzzy Directional Features (FDF) and then show how these features can be effectively utilized for writer independent character recognition. Experimental results show that FDF set perform well for writer independent data set at stroke level recognition. The main contribution of this paper is the introduction of a novel feature set and establish experimentally its ability in recognition of handwritten Devanagari script.
Voice based self help System: User Experience Vs Accuracy
Venue: arXiv cs.CL 2015
Year: 2015

In general, self help systems are being increasingly deployed by service based industries because they are capable of delivering better customer service and increasingly the switch is to voice based self help systems because they provide a natural interface for a human to interact with a machine. A speech based self help system ideally needs a speech recognition engine to convert spoken speech to text and in addition a language processing engine to take care of any misrecognitions by the speech recognition engine. Any off-the-shelf speech recognition engine is generally a combination of acoustic processing and speech grammar. While this is the norm, we believe that ideally a speech recognition application should have in addition to a speech recognition engine a separate language processing engine to give the system better performance. In this paper, we discuss ways in which the speech recognition engine and the language processing engine can be combined to give a better user experience.
Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability
Venue: arXiv cs.GT 2015
Year: 2015

We study $n$-player turn-based games played on a finite directed graph. For each play, the players have to pay a cost that they want to minimize. Instead of the well-known notion of Nash equilibrium (NE), we focus on the notion of subgame perfect equilibrium (SPE), a refinement of NE well-suited in the framework of games played on graphs. We also study natural variants of SPE, named weak (resp. very weak) SPE, where players who deviate cannot use the full class of strategies but only a subclass with a finite number of (resp. a unique) deviation step(s). Our results are threefold. Firstly, we characterize in the form of a Folk theorem the set of all plays that are the outcome of a weak SPE. Secondly, for the class of quantitative reachability games, we prove the existence of a finite-memory SPE and provide an algorithm for computing it (only existence was known with no information regarding the memory). Moreover, we show that the existence of a constrained SPE, i.e. an SPE such that each player pays a cost less than a given constant, can be decided. The proofs rely on our Folk theorem for weak SPEs (which coincide with SPEs in the case of quantitative reachability games) and on the decidability of MSO logic on infinite words. Finally with similar techniques, we provide a second general class of games for which the existence of a (constrained) weak SPE is decidable.
Modeling Spatial-Temporal Clues in a Hybrid Deep Learning Framework for Video Classification
Venue: arXiv cs.CV 2015
Year: 2015

Classifying videos according to content semantics is an important problem with a wide range of applications. In this paper, we propose a hybrid deep learning framework for video classification, which is able to model static spatial information, short-term motion, as well as long-term temporal clues in the videos. Specifically, the spatial and the short-term motion features are extracted separately by two Convolutional Neural Networks (CNN). These two types of CNN-based features are then combined in a regularized feature fusion network for classification, which is able to learn and utilize feature relationships for improved performance. In addition, Long Short Term Memory (LSTM) networks are applied on top of the two features to further model longer-term temporal clues. The main contribution of this work is the hybrid learning framework that can model several important aspects of the video data. We also show that (1) combining the spatial and the short-term motion features in the regularized fusion network is better than direct classification and fusion using the CNN with a softmax layer, and (2) the sequence-based LSTM is highly complementary to the traditional classification strategy without considering the temporal frame orders. Extensive experiments are conducted on two popular and challenging benchmarks, the UCF-101 Human Actions and the Columbia Consumer Videos (CCV). On both benchmarks, our framework achieves to-date the best reported performance: $91.3\%$ on the UCF-101 and $83.5\%$ on the CCV.
"How much?" Is Not Enough - An Analysis of Open Budget Initiatives
Venue: arXiv cs.CY 2015
Year: 2015

A worldwide movement towards the publication of Open Government Data is taking place, and budget data is one of the key elements pushing this trend. Its importance is mostly related to transparency, but publishing budget data, combined with other actions, can also improve democratic participation, allow comparative analysis of governments and boost data-driven business. However, the lack of standards and common evaluation criteria still hinders the development of appropriate tools and the materialization of the appointed benefits. In this paper, we present a model to analyse government initiatives to publish budget data. We identify the main features of these initiatives with a double objective: (i) to drive a structured analysis, relating some dimensions to their possible impacts, and (ii) to derive characterization attributes to compare initiatives based on each dimension. We define use perspectives and analyse some initiatives using this model. We conclude that, in order to favour use perspectives, special attention must be given to user feedback, semantics standards and linking possibilities.
Asymptotic behaviour of weighted differential entropies in a Bayesian problem
Venue: arXiv cs.IT 2015
Year: 2015

We consider a Bayesian problem of estimating of probability of success in a series of conditionally independent trials with binary outcomes. We study the asymptotic behaviour of differential entropy for posterior probability density function conditional on $x$ successes after $n$ conditionally independent trials, when $n \to \infty$. It is shown that after an appropriate normalization in cases $x \sim n$ and $x$ $\sim n^β$ ($0<β<1$) limiting distribution is Gaussian and the differential entropy of standardized RV converges to differential entropy of standard Gaussian random variable. When $x$ or $n-x$ is a constant the limiting distribution in not Gaussian, but still the asymptotic of differential entropy can be found explicitly. Then suppose that one is interested to know whether the coin is fair or not and for large $n$ is interested in the true frequency. To do so the concept of weighted differential entropy introduced in \cite{Belis1968} is used when the frequency $γ$ is necessary to emphasize. It was found that the weight in suggested form does not change the asymptotic form of Shannon, Renyi, Tsallis and Fisher entropies, but change the constants. The main term in weighted Fisher Information is changed by some constant which depend on distance between the true frequency and the value we want to emphasize. In third part we derived the weighted versions of Rao-Cramér, Bhattacharyya and Kullback inequalities. This result is applied to the Bayesian problem described above. The asymptotic forms of these inequalities are obtained for a particular class of weight functions.
Ego-Object Discovery
Venue: arXiv cs.CV 2015
Year: 2015

Lifelogging devices are spreading faster everyday. This growth can represent great benefits to develop methods for extraction of meaningful information about the user wearing the device and his/her environment. In this paper, we propose a semi-supervised strategy for easily discovering objects relevant to the person wearing a first-person camera. Given an egocentric video/images sequence acquired by the camera, our algorithm uses both the appearance extracted by means of a convolutional neural network and an object refill methodology that allows to discover objects even in case of small amount of object appearance in the collection of images. An SVM filtering strategy is applied to deal with the great part of the False Positive object candidates found by most of the state of the art object detectors. We validate our method on a new egocentric dataset of 4912 daily images acquired by 4 persons as well as on both PASCAL 2012 and MSRC datasets. We obtain for all of them results that largely outperform the state of the art approach. We make public both the EDUB dataset and the algorithm code.
Scheduling wireless links by graph multicoloring in the physical interference model
Venue: arXiv cs.NI 2015
Year: 2015

Scheduling wireless links for simultaneous activation in such a way that all transmissions are successfully decoded at the receivers and moreover network capacity is maximized is a computationally hard problem. Usually it is tackled by heuristics whose output is a sequence of time slots in which every link appears in exactly one time slot. Such approaches can be interpreted as the coloring of a graph's vertices so that every vertex gets exactly one color. Here we introduce a new approach that can be viewed as assigning multiple colors to each vertex, so that, in the resulting schedule, every link may appear more than once (though the same number of times for all links). We report on extensive computational experiments, under the physical interference model, revealing substantial gains for a variety of randomly generated networks.
Benchmarking the cost of thread divergence in CUDA
Venue: arXiv cs.DC 2015
Year: 2015

All modern processors include a set of vector instructions. While this gives a tremendous boost to the performance, it requires a vectorized code that can take advantage of such instructions. As an ideal vectorization is hard to achieve in practice, one has to decide when different instructions may be applied to different elements of the vector operand. This is especially important in implicit vectorization as in NVIDIA CUDA Single Instruction Multiple Threads (SIMT) model, where the vectorization details are hidden from the programmer. In order to assess the costs incurred by incompletely vectorized code, we have developed a micro-benchmark that measures the characteristics of the CUDA thread divergence model on different architectures focusing on the loops performance.
Garbage Collection Techniques for Flash-Resident Page-Mapping FTLs
Venue: arXiv cs.DB 2015
Year: 2015

Storage devices based on flash memory have replaced hard disk drives (HDDs) due to their superior performance, increasing density, and lower power consumption. Unfortunately, flash memory is subject to challenging idiosyncrasies like erase-before-write and limited block lifetime. These constraints are handled by a flash translation layer (FTL), which performs out-of-place updates, wear-leveling and garbage-collection behind the scene, while offering the application a virtualization of the physical address space. A class of relevant FTLs employ a flash-resident page-associative mapping table from logical to physical addresses, with a smaller RAM-resident cache for frequently mapped entries. In this paper, we address the problem of performing garbage-collection under such FTLs. We observe two problems. Firstly, maintaining the metadata needed to perform garbage-collection under these schemes is problematic, because at write-time we do not necessarily know the physical address of the before-image. Secondly, the size of this metadata must remain small, because it makes RAM unavailable for caching frequently accessed entries. We propose two complementary techniques, called Lazy Gecko and Logarithmic Gecko, which address these issues. Lazy Gecko works well when RAM is plentiful enough to store the GC metadata. Logarithmic Gecko works well when RAM isn't plentiful and efficiently stores the GC metadata in flash. Thus, these techniques are applicable to a wide range of flash devices with varying amounts of embedded RAM.
Spectral Graph Theoretic Analysis of Tsallis Entropy-based Dissimilarity Measure
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we introduce a nonextensive quantum information theoretic measure which may be defined between any arbitrary number of density matrices, and we analyze its fundamental properties in the spectral graph-theoretic framework. Unlike other entropic measures, the proposed quantum divergence is symmetric, matrix-convex, theoretically upper-bounded, and has the advantage of being generalizable to any arbitrary number of density matrices, with a possibility of assigning weights to these densities.
Autonomous CRM Control via CLV Approximation with Deep Reinforcement Learning in Discrete and Continuous Action Space
Venue: arXiv cs.LG 2015
Year: 2015

The paper outlines a framework for autonomous control of a CRM (customer relationship management) system. First, it explores how a modified version of the widely accepted Recency-Frequency-Monetary Value system of metrics can be used to define the state space of clients or donors. Second, it describes a procedure to determine the optimal direct marketing action in discrete and continuous action space for the given individual, based on his position in the state space. The procedure involves the use of model-free Q-learning to train a deep neural network that relates a client's position in the state space to rewards associated with possible marketing actions. The estimated value function over the client state space can be interpreted as customer lifetime value, and thus allows for a quick plug-in estimation of CLV for a given client. Experimental results are presented, based on KDD Cup 1998 mailing dataset of donation solicitations.
Location, location, location: Border effects in interference limited ad hoc networks
Venue: arXiv cs.NI 2015
Year: 2015

Wireless networks are fundamentally limited by the intensity of the received signals and by their inherent interference. It is shown here that in finite ad hoc networks where node placement is modelled according to a Poisson point process and no carrier sensing is employed for medium access, the SINR received by nodes located at the border of the network deployment/operation region is on average greater than the rest. This is primarily due to the uneven interference landscape of such networks which is particularly kind to border nodes giving rise to all sorts of performance inhomogeneities and access unfairness. Using tools from stochastic geometry we quantify these spatial variations and provide closed form communication-theoretic results showing why the receiver's location is so important.
Multihop connectivity of ad hoc networks with randomly oriented directional antennas
Venue: arXiv cs.NI 2015
Year: 2015

Directional antennas and beamforming can significantly improve point-to-point wireless links when perfectly aligned. In this letter we investigate the extreme opposite where antenna orientations and positions are chosen at random in the presence of Rayleigh fading. We show that while the 1-hop network connectivity is deteriorated, the multihop routes improve, especially in the dense regime. We derive closed form expressions for the expectation of the $1$-hop and $2$-hop degree which are verified through computer simulations. We conclude that node density does not greatly affect the number of hops required between stations whilst simple random beamforming schemes do, thus returning substantial network performance benefits due to the existence of shorter multi-hop paths.
Data Mining for Prediction of Human Performance Capability in the Software-Industry
Venue: arXiv cs.LG 2015
Year: 2015

The recruitment of new personnel is one of the most essential business processes which affect the quality of human capital within any company. It is highly essential for the companies to ensure the recruitment of right talent to maintain a competitive edge over the others in the market. However IT companies often face a problem while recruiting new people for their ongoing projects due to lack of a proper framework that defines a criteria for the selection process. In this paper we aim to develop a framework that would allow any project manager to take the right decision for selecting new talent by correlating performance parameters with the other domain-specific attributes of the candidates. Also, another important motivation behind this project is to check the validity of the selection procedure often followed by various big companies in both public and private sectors which focus only on academic scores, GPA/grades of students from colleges and other academic backgrounds. We test if such a decision will produce optimal results in the industry or is there a need for change that offers a more holistic approach to recruitment of new talent in the software companies. The scope of this work extends beyond the IT domain and a similar procedure can be adopted to develop a recruitment framework in other fields as well. Data-mining techniques provide useful information from the historical projects depending on which the hiring-manager can make decisions for recruiting high-quality workforce. This study aims to bridge this hiatus by developing a data-mining framework based on an ensemble-learning technique to refocus on the criteria for personnel selection. The results from this research clearly demonstrated that there is a need to refocus on the selection-criteria for quality objectives.
MOTChallenge 2015: Towards a Benchmark for Multi-Target Tracking
Venue: arXiv cs.CV 2015
Year: 2015

In the recent past, the computer vision community has developed centralized benchmarks for the performance evaluation of a variety of tasks, including generic object and pedestrian detection, 3D reconstruction, optical flow, single-object short-term tracking, and stereo estimation. Despite potential pitfalls of such benchmarks, they have proved to be extremely helpful to advance the state of the art in the respective area. Interestingly, there has been rather limited work on the standardization of quantitative benchmarks for multiple target tracking. One of the few exceptions is the well-known PETS dataset, targeted primarily at surveillance applications. Despite being widely used, it is often applied inconsistently, for example involving using different subsets of the available data, different ways of training the models, or differing evaluation scripts. This paper describes our work toward a novel multiple object tracking benchmark aimed to address such issues. We discuss the challenges of creating such a framework, collecting existing and new data, gathering state-of-the-art methods to be tested on the datasets, and finally creating a unified evaluation system. With MOTChallenge we aim to pave the way toward a unified evaluation framework for a more meaningful quantification of multi-target tracking.
A lower bound on the order of the largest induced forest in planar graphs with high girth
Venue: arXiv cs.DM 2015
Year: 2015

We give here new upper bounds on the size of a smallest feedback vertex set in planar graphs with high girth. In particular, we prove that a planar graph with girth $g$ and size $m$ has a feedback vertex set of size at most $\frac{4m}{3g}$, improving the trivial bound of $\frac{2m}{g}$. We also prove that every $2$-connected graph with maximum degree $3$ and order $n$ has a feedback vertex set of size at most $\frac{n+2}{3}$.
Supporting Language Learners with the Meanings Of Closed Class Items
Venue: arXiv cs.AI 2015
Year: 2015

The process of language learning involves the mastery of countless tasks: making the constituent sounds of the language being learned, learning the grammatical patterns, and acquiring the requisite vocabulary for reception and production. While a plethora of computational tools exist to facilitate the first and second of these tasks, a number of challenges arise with respect to enabling the third. This paper describes a tool that has been designed to support language learners with the challenge of understanding the use of closed-class lexical items. The process of learning the Arabic for office is (mktb) is relatively simple and should be possible by means of simple repetition of the word. However, it is much more difficult to learn and correctly use the Arabic equivalent of the word on. The current paper describes a mechanism for the delivery of diagnostic information regarding specific lexical examples, with the aim of clearly demonstrating why a particular translation of a given closed-class item may be appropriate in certain situations but not others, thereby helping learners to understand and use the term correctly.