OpenRaiser/Intern-Atlas huggingface dataset:
Selection of Input Primitives for the Generalized Label Correcting Method
Venue: arXiv cs.RO 2016
Year: 2016

The generalized label correcting method is an efficient search-based approach to trajectory optimization. It relies on a finite set of control primitives that are concatenated into candidate control signals. This paper investigates the principled selection of this set of control primitives. Emphasis is placed on a particularly challenging input space geometry, the $n$-dimensional sphere. We propose using controls which minimize a generalized energy function and discuss the optimization technique used to obtain these control primitives. A numerical experiment is presented showing a factor of two improvement in running time when using the optimized control primitives over a random sampling strategy.
An Ensemble Blocking Scheme for Entity Resolution of Large and Sparse Datasets
Venue: arXiv cs.AI 2016
Year: 2016

Entity Resolution, also called record linkage or deduplication, refers to the process of identifying and merging duplicate versions of the same entity into a unified representation. The standard practice is to use a Rule based or Machine Learning based model that compares entity pairs and assigns a score to represent the pairs' Match/Non-Match status. However, performing an exhaustive pair-wise comparison on all pairs of records leads to quadratic matcher complexity and hence a Blocking step is performed before the Matching to group similar entities into smaller blocks that the matcher can then examine exhaustively. Several blocking schemes have been developed to efficiently and effectively block the input dataset into manageable groups. At CareerBuilder (CB), we perform deduplication on massive datasets of people profiles collected from disparate sources with varying informational content. We observed that, employing a single blocking technique did not cover the base for all possible scenarios due to the multi-faceted nature of our data sources. In this paper, we describe our ensemble approach to blocking that combines two different blocking techniques to leverage their respective strengths.
Thirteen Years of Mining Software Repositories (MSR) Conference - What is the Bibliography Data Telling Us?
Venue: arXiv cs.SE 2016
Year: 2016

The Mining Software Repositories (MSR) conference is a reputed, long-running and flagship conference in the area of Software Analytics which has successfully completed more than one decade as of year 2016. We conduct a bibliometric and scientific publication mining based study to study how the conference has evolved over the recent past 13 years (from 2004 to 2007 as a workshop and then from 2008 to 2016 as a conference). Our objective is to perform an examination of the state of MSR so that the MSR community can identify strengths, areas of improvements and future directions for the conference.
Nested Words for Order-2 Pushdown Systems
Venue: arXiv cs.FL 2016
Year: 2016

We study linear time model checking of collapsible higher-order pushdown systems (CPDS) of order 2 (manipulating stack of stacks) against MSO and PDL (propositional dynamic logic with converse and loop) enhanced with push/pop matching relations. To capture these linear time behaviours with matchings, we propose order-2 nested words. These graphs consist of a word structure augmented with two binary matching relations, one for each order of stack, which relate a push with matching pops (or collapse) on the respective stack. Due to the matching relations, satisfiability and model checking are undecidable. Hence we propose an under-approximation, bounding the number of times an order-1 push can be popped. With this under-approximation, which still allows unbounded stack height, we get decidability for satisfiability and model checking of both MSO and PDL. The problems are ExpTime-Complete for PDL.
A Generalization of the Łoś-Tarski Preservation Theorem
Venue: arXiv cs.LO 2016
Year: 2016

In this dissertation, we present for each natural number $k$, semantic characterizations of the $\exists^k \forall^*$ and $\forall^k \exists^*$ prefix classes of first order logic sentences, over all structures finite and infinite. This result, that we call the *generalized Łoś-Tarski theorem*, abbreviated $\mathsf{GLT}(k)$, yields the classical Łoś-Tarski preservation theorem when $k$ equals 0. It also provides new characterizations of the $Σ^0_2$ and $Π^0_2$ prefix classes, that are finer than all characterizations of these classes in the literature. Further, our semantic notions are finitary in nature, in contrast to those contained in the literature characterizations. In the context of finite structures, we formulate an abstract combinatorial property of structures, that when satisfied by a class, ensures that $\mathsf{GLT}(k)$ holds over the class. This property, that we call the *Equivalent Bounded Substructure Property*, abbreviated $\mathsf{EBSP}$, intuitively states that a large structure contains a small "logically similar" substructure. It turns out that this simply stated property is enjoyed by a variety of classes of interest in computer science: examples include words, trees (unordered, ordered or ranked), nested words, graph classes of bounded tree-depth/shrub-depth, and $m$-partite cographs. Further, $\mathsf{EBSP}$ remains preserved under various well-studied operations, such as complementation, transpose, the line-graph operation, disjoint union, cartesian and tensor products, etc. This enables constructing a wide spectrum of classes that satisfy $\mathsf{EBSP}$, and hence $\mathsf{GLT}(k)$. Remarkably, $\mathsf{EBSP}$ can be regarded as a finitary analogue of the classical downward Löwenheim-Skolem property. In summary, this dissertation provides new notions and results in both contexts, that of all structures and that of finite structures.
Automated Visual Fin Identification of Individual Great White Sharks
Venue: arXiv cs.CV 2016
Year: 2016

This paper discusses the automated visual identification of individual great white sharks from dorsal fin imagery. We propose a computer vision photo ID system and report recognition results over a database of thousands of unconstrained fin images. To the best of our knowledge this line of work establishes the first fully automated contour-based visual ID system in the field of animal biometrics. The approach put forward appreciates shark fins as textureless, flexible and partially occluded objects with an individually characteristic shape. In order to recover animal identities from an image we first introduce an open contour stroke model, which extends multi-scale region segmentation to achieve robust fin detection. Secondly, we show that combinatorial, scale-space selective fingerprinting can successfully encode fin individuality. We then measure the species-specific distribution of visual individuality along the fin contour via an embedding into a global `fin space'. Exploiting this domain, we finally propose a non-linear model for individual animal recognition and combine all approaches into a fine-grained multi-instance framework. We provide a system evaluation, compare results to prior work, and report performance and properties in detail.
Entwicklung eines Reputationssystems für cyber-physikalische Systeme am Beispiel des inHMotion Forschungsprojektes
Venue: arXiv cs.CR 2016
Year: 2016

Through the continued progress and advances of networking technology and also through efforts like Industry 4.0, SmartGrid, SmartCities, systems, that have been self-sustaining for the most part are now forming networked Cyber-physical Systems (CPS). Networking does not only have undoubtely benefits but also increase the often overlooked attack surface of these systems. A basic problem in information technology systems is building and sustaining trust. This work looks at the usage of reputation systems in the field of CPS and whether they could be used to assert the trustworthyness of communication partners. This is done in context of a research project inHMotion of the University of applied Sciences Munich, which is in the field of Intelligent Transportation Systems (ITS). A risk based analysis is performed for this project. Based on solicited threats mitigations are proposed. A possible solution might be the usage of a reputation system, which is designed and a prototype implementation for a simulation ist done. The concept of a meta reputation system, which combines different reputation systems and verification systems can achieve promising results in a simple simulation. In a concluding discussion criticism and possible improvements are given.
A Theory of Interactive Debugging of Knowledge Bases in Monotonic Logics
Venue: arXiv cs.AI 2016
Year: 2016

A broad variety of knowledge-based applications such as recommender, expert, planning or configuration systems usually operate on the basis of knowledge represented by means of some logical language. Such a logical knowledge base (KB) enables intelligent behavior of such systems by allowing them to automatically reason, answer queries of interest or solve complex real-world problems. Nowadays, where information acquisition comes at low costs and often happens automatically, the applied KBs are continuously growing in terms of size, information content and complexity. These developments foster the emergence of errors in these KBs and thus pose a significant challenge on all people and tools involved in KB evolution, maintenance and application. If some minimal quality criteria such as logical consistency are not met by some KB, it becomes useless for knowledge-based applications. To guarantee the compliance of KBs with given requirements, (non-interactive) KB debuggers have been proposed. These however often cannot localize all potential faults, suggest too large or incorrect modifications of the faulty KB or suffer from poor scalability due to the inherent complexity of the KB debugging problem. As a remedy to these issues, based on a well-founded theoretical basis this work proposes complete, sound and optimal methods for the interactive debugging of KBs that suggest the one (minimally invasive) error correction of the faulty KB that yields a repaired KB with exactly the intended semantics. Users, e.g. domain experts, are involved in the debugging process by answering automatically generated queries whether some given statements must or must not hold in the domain that should be modeled by the problematic KB at hand.
Global Caching for the Alternation-free $μ$-Calculus
Venue: arXiv cs.LO 2016
Year: 2016

We present a sound, complete, and optimal single-pass tableau algorithm for the alternation-free $μ$-calculus. The algorithm supports global caching with intermediate propagation and runs in time $2^{\mathcal{O}(n)}$. In game-theoretic terms, our algorithm integrates the steps for constructing and solving the Büchi game arising from the input tableau into a single procedure; this is done on-the-fly, i.e. may terminate before the game has been fully constructed. This suggests a slogan to the effect that global caching = game solving on-the-fly. A prototypical implementation shows promising initial results.
Polar Coding for Empirical Coordination of Signals and Actions over Noisy Channels
Venue: arXiv cs.IT 2016
Year: 2016

-We develop a polar coding scheme for empirical coordination in a two-node network with a noisy link in which the input and output signals have to be coordinated with the source and the reconstruction. In the case of non-causal encoding and decoding, we show that polar codes achieve the best known inner bound for the empirical coordination region, provided that a vanishing rate of common randomness is available. This scheme provides a constructive alternative to random binning and coding proofs.
Partial Least Squares Regression on Riemannian Manifolds and Its Application in Classifications
Venue: arXiv cs.CV 2016
Year: 2016

Partial least squares regression (PLSR) has been a popular technique to explore the linear relationship between two datasets. However, most of algorithm implementations of PLSR may only achieve a suboptimal solution through an optimization on the Euclidean space. In this paper, we propose several novel PLSR models on Riemannian manifolds and develop optimization algorithms based on Riemannian geometry of manifolds. This algorithm can calculate all the factors of PLSR globally to avoid suboptimal solutions. In a number of experiments, we have demonstrated the benefits of applying the proposed model and algorithm to a variety of learning tasks in pattern recognition and object classification.
Controlling rigid formations of mobile agents under inconsistent measurements
Venue: arXiv cs.RO 2016
Year: 2016

Despite the great success of using gradient-based controllers to stabilize rigid formations of autonomous agents in the past years, surprising yet intriguing undesirable collective motions have been reported recently when inconsistent measurements are used in the agents' local controllers. To make the existing gradient control robust against such measurement inconsistency, we exploit local estimators following the well known internal model principle for robust output regulation control. The new estimator-based gradient control is still distributed in nature and can be constructed systematically even when the number of agents in a rigid formation grows. We prove rigorously that the proposed control is able to guarantee exponential convergence and then demonstrate through robotic experiments and computer simulations that the reported inconsistency-induced orbits of collective movements are effectively eliminated.
Detecting facial landmarks in the video based on a hybrid framework
Venue: arXiv cs.CV 2016
Year: 2016

To dynamically detect the facial landmarks in the video, we propose a novel hybrid framework termed as detection-tracking-detection (DTD). First, the face bounding box is achieved from the first frame of the video sequence based on a traditional face detection method. Then, a landmark detector detects the facial landmarks, which is based on a cascaded deep convolution neural network (DCNN). Next, the face bounding box in the current frame is estimated and validated after the facial landmarks in the previous frame are tracked based on the median flow. Finally, the facial landmarks in the current frame are exactly detected from the validated face bounding box via the landmark detector. Experimental results indicate that the proposed framework can detect the facial landmarks in the video sequence more effectively and with lower consuming time compared to the frame-by-frame method via the DCNN.
Minimizing Compression Artifacts for High Resolutions with Adaptive Quantization Matrices for HEVC
Venue: arXiv cs.MM 2016
Year: 2016

Visual Display Units (VDUs), capable of displaying video data at High Definition (HD) and Ultra HD (UHD) resolutions, are frequently employed in a variety of technological domains. Quantization-induced video compression artifacts, which are usually unnoticeable in low resolution environments, are typically conspicuous on high resolution VDUs and video data. The default quantization matrices (QMs) in HEVC do not take into account specific display resolutions of VDUs or video data to determine the appropriate levels of quantization required to reduce unwanted compression artifacts. Therefore, we propose a novel, adaptive quantization matrix technique for the HEVC standard including Scalable HEVC (SHVC). Our technique, which is based on a refinement of the current QM technique in HEVC, takes into consideration specific display resolutions of the target VDUs in order to minimize compression artifacts. We undertake a thorough evaluation of the proposed technique by utilizing SHVC SHM 9.0 (two-layered bit-stream) and the BD-Rate and SSIM metrics. For the BD-Rate evaluation, the proposed method achieves maximum BD-Rate reductions of 56.5% in the enhancement layer. For the SSIM evaluation, our technique achieves a maximum structural improvement of 0.8660 vs. 0.8538.
Multi-View Constraint Propagation with Consensus Prior Knowledge
Venue: arXiv cs.CV 2016
Year: 2016

In many applications, the pairwise constraint is a kind of weaker supervisory information which can be collected easily. The constraint propagation has been proved to be a success of exploiting such side-information. In recent years, some methods of multi-view constraint propagation have been proposed. However, the problem of reasonably fusing different views remains unaddressed. In this paper, we present a method dubbed Consensus Prior Constraint Propagation (CPCP), which can provide the prior knowledge of the robustness of each data instance and its neighborhood. With the robustness generated from the consensus information of each view, we build a unified affinity matrix as a result of the propagation. Specifically, we fuse the affinity of different views at a data instance level instead of a view level. This paper also introduces an approach to deal with the imbalance between the positive and negative constraints. The proposed method has been tested in clustering tasks on two publicly available multi-view data sets to show the superior performance.
Document Image Coding and Clustering for Script Discrimination
Venue: arXiv cs.CV 2016
Year: 2016

The paper introduces a new method for discrimination of documents given in different scripts. The document is mapped into a uniformly coded text of numerical values. It is derived from the position of the letters in the text line, based on their typographical characteristics. Each code is considered as a gray level. Accordingly, the coded text determines a 1-D image, on which texture analysis by run-length statistics and local binary pattern is performed. It defines feature vectors representing the script content of the document. A modified clustering approach employed on document feature vector groups documents written in the same script. Experimentation performed on two custom oriented databases of historical documents in old Cyrillic, angular and round Glagolitic as well as Antiqua and Fraktur scripts demonstrates the superiority of the proposed method with respect to well-known methods in the state-of-the-art.
Don't Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization
Venue: arXiv cs.SI 2016
Year: 2016

We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds --- a central problem in the study of network cascades. The majority of existing work on this problem, formally referred to as the influence maximization problem, is designed for submodular cascades. Despite the empirical evidence that many cascades are non-submodular, little work has been done focusing on non-submodular influence maximization. We propose a new heuristic for solving the influence maximization problem and show via simulations on real-world and synthetic networks that our algorithm outputs more influential seed sets than the state-of-the-art greedy algorithm in many natural cases, with average improvements of 7% for submodular cascades, and 55% for non-submodular cascades. Our heuristic uses a dynamic programming approach on a hierarchical decomposition of the social network to leverage the relation between the spread of cascades and the community structure of social networks. We verify the importance of network structure by showing the quality of the hierarchical decomposition impacts the quality of seed set output by our algorithm. We also present "worst-case" theoretical results proving that in certain settings our algorithm outputs seed sets that are a factor of $Θ(\sqrt{n})$ more influential than those of the greedy algorithm, where $n$ is the number of nodes in the network. Finally, we generalize our algorithm to a message passing version that can be used to find seed sets that have at least as much influence as the dynamic programming algorithms.
On the Mathematical Relationship between Expected n-call@k and the Relevance vs. Diversity Trade-off
Venue: arXiv cs.IR 2016
Year: 2016

It has been previously noted that optimization of the n-call@k relevance objective (i.e., a set-based objective that is 1 if at least n documents in a set of k are relevant, otherwise 0) encourages more result set diversification for smaller n, but this statement has never been formally quantified. In this work, we explicitly derive the mathematical relationship between expected n-call@k and the relevance vs. diversity trade-off --- through fortuitous cancellations in the resulting combinatorial optimization, we show the trade-off is a simple and intuitive function of n (notably independent of the result set size k e n), where diversification increases as n approaches 1.
Resilient Operation of Transportation Networks via Variable Speed Limits
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we investigate the use of variable speed limits for resilient operation of transportation networks, which are modeled as dynamical flow networks under local routing decisions. In such systems, some external inflow is injected to the so-called origin nodes of the network. The total inflow arriving at each node is routed to its operational outgoing links based on their current particle densities. The density on each link has first order dynamics driven by the difference of its incoming and outgoing flows. A link irreversibly fails if it reaches its jam density. Such failures may propagate in the network and cause a systemic failure. We show that larger link capacities do not necessarily help in preventing systemic failures under local routing. Accordingly, we propose the use of variable speed limits to operate the links below their capacities, when necessary, to compensate for the lack of global information and coordination in routing decisions. Our main result shows that systemic failures under feasible external inflows can always be averted through a proper selection of speed limits if the routing decisions are sufficiently responsive to local congestion and the network is initially uncongested. This is an attractive feature as it is much easier in practice to adjust the speed limits than to build more physical capacity or to alter routing decisions that are determined by social behavior.
Spatio-Temporal Sentiment Hotspot Detection Using Geotagged Photos
Venue: arXiv cs.CV 2016
Year: 2016

We perform spatio-temporal analysis of public sentiment using geotagged photo collections. We develop a deep learning-based classifier that predicts the emotion conveyed by an image. This allows us to associate sentiment with place. We perform spatial hotspot detection and show that different emotions have distinct spatial distributions that match expectations. We also perform temporal analysis using the capture time of the photos. Our spatio-temporal hotspot detection correctly identifies emerging concentrations of specific emotions and year-by-year analyses of select locations show there are strong temporal correlations between the predicted emotions and known events.
A Novel GPU-based Parallel Implementation Scheme and Performance Analysis of Robot Forward Dynamics Algorithms
Venue: arXiv cs.RO 2016
Year: 2016

We propose a novel unifying scheme for parallel implementation of articulated robot dynamics algorithms. It is based on a unified Lie group notation for deriving the equations of motion of articulated robots, where various well-known forward algorithms differ only by their joint inertia matrix inversion strategies. This new scheme leads to a unified abstraction of state-of-the-art forward dynamics algorithms into combinations of block bi-diagonal and/or block tri-diagonal systems, which may be efficiently solved by parallel all-prefix-sum operations (scan) and parallel odd-even elimination (OEE) respectively. We implement the proposed scheme on a Nvidia CUDA GPU platform for the comparative study of three algorithms, namely the hybrid articulated-body inertia algorithm (ABIA), the parallel joint space inertia inversion algorithm (JSIIA) and the constrained force algorithm (CFA), and the performances are analyzed.