OpenRaiser/Intern-Atlas huggingface dataset:
Fair Allocation based on Diminishing Differences
Venue: arXiv cs.GT 2019
Year: 2019

Ranking alternatives is a natural way for humans to explain their preferences. It is being used in many settings, such as school choice, course allocations and residency matches. In some cases, several `items' are given to each participant. Without having any information on the underlying cardinal utilities, arguing about fairness of allocation requires extending the ordinal item ranking to ordinal bundle ranking. The most commonly used such extension is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if its score is better according to all additive score functions. SD is a very conservative extension, by which few allocations are necessarily fair while many allocations are possibly fair. We propose to make a natural assumption on the underlying cardinal utilities of the players, namely that the difference between two items at the top is larger than the difference between two items at the bottom. This assumption implies a preference extension which we call diminishing differences (DD), where X is preferred over Y if its score is better according to all additive score functions satisfying the DD assumption. We give a full characterization of allocations that are necessarily-proportional or possibly-proportional according to this assumption. Based on this characterization, we present a polynomial-time algorithm for finding a necessarily-DD-proportional allocation if it exists. Using simulations, we show that with high probability, a necessarily-proportional allocation does not exist but a necessarily-DD-proportional allocation exists, and moreover, that allocation is proportional according to the underlying cardinal utilities. We also consider chore allocation under the analogous condition --- increasing-differences.
Variations of Checking Stack Automata: Obtaining Unexpected Decidability Properties
Venue: arXiv cs.FL 2019
Year: 2019

We introduce a model of one-way language acceptors (a variant of a checking stack automaton) and show the following decidability properties: (1) The deterministic version has a decidable membership problem but has an undecidable emptiness problem. (2) The nondeterministic version has an undecidable membership problem and emptiness problem. There are many models of accepting devices for which there is no difference with these problems between deterministic and nondeterministic versions, and the same holds for the emptiness problem. As far as we know, the model we introduce above is the first one-way model to exhibit properties (1) and (2). We define another family of one-way acceptors where the nondeterministic version has an undecidable emptiness problem, but the deterministic version has a decidable emptiness problem. We also know of no other model with this property in the literature. We also investigate decidability properties of other variations of checking stack automata (e.g., allowing multiple stacks, two-way input, etc.). Surprisingly, two-way deterministic machines with multiple checking stacks and multiple reversal-bounded counters are shown to have a decidable membership problem, a very general model with this property.
Automatic White-Box Testing of First-Order Logic Ontologies
Venue: arXiv cs.AI 2019
Year: 2019

Formal ontologies are axiomatizations in a logic-based formalism. The development of formal ontologies, and their important role in the Semantic Web area, is generating considerable research on the use of automated reasoning techniques and tools that help in ontology engineering. One of the main aims is to refine and to improve axiomatizations for enabling automated reasoning tools to efficiently infer reliable information. Defects in the axiomatization can not only cause wrong inferences, but can also hinder the inference of expected information, either by increasing the computational cost of, or even preventing, the inference. In this paper, we introduce a novel, fully automatic white-box testing framework for first-order logic ontologies. Our methodology is based on the detection of inference-based redundancies in the given axiomatization. The application of the proposed testing method is fully automatic since a) the automated generation of tests is guided only by the syntax of axioms and b) the evaluation of tests is performed by automated theorem provers. Our proposal enables the detection of defects and serves to certify the grade of suitability --for reasoning purposes-- of every axiom. We formally define the set of tests that are generated from any axiom and prove that every test is logically related to redundancies in the axiom from which the test has been generated. We have implemented our method and used this implementation to automatically detect several non-trivial defects that were hidden in various first-order logic ontologies. Throughout the paper we provide illustrative examples of these defects, explain how they were found, and how each proof --given by an automated theorem-prover-- provides useful hints on the nature of each defect. Additionally, by correcting all the detected defects, we have obtained an improved version of one of the tested ontologies: Adimen-SUMO.
Development of a N-type GM-PHD Filter for Multiple Target, Multiple Type Visual Tracking
Venue: arXiv cs.CV 2019
Year: 2019

We propose a new framework that extends the standard Probability Hypothesis Density (PHD) filter for multiple targets having $N\geq2$ different types based on Random Finite Set theory, taking into account not only background clutter, but also confusions among detections of different target types, which are in general different in character from background clutter. Under Gaussianity and linearity assumptions, our framework extends the existing Gaussian mixture (GM) implementation of the standard PHD filter to create a N-type GM-PHD filter. The methodology is applied to real video sequences by integrating object detectors' information into this filter for two scenarios. For both cases, Munkres's variant of the Hungarian assignment algorithm is used to associate tracked target identities between frames. This approach is evaluated and compared to both raw detection and independent GM-PHD filters using the Optimal Sub-pattern Assignment metric and discrimination rate. This shows the improved performance of our strategy on real video sequences.
Concept Transfer Learning for Adaptive Language Understanding
Venue: arXiv cs.CL 2019
Year: 2019

Concept definition is important in language understanding (LU) adaptation since literal definition difference can easily lead to data sparsity even if different data sets are actually semantically correlated. To address this issue, in this paper, a novel concept transfer learning approach is proposed. Here, substructures within literal concept definition are investigated to reveal the relationship between concepts. A hierarchical semantic representation for concepts is proposed, where a semantic slot is represented as a composition of {\em atomic concepts}. Based on this new hierarchical representation, transfer learning approaches are developed for adaptive LU. The approaches are applied to two tasks: value set mismatch and domain adaptation, and evaluated on two LU benchmarks: ATIS and DSTC 2\&3. Thorough empirical studies validate both the efficiency and effectiveness of the proposed method. In particular, we achieve state-of-the-art performance ($F_1$-score 96.08\%) on ATIS by only using lexicon features.
On the role of clustering in Personalized PageRank estimation
Venue: arXiv cs.SI 2019
Year: 2019

Personalized PageRank (PPR) is a measure of the importance of a node from the perspective of another (we call these nodes the $\textit{target}$ and the $\textit{source}$, respectively). PPR has been used in many applications, such as offering a Twitter user (the source) recommendations of who to follow (targets deemed important by PPR); additionally, PPR has been used in graph-theoretic problems such as community detection. However, computing PPR is infeasible for large networks like Twitter, so efficient estimation algorithms are necessary. In this work, we analyze the relationship between PPR estimation complexity and clustering. First, we devise algorithms to estimate PPR for many source/target pairs. In particular, we propose an enhanced version of the existing single pair estimator $\texttt{Bidirectional-PPR}$ that is more useful as a primitive for many pair estimation. We then show that the common underlying graph can be leveraged to efficiently and jointly estimate PPR for many pairs, rather than treating each pair separately using the primitive algorithm. Next, we show the complexity of our joint estimation scheme relates closely to the degree of clustering among the sources and targets at hand, indicating that estimating PPR for many pairs is easier when clustering occurs. Finally, we consider estimating PPR when several machines are available for parallel computation, devising a method that leverages our clustering findings, specifically the quantities computed $\textit{in situ}$, to assign tasks to machines in a manner that reduces computation time. This demonstrates that the relationship between complexity and clustering has important consequences in a practical distributed setting.
Seeking Optimum System Settings for Physical Activity Recognition on Smartwatches
Venue: arXiv cs.CY 2019
Year: 2019

Physical activity recognition (PAR) using wearable devices can provide valued information regarding an individual's degree of functional ability and lifestyle. In this regards, smartphone-based physical activity recognition is a well-studied area. Research on smartwatch-based PAR, on the other hand, is still in its infancy. Through a large-scale exploratory study, this work aims to investigate the smartwatch-based PAR domain. A detailed analysis of various feature banks and classification methods are carried out to find the optimum system settings for the best performance of any smartwatch-based PAR system for both personal and impersonal models. To further validate our hypothesis for both personal (The classifier is built using the data only from one specific user) and impersonal (The classifier is built using the data from every user except the one under study) models, we tested single subject validation process for smartwatch-based activity recognition.
Detecting Approximate Reflection Symmetry in a Point Set using Optimization on Manifold
Venue: arXiv cs.CV 2019
Year: 2019

We propose an algorithm to detect approximate reflection symmetry present in a set of volumetrically distributed points belonging to $\mathbb{R}^d$ containing a distorted reflection symmetry pattern. We pose the problem of detecting approximate reflection symmetry as the problem of establishing correspondences between the points which are reflections of each other and we determine the reflection symmetry transformation. We formulate an optimization framework in which the problem of establishing the correspondences amounts to solving a linear assignment problem and the problem of determining the reflection symmetry transformation amounts to solving an optimization problem on a smooth Riemannian product manifold. The proposed approach estimates the symmetry from the geometry of the points and is descriptor independent. We evaluate the performance of the proposed approach on the standard benchmark dataset and achieve the state-of-the-art performance. We further show the robustness of our approach by varying the amount of distortion in a perfect reflection symmetry pattern where we perturb each point by a different amount of perturbation. We demonstrate the effectiveness of the method by applying it to the problem of 2-D and 3-D reflection symmetry detection along with comparisons.
Gabor frames and deep scattering networks in audio processing
Venue: arXiv cs.SD 2019
Year: 2019

This paper introduces Gabor scattering, a feature extractor based on Gabor frames and Mallat's scattering transform. By using a simple signal model for audio signals specific properties of Gabor scattering are studied. It is shown that for each layer, specific invariances to certain signal characteristics occur. Furthermore, deformation stability of the coefficient vector generated by the feature extractor is derived by using a decoupling technique which exploits the contractivity of general scattering networks. Deformations are introduced as changes in spectral shape and frequency modulation. The theoretical results are illustrated by numerical examples and experiments. Numerical evidence is given by evaluation on a synthetic and a "real" data set, that the invariances encoded by the Gabor scattering transform lead to higher performance in comparison with just using Gabor transform, especially when few training samples are available.
Shrub-depth: Capturing Height of Dense Graphs
Venue: arXiv cs.LO 2019
Year: 2019

The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower $ω$ levels of the MSO1 transduction hierarchy of simple graphs.
Streamability of nested word transductions
Venue: arXiv cs.FL 2019
Year: 2019

We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height of the input word. We show that it is decidable in coNPTime for a nested word transduction defined by a visibly pushdown transducer (VPT), if it is HBM. In this case, the required amount of memory may depend exponentially on the height of the word. We exhibit a sufficient, decidable condition for a VPT to be evaluated with a memory that depends quadratically on the height of the word. This condition defines a class of transductions that strictly contains all determinizable VPTs.
Hyperbolic triangulations and discrete random graphs
Venue: arXiv cs.CG 2019
Year: 2019

The hyperbolic random graph model (HRG) has proven useful in the analysis of scale-free networks, which are ubiquitous in many fields, from social network analysis to biology. However, working with this model is algorithmically and conceptually challenging because of the nature of the distances in the hyperbolic plane. In this paper we study the algorithmic properties of regularly generated triangulations in the hyperbolic plane. We propose a discrete variant of the HRG model where nodes are mapped to the vertices of such a triangulation; our algorithms allow us to work with this model in a simple yet efficient way. We present experimental results conducted on real world networks to evaluate the practical benefits of DHRG in comparison to the HRG model.
Robustness Among Multiwinner Voting Rules
Venue: arXiv cs.GT 2019
Year: 2019

We investigate how robust the results of committee elections are to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules the effect of making a single swap of adjacent candidates in a single preference order is either that (1) at most one committee member might be replaced, or (2) it is possible that the whole committee will be replaced. We also show that the problem of computing the smallest number of swaps that lead to changing the election outcome is typically NP-hard, but there are natural FPT algorithms. Finally, for a number of rules we assess experimentally the average number of random swaps necessary to change the election result.
Logical properties of random graphs from small addable classes
Venue: arXiv cs.LO 2019
Year: 2019

We establish zero-one laws and convergence laws for monadic second-order logic (MSO) (and, a fortiori, first-order logic) on a number of interesting graph classes. In particular, we show that MSO obeys a zero-one law on the class of connected planar graphs, the class of connected graphs of tree-width at most $k$ and the class of connected graphs excluding the $k$-clique as a minor. In each of these cases, dropping the connectivity requirement leads to a class where the zero-one law fails but a convergence law for MSO still holds.
Deep Q-Learning for Self-Organizing Networks Fault Management and Radio Performance Improvement
Venue: arXiv cs.NI 2019
Year: 2019

We propose an algorithm to automate fault management in an outdoor cellular network using deep reinforcement learning (RL) against wireless impairments. This algorithm enables the cellular network cluster to self-heal by allowing RL to learn how to improve the downlink signal to interference plus noise ratio through exploration and exploitation of various alarm corrective actions. The main contributions of this paper are to 1) introduce a deep RL-based fault handling algorithm which self-organizing networks can implement in a polynomial runtime and 2) show that this fault management method can improve the radio link performance in a realistic network setup. Simulation results show that our proposed algorithm learns an action sequence to clear alarms and improve the performance in the cellular cluster better than existing algorithms, even against the randomness of the network fault occurrences and user movements.
On the Impact of the Model-based Representation of Inconsistencies to Manual Reviews: Results from a Controlled Experiment - Extended Version
Venue: arXiv cs.SE 2019
Year: 2019

To ensure fulfilling stakeholder wishes, it is crucial to validate the documented requirements. This is often complicated by the fact that the wishes and intentions of different stakeholders are somewhat contradictory, which manifests itself in inconsistent requirements. To aid requirements engineers in identifying and resolving inconsistent requirements, we investigated the usefulness for manual reviews of two different model-based representation formats for inconsistent requirements; one that represent the inconsistent requirements in separate diagrams and one that represents them integrated into one diagram using annotations. The results from a controlled experiment show that the use of such integrated review diagrams can significantly increase efficiency of manual reviews, without sacrificing effectiveness.
Community Discovery in Dynamic Networks: a Survey
Venue: arXiv cs.SI 2019
Year: 2019

Networks built to model real world phenomena are characeterised by some properties that have attracted the attention of the scientific community: (i) they are organised according to community structure and (ii) their structure evolves with time. Many researchers have worked on methods that can efficiently unveil substructures in complex networks, giving birth to the field of community discovery. A novel and challenging problem started capturing researcher interest recently: the identification of evolving communities. To model the evolution of a system, dynamic networks can be used: nodes and edges are mutable and their presence, or absence, deeply impacts the community structure that composes them. The aim of this survey is to present the distinctive features and challenges of dynamic community discovery, and propose a classification of published approaches. As a "user manual", this work organizes state of art methodologies into a taxonomy, based on their rationale, and their specific instanciation. Given a desired definition of network dynamics, community characteristics and analytical needs, this survey will support researchers to identify the set of approaches that best fit their needs. The proposed classification could also help researchers to choose in which direction should future research be oriented.
A unified approach to source and message compression
Venue: arXiv cs.IT 2019
Year: 2019

We study the problem of source and message compression in the one-shot setting for the point-to-point and multi-party scenarios (with and without side information). We derive achievability results for these tasks in a unified manner, using the techniques of convex-split, which was introduced in [Anshu,Devabathini and Jain 2014] and position-based decoding introduced in [Anshu, Jain and Warsi 2017], which in turn uses hypothesis testing between distributions. These results are in terms of smooth max divergence and smooth hypothesis testing divergence. As a by-product of the tasks studied in this work, we obtain several known source compression results (originally studied in the asymptotic and i.i.d. setting) in the one-shot case. One of our achievability results includes the problem of message compression with side information, originally studied in [Braverman and Rao 2011]. We show that both our result and the result in [Braverman and Rao 2011] are near optimal in the one-shot setting by proving a converse bound.
Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP
Venue: arXiv cs.DM 2019
Year: 2019

We show that there is a polynomial-time algorithm with approximation guarantee $\frac{3}{2}+ε$ for the $s$-$t$-path TSP, for any fixed $ε>0$. It is well known that Wolsey's analysis of Christofides' algorithm also works for the $s$-$t$-path TSP with its natural LP relaxation except for the narrow cuts (in which the LP solution has value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut lonely) or at least three (then call the cut busy). Our algorithm "guesses" (by dynamic programming) lonely cuts and edges. Then we partition the instance into smaller instances and strengthen the LP, requiring value at least three for busy cuts. By setting up a $k$-stage recursive dynamic program, we can compute a spanning tree $(V,S)$ and an LP solution $y$ such that $(\frac{1}{2}+O(2^{-k}))y$ is in the $T$-join polyhedron, where $T$ is the set of vertices whose degree in $S$ has the wrong parity.
Developing the Path Signature Methodology and its Application to Landmark-based Human Action Recognition
Venue: arXiv cs.CV 2019
Year: 2019

Landmark-based human action recognition in videos is a challenging task in computer vision. One key step is to design a generic approach that generates discriminative features for the spatial structure and temporal dynamics. To this end, we regard the evolving landmark data as a high-dimensional path and apply non-linear path signature techniques to provide an expressive, robust, non-linear, and interpretable representation for the sequential events. We do not extract signature features from the raw path, rather we propose path disintegrations and path transformations as preprocessing steps. Path disintegrations turn a high-dimensional path linearly into a collection of lower-dimensional paths; some of these paths are in pose space while others are defined over a multiscale collection of temporal intervals. Path transformations decorate the paths with additional coordinates in standard ways to allow the truncated signatures of transformed paths to expose additional features. For spatial representation, we apply the signature transform to vectorize the paths that arise out of pose disintegration, and for temporal representation, we apply it again to describe this evolving vectorization. Finally, all the features are collected together to constitute the input vector of a linear single-hidden-layer fully-connected network for classification. Experimental results on four datasets demonstrated that the proposed feature set with only a linear shallow network and Dropconnect is effective and achieves comparable state-of-the-art results to the advanced deep networks, and meanwhile, is capable of interpretation.