OpenRaiser/Intern-Atlas huggingface dataset:
Adversarial Influence Maximization
Venue: arXiv cs.SI 2019
Year: 2019

We consider the problem of influence maximization in fixed networks for contagion models in an adversarial setting. The goal is to select an optimal set of nodes to seed the influence process, such that the number of influenced nodes at the conclusion of the campaign is as large as possible. We formulate the problem as a repeated game between a player and adversary, where the adversary specifies the edges along which the contagion may spread, and the player chooses sets of nodes to influence in an online fashion. We establish upper and lower bounds on the minimax pseudo-regret in both undirected and directed networks.
Decision Tree Classification with Differential Privacy: A Survey
Venue: arXiv cs.DB 2019
Year: 2019

Data mining information about people is becoming increasingly important in the data-driven society of the 21st century. Unfortunately, sometimes there are real-world considerations that conflict with the goals of data mining; sometimes the privacy of the people being data mined needs to be considered. This necessitates that the output of data mining algorithms be modified to preserve privacy while simultaneously not ruining the predictive power of the outputted model. Differential privacy is a strong, enforceable definition of privacy that can be used in data mining algorithms, guaranteeing that nothing will be learned about the people in the data that could not already be discovered without their participation. In this survey, we focus on one particular data mining algorithm -- decision trees -- and how differential privacy interacts with each of the components that constitute decision tree algorithms. We analyze both greedy and random decision trees, and the conflicts that arise when trying to balance privacy requirements with the accuracy of the model.
How to do lexical quality estimation of a large OCRed historical Finnish newspaper collection with scarce resources
Venue: arXiv cs.CL 2019
Year: 2019

The National Library of Finland has digitized the historical newspapers published in Finland between 1771 and 1910. This collection contains approximately 1.95 million pages in Finnish and Swedish. Finnish part of the collection consists of about 2.40 billion words. The National Library's Digital Collections are offered via the digi.kansalliskirjasto.fi web service, also known as Digi. Part of the newspaper material (from 1771 to 1874) is also available freely downloadable in The Language Bank of Finland provided by the FINCLARIN consortium. The collection can also be accessed through the Korp environment that has been developed by Språkbanken at the University of Gothenburg and extended by FINCLARIN team at the University of Helsinki to provide concordances of text resources. A Cranfield style information retrieval test collection has also been produced out of a small part of the Digi newspaper material at the University of Tampere. Quality of OCRed collections is an important topic in digital humanities, as it affects general usability and searchability of collections. There is no single available method to assess quality of large collections, but different methods can be used to approximate quality. This paper discusses different corpus analysis style methods to approximate overall lexical quality of the Finnish part of the Digi collection. Methods include usage of parallel samples and word error rates, usage of morphological analyzers, frequency analysis of words and comparisons to comparable edited lexical data. Our aim in the quality analysis is twofold: firstly to analyze the present state of the lexical data and secondly, to establish a set of assessment methods that build up a compact procedure for quality assessment after e.g. new OCRing or post correction of the material. In the discussion part of the paper we shall synthesize results of our different analyses.
Kolmogorov complexity and generalized length functions
Venue: arXiv cs.CC 2019
Year: 2019

Kolmogorov complexity measures the algorithmic complexity of a finite binary string $σ$ in terms of the length of the shortest description $σ^*$ of $σ$. Traditionally, the length of a string is taken to measure the amount of information contained in the string. However, we may also view the length of $σ$ as a measure of the cost of producing $σ$, which permits one to generalize the notion of length, wherein the cost of producing a 0 or a 1 can vary in some prescribed manner. In this article, we initiate the study of this generalization of length based on the above information cost interpretation. We also modify the definition of Kolmogorov complexity to use such generalized length functions instead of standard length. We further investigate conditions under which the notion of complexity defined in terms of a given generalized length function preserves some essential properties of Kolmogorov complexity. We focus on a specific class of generalized length functions that are intimately related to a specific subcollection of Bernoulli $p$-measures, namely those corresponding to the unique computable real $p\in(0,1)$ such that $p^k=1-p$, for integers $k\geq 1$. We then study randomness with respect to such measures, by proving a generalization version of the classic Levin-Schnorr theorem that involves $k$-length functions and then proving subsequent results that involve effective dimension and entropy.
ViFi: Virtual Fingerprinting WiFi-based Indoor Positioning via Multi-Wall Multi-Floor Propagation Model
Venue: arXiv cs.NI 2019
Year: 2019

Widespread adoption of indoor positioning systems based on WiFi fingerprinting is at present hindered by the large efforts required for measurements collection during the offline phase. Two approaches were recently proposed to address such issue: crowdsourcing and RSS radiomap prediction, based on either interpolation or propagation channel model fitting from a small set of measurements. RSS prediction promises better positioning accuracy when compared to crowdsourcing, but no systematic analysis of the impact of system parameters on positioning accuracy is available. This paper fills this gap by introducing ViFi, an indoor positioning system that relies on RSS prediction based on Multi-Wall Multi-Floor (MWMF) propagation model to generate a discrete RSS radiomap (virtual fingerprints). Extensive experimental results, obtained in multiple independent testbeds, show that ViFi outperforms virtual fingerprinting systems adopting simpler propagation models in terms of accuracy, and allows a sevenfold reduction in the number of measurements to be collected, while achieving the same accuracy of a traditional fingerprinting system deployed in the same environment. Finally, a set of guidelines for the implementation of ViFi in a generic environment, that saves the effort of collecting additional measurements for system testing and fine tuning, is proposed.
Adams Conditioning and Likelihood Ratio Transfer Mediated Inference
Venue: arXiv cs.AI 2019
Year: 2019

Bayesian inference as applied in a legal setting is about belief transfer and involves a plurality of agents and communication protocols. A forensic expert (FE) may communicate to a trier of fact (TOF) first its value of a certain likelihood ratio with respect to FE's belief state as represented by a probability function on FE's proposition space. Subsequently FE communicates its recently acquired confirmation that a certain evidence proposition is true. Then TOF performs likelihood ratio transfer mediated reasoning thereby revising their own belief state. The logical principles involved in likelihood transfer mediated reasoning are discussed in a setting where probabilistic arithmetic is done within a meadow, and with Adams conditioning placed in a central role.
Is Non-Neutrality Profitable for the Stakeholders of the Internet Market?
Venue: arXiv cs.GT 2019
Year: 2019

Net neutrality on the Internet is perceived as the policy that mandates Internet Service Providers (ISPs) to treat all data equally, regardless of the source, destination, or type of transmitted data. In this work, we consider a scheme in which the decision makers of the market are two ISPs, one "big" Content Provider (CP), and a continuum of end-users. One of the ISPs is neutral and the other is non-neutral, i.e. she offers a premium quality to a CP in exchange for a side-payment. In addition, we assume that the CP can differentiate between ISPs by controlling the quality of the content she is offering on each one. In this part of the paper, we consider a scenario in which end-users are not locked in with the ISPs and can switch between ISPs easily. We formulate a sequential game, and show that there exists a unique Sub-game Perfect Nash Equilibrium (SPNE) for the game, where the CP pays the side-payment to the non-neutral ISP and offers her content with the premium quality. In addition, the CP does not offer her content on the neutral ISP. Thus, driving this ISP out of the market.
SqueezeDet: Unified, Small, Low Power Fully Convolutional Neural Networks for Real-Time Object Detection for Autonomous Driving
Venue: arXiv cs.CV 2019
Year: 2019

Object detection is a crucial task for autonomous driving. In addition to requiring high accuracy to ensure safety, object detection for autonomous driving also requires real-time inference speed to guarantee prompt vehicle control, as well as small model size and energy efficiency to enable embedded system deployment. In this work, we propose SqueezeDet, a fully convolutional neural network for object detection that aims to simultaneously satisfy all of the above constraints. In our network, we use convolutional layers not only to extract feature maps but also as the output layer to compute bounding boxes and class probabilities. The detection pipeline of our model only contains a single forward pass of a neural network, thus it is extremely fast. Our model is fully-convolutional, which leads to a small model size and better energy efficiency. While achieving the same accuracy as previous baselines, our model is 30.4x smaller, 19.7x faster, and consumes 35.2x lower energy. The code is open-sourced at \url{https://github.com/BichenWuUCB/squeezeDet}.
Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
Venue: arXiv cs.NA 2019
Year: 2019

We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern, which is closely related to finite completion. Probabilistic conditions are then studied and a lower bound on the sampling probability is given, which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a sufficient condition on the sampling pattern that ensures there exists exactly one completion for the sampled tensor.
Testing Ising Models
Venue: arXiv cs.DS 2019
Year: 2019

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each other? These problems of testing independence and goodness-of-fit have received enormous attention in statistics, information theory, and theoretical computer science, with sample-optimal algorithms known in several interesting regimes of parameters. Unfortunately, it has also been understood that these problems become intractable in large dimensions, necessitating exponential sample complexity. Motivated by the exponential lower bounds for general distributions as well as the ubiquity of Markov Random Fields (MRFs) in the modeling of high-dimensional distributions, we initiate the study of distribution testing on structured multivariate distributions, and in particular the prototypical example of MRFs: the Ising Model. We demonstrate that, in this structured setting, we can avoid the curse of dimensionality, obtaining sample and time efficient testers for independence and goodness-of-fit. One of the key technical challenges we face along the way is bounding the variance of functions of the Ising model.
Co-localization with Category-Consistent Features and Geodesic Distance Propagation
Venue: arXiv cs.CV 2019
Year: 2019

Co-localization is the problem of localizing objects of the same class using only the set of images that contain them. This is a challenging task because the object detector must be built without negative examples that can lead to more informative supervision signals. The main idea of our method is to cluster the feature space of a generically pre-trained CNN, to find a set of CNN features that are consistently and highly activated for an object category, which we call category-consistent CNN features. Then, we propagate their combined activation map using superpixel geodesic distances for co-localization. In our first set of experiments, we show that the proposed method achieves state-of-the-art performance on three related benchmarks: PASCAL 2007, PASCAL-2012, and the Object Discovery dataset. We also show that our method is able to detect and localize truly unseen categories, on six held-out ImageNet categories with accuracy that is significantly higher than previous state-of-the-art. Our intuitive approach achieves this success without any region proposals or object detectors and can be based on a CNN that was pre-trained purely on image classification tasks without further fine-tuning.
Border-Peeling Clustering
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we present a novel non-parametric clustering technique. Our technique is based on the notion that each latent cluster is comprised of layers that surround its core, where the external layers, or border points, implicitly separate the clusters. Unlike previous techniques, such as DBSCAN, where the cores of the clusters are defined directly by their densities, here the latent cores are revealed by a progressive peeling of the border points. Analyzing the density of the local neighborhoods allows identifying the border points and associating them with points of inner layers. We show that the peeling process adapts to the local densities and characteristics to successfully separate adjacent clusters (of possibly different densities). We extensively tested our technique on large sets of labeled data, including high-dimensional datasets of deep features that were trained by a convolutional neural network. We show that our technique is competitive to other state-of-the-art non-parametric methods using a fixed set of parameters throughout the experiments.
Feature Encoding in Band-limited Distributed Surveillance Systems
Venue: arXiv cs.CV 2019
Year: 2019

Distributed surveillance systems have become popular in recent years due to security concerns. However, transmitting high dimensional data in bandwidth-limited distributed systems becomes a major challenge. In this paper, we address this issue by proposing a novel probabilistic algorithm based on the divergence between the probability distributions of the visual features in order to reduce their dimensionality and thus save the network bandwidth in distributed wireless smart camera networks. We demonstrate the effectiveness of the proposed approach through extensive experiments on two surveillance recognition tasks.
Solving Combinatorial Optimization problems with Quantum inspired Evolutionary Algorithm Tuned using a Novel Heuristic Method
Venue: arXiv cs.AI 2019
Year: 2019

Quantum inspired Evolutionary Algorithms were proposed more than a decade ago and have been employed for solving a wide range of difficult search and optimization problems. A number of changes have been proposed to improve performance of canonical QEA. However, canonical QEA is one of the few evolutionary algorithms, which uses a search operator with relatively large number of parameters. It is well known that performance of evolutionary algorithms is dependent on specific value of parameters for a given problem. The advantage of having large number of parameters in an operator is that the search process can be made more powerful even with a single operator without requiring a combination of other operators for exploration and exploitation. However, the tuning of operators with large number of parameters is complex and computationally expensive. This paper proposes a novel heuristic method for tuning parameters of canonical QEA. The tuned QEA outperforms canonical QEA on a class of discrete combinatorial optimization problems which, validates the design of the proposed parameter tuning framework. The proposed framework can be used for tuning other algorithms with both large and small number of tunable parameters.
Time and space efficient generators for quasiseparable matrices
Venue: arXiv cs.SC 2019
Year: 2019

The class of quasiseparable matrices is defined by the property that any submatrix entirely below or above the main diagonal has small rank, namely below a bound called the order of quasiseparability. These matrices arise naturally in solving PDE's for particle interaction with the Fast Multi-pole Method (FMM), or computing generalized eigenvalues. From these application fields, structured representations and algorithms have been designed in numerical linear algebra to compute with these matrices in time linear in the matrix dimension and either quadratic or cubic in the quasiseparability order. Motivated by the design of the general purpose exact linear algebra library LinBox, and by algorithmic applications in algebraic computing, we adapt existing techniques introduce novel ones to use quasiseparable matrices in exact linear algebra, where sub-cubic matrix arithmetic is available. In particular, we will show, the connection between the notion of quasiseparability and the rank profile matrix invariant, that we have introduced in 2015. It results in two new structured representations, one being a simpler variation on the hierarchically semiseparable storage, and the second one exploiting the generalized Bruhat decomposition. As a consequence, most basic operations, such as computing the quasiseparability orders, applying a vector, a block vector, multiplying two quasiseparable matrices together, inverting a quasiseparable matrix, can be at least as fast and often faster than previous existing algorithms.
Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
Venue: arXiv cs.LO 2019
Year: 2019

We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences, and ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and on conjunctive queries. We show that rewritability into FO and into monadic Datalog (MDLog) are decidable, and that rewritability into Datalog is decidable when the original query satisfies a certain condition related to equality. We establish 2NExpTime-completeness for all studied problems except rewritability into MDLog for which there remains a gap between 2NExpTime and 3ExpTime. We also analyze the shape of rewritings, which in the MMSNP case correspond to obstructions, and give a new construction of canonical Datalog programs that is more elementary than existing ones and also applies to formulas with free variables.
Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
Venue: arXiv cs.CG 2019
Year: 2019

We introduce the fully-dynamic conflict-free coloring problem for a set $S$ of intervals in $\mathbb{R}^1$ with respect to points, where the goal is to maintain a conflict-free coloring for$S$ under insertions and deletions. A coloring is conflict-free if for each point $p$ contained in some interval, $p$ is contained in an interval whose color is not shared with any other interval containing $p$. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: - a lower bound on the number of recolorings as a function of the number of colors, which implies that with $O(1)$ recolorings per update the worst-case number of colors is $Ω(\log n/\log\log n)$, and that any strategy using $O(1/\varepsilon)$ colors needs $Ω(\varepsilon n^{\varepsilon})$ recolorings; - a coloring strategy that uses $O(\log n)$ colors at the cost of $O(\log n)$ recolorings, and another strategy that uses $O(1/\varepsilon)$ colors at the cost of $O(n^{\varepsilon}/\varepsilon)$ recolorings; - stronger upper and lower bounds for special cases. We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight.
Hypothesis Test for Bounds on the Size of Random Defective Set
Venue: arXiv cs.IT 2019
Year: 2019

The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is unknown there arises an additional problem, namely: how to estimate the random number of defective elements. n this paper, we concentrate on testing the hypothesis $H_0$: the number of defectives $\le s_1$ against the alternative hypothesis $H_1$: the number of defectives $\ge s_2$. We introduce a new decoding algorithm based on the comparison of the number of tests having positive responses with an appropriate fixed threshold. For some asymptotic regimes on $s_1$ and $s_2$, the proposed algorithm is shown to be order-optimal. Additionally, our simulation results verify the advantages of the proposed algorithm such as low complexity and a small error probability compared with known algorithms.
On profile reconstruction of Euler-Bernoulli beams by means of an energy based genetic algorithm
Venue: arXiv cs.CE 2019
Year: 2019

This paper studies the inverse problem related to the identification of the flexural stiffness of an Euler Bernoulli beam in order to reconstruct its profile starting from available response data. The proposed identification procedure makes use of energy measurements and is based on the application of a closed form solution for the static displacements of multi-stepped beams. This solution allows to easily calculate the energy related to beams modeled with arbitrary multi-step shapes subjected to a transversal roving force, and to compare it with the correspondent data obtained through direct measurements on real beams. The optimal solution which minimizes the difference between measured and calculated data is then sought by means of genetic algorithms. In the paper several different stepped beams are investigated showing that the proposed procedure allows in many cases to identify the exact beam profile. However it is shown that in some other cases different multi-step profiles may correspond to very similar static responses, and therefore to comparable minima in the optimization problem, thus complicating the profile identification problem.