OpenRaiser/Intern-Atlas huggingface dataset:
RRR: Rank-Regret Representative
Venue: arXiv cs.DB 2018
Year: 2018

Selecting the best items in a dataset is a common task in data exploration. However, the concept of "best" lies in the eyes of the beholder: different users may consider different attributes more important, and hence arrive at different rankings. Nevertheless, one can remove "dominated" items and create a "representative" subset of the data set, comprising the "best items" in it. A Pareto-optimal representative is guaranteed to contain the best item of each possible ranking, but it can be almost as big as the full data. Representative can be found if we relax the requirement to include the best item for every possible user, and instead just limit the users' "regret". Existing work defines regret as the loss in score by limiting consideration to the representative instead of the full data set, for any chosen ranking function. However, the score is often not a meaningful number and users may not understand its absolute value. Sometimes small ranges in score can include large fractions of the data set. In contrast, users do understand the notion of rank ordering. Therefore, alternatively, we consider the position of the items in the ranked list for defining the regret and propose the {\em rank-regret representative} as the minimal subset of the data containing at least one of the top-$k$ of any possible ranking function. This problem is NP-complete. We use the geometric interpretation of items to bound their ranks on ranges of functions and to utilize combinatorial geometry notions for developing effective and efficient approximation algorithms for the problem. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.
Fair Adaptive Data Rate Allocation and Power Control in LoRaWAN
Venue: arXiv cs.NI 2018
Year: 2018

In this paper, we present results of a study of the data rate fairness among nodes within a LoRaWAN cell. Since LoRa/LoRaWAN supports various data rates, we firstly derive the fairest ratios of deploying each data rate within a cell for a fair collision probability. LoRa/LoRaWAN, like other frequency modulation based radio interfaces, exhibits the \textit{capture effect} in which only the stronger signal of colliding signals will be extracted. This leads to unfairness, where far nodes or nodes experiencing higher attenuation are less likely to see their packets received correctly. Therefore, we secondly develop a transmission power control algorithm to balance the received signal powers from all nodes regardless of their distances from the gateway for a fair data extraction. Simulations show that our approach achieves higher fairness in data rate than the state-of-art in almost all network configurations.
Improved Upper Bounds on all Maximal $α$-gapped Repeats and Palindromes
Venue: arXiv cs.FL 2018
Year: 2018

We show that the number of all maximal $α$-gapped repeats and palindromes of a word of length $n$ is at most $3(π^2/6 + 5/2) αn$ and $7 (π^2 / 6 + 1/2) αn - 5 n - 1$, respectively.
A framework for (de)composing with Boolean automata networks
Venue: arXiv cs.DM 2018
Year: 2018

Boolean automata networks (BANs) are a generalisation of Boolean cellular automata. In such, any theorem describing the way BANs compute information is a strong tool that can be applied to a wide range of models of computation. In this paper we explore a way of working with BANs which involves adding external inputs to the base model (via modules), and more importantly, a way to link networks together using the above mentioned inputs (via wirings). Our aim is to develop a powerful formalism for BAN (de)composition. We formulate two results: the first one shows that our modules/wirings definition is complete, the second one uses modules/wirings to prove simulation results amongst BANs.
Solving determinantal systems using homotopy techniques
Venue: arXiv cs.SC 2018
Year: 2018

Let $\K$ be a field of characteristic zero and $\Kbar$ be an algebraic closure of $\K$. Consider a sequence of polynomials$G=(g\_1,\dots,g\_s)$ in $\K[X\_1,\dots,X\_n]$, a polynomial matrix $\F=[f\_{i,j}] \in \K[X\_1,\dots,X\_n]^{p \times q}$, with $p \leq q$,and the algebraic set $V\_p(F, G)$ of points in $\KKbar$ at which all polynomials in $\G$ and all $p$-minors of $\F$vanish. Such polynomial systems appear naturally in e.g. polynomial optimization, computational geometry.We provide bounds on the number of isolated points in $V\_p(F, G)$ depending on the maxima of the degrees in rows (resp. columns) of $\F$. Next, we design homotopy algorithms for computing those points. These algorithms take advantage of the determinantal structure of the system defining $V\_p(F, G)$. In particular, the algorithms run in time that is polynomial in the bound on the number of isolated points.
Leakage and Protocol Composition in a Game-Theoretic Perspective
Venue: arXiv cs.CR 2018
Year: 2018

In the inference attacks studied in Quantitative Information Flow (QIF), the adversary typically tries to interfere with the system in the attempt to increase its leakage of secret information. The defender, on the other hand, typically tries to decrease leakage by introducing some controlled noise. This noise introduction can be modeled as a type of protocol composition, i.e., a probabilistic choice among different protocols, and its effect on the amount of leakage depends heavily on whether or not this choice is visible to the adversary. In this work we consider operators for modeling visible and invisible choice in protocol composition, and we study their algebraic properties. We then formalize the interplay between defender and adversary in a game-theoretic framework adapted to the specific issues of QIF, where the payoff is information leakage. We consider various kinds of leakage games, depending on whether players act simultaneously or sequentially, and on whether or not the choices of the defender are visible to the adversary. Finally, we establish a hierarchy of these games in terms of their information leakage, and provide methods for finding optimal strategies (at the points of equilibrium) for both attacker and defender in the various cases. The full version of this paper can be found in arXiv:1803.10042
Quantitative Separation Logic - A Logic for Reasoning about Probabilistic Programs
Venue: arXiv cs.LO 2018
Year: 2018

We present quantitative separation logic ($\mathsf{QSL}$). In contrast to classical separation logic, $\mathsf{QSL}$ employs quantities which evaluate to real numbers instead of predicates which evaluate to Boolean values. The connectives of classical separation logic, separating conjunction and separating implication, are lifted from predicates to quantities. This extension is conservative: Both connectives are backward compatible to their classical analogs and obey the same laws, e.g. modus ponens, adjointness, etc. Furthermore, we develop a weakest precondition calculus for quantitative reasoning about probabilistic pointer programs in $\mathsf{QSL}$. This calculus is a conservative extension of both Reynolds' separation logic for heap-manipulating programs and Kozen's / McIver and Morgan's weakest preexpectations for probabilistic programs. Soundness is proven with respect to an operational semantics based on Markov decision processes. Our calculus preserves O'Hearn's frame rule, which enables local reasoning. We demonstrate that our calculus enables reasoning about quantities such as the probability of terminating with an empty heap, the probability of reaching a certain array permutation, or the expected length of a list.
On the Benefits of Asymmetric Coded Cache Placement in Combination Networks with End-User Caches
Venue: arXiv cs.IT 2018
Year: 2018

This paper investigates the fundamental tradeoff between cache size and download time in the (H;r;M;N) combination network, where a server with N files is connected to H relays (without caches) and each of the K:=\binom{H}{r} users (with caches of size M files) is connected to a different subset of r relays. Existing schemes fall within two categories: either use the uncoded symmetric cache placement originally proposed for the shared-link model and design delivery phase dependent on the network topology, or effectively divide the combination network into H independent shared-link networks each serving \binom{H-1}{r-1} users; in either case, the placement phase is independent of network topology. In this paper, a novel strategy is proposed where the coded cache placement is dependent on network topology. The proposed scheme is shown to be information theoretically optimal for large cache size. In addition, when not exactly optimal, the proposed scheme can also outperform existing schemes.
Using Deep Learning for Segmentation and Counting within Microscopy Data
Venue: arXiv cs.CV 2018
Year: 2018

Cell counting is a ubiquitous, yet tedious task that would greatly benefit from automation. From basic biological questions to clinical trials, cell counts provide key quantitative feedback that drive research. Unfortunately, cell counting is most commonly a manual task and can be time-intensive. The task is made even more difficult due to overlapping cells, existence of multiple focal planes, and poor imaging quality, among other factors. Here, we describe a convolutional neural network approach, using a recently described feature pyramid network combined with a VGG-style neural network, for segmenting and subsequent counting of cells in a given microscopy image.
A Feature Clustering Approach Based on Histogram of Oriented Optical Flow and Superpixels
Venue: arXiv cs.CV 2018
Year: 2018

Visual feature clustering is one of the cost-effective approaches to segment objects in videos. However, the assumptions made for developing the existing algorithms prevent them from being used in situations like segmenting an unknown number of static and moving objects under heavy camera movements. This paper addresses the problem by introducing a clustering approach based on superpixels and short-term Histogram of Oriented Optical Flow (HOOF). Salient Dither Pattern Feature (SDPF) is used as the visual feature to track the flow and Simple Linear Iterative Clustering (SLIC) is used for obtaining the superpixels. This new clustering approach is based on merging superpixels by comparing short term local HOOF and a color cue to form high-level semantic segments. The new approach was compared with one of the latest feature clustering approaches based on K-Means in eight-dimensional space and the results revealed that the new approach is better by means of consistency, completeness, and spatial accuracy. Further, the new approach completely solved the problem of not knowing the number of objects in a scene.
Computational International Relations: What Can Programming, Coding and Internet Research Do for the Discipline?
Venue: arXiv cs.CY 2018
Year: 2018

Computational Social Science emerged as a highly technical and popular discipline in the last few years, owing to the substantial advances in communication technology and daily production of vast quantities of personal data. As per capita data production significantly increased in the last decade, both in terms of its size, bytes, as well as its detail, heart rate monitors, Internet connected appliances, smartphones, social scientists ability to extract meaningful social, political and demographic information from digital data also increased. A vast methodological gap exists in computational international relations, or ComInt, which refers to the use of one or a combination of tools such as data mining, natural language processing, automated text analysis, web scraping, geospatial analysis and machine learning to provide larger and better organized data to test more advanced theories of IR. After providing an overview of the potentials of computational IR and how an IR scholar can establish technical proficiency in computer science, such as starting with Python, R, QGis, ArcGIS or Github, this paper will focus on some of the author's works in providing an idea for IR students on how to think about computational IR. The paper argues that computational methods transcend the methodological schism between qualitative and quantitative approaches and form a solid foundation for building truly multi method research design.
RF Energy Harvesting Sensor Networks for Healthcare of Animals: Opportunities and Challenges
Venue: arXiv cs.NI 2018
Year: 2018

In recent years, the radio frequency (RF) energy harvesting technique is considered as a favorable alternative to supply power for the next-generation wireless sensor networks. Due to the features of energy self-sustainability and long lifetime, the energy harvesting sensor network (RF-EHSN) becomes a promising solution to provide smart healthcare services. Nowadays, many energy harvesting based applications have been developed for monitoring the health status of human beings; how to benefit animals, however, has not yet drawn people's attention. This article explores the potential of applying RF-EHSNs to monitoring the health level of animals. The unique challenges and potential solutions at different layers of an RF-EHSN for animals' healthcare service are studied.
Buckling of thin composite plates reinforced with randomly oriented, straight single-walled carbon nanotubes using B3-Spline finite strip method
Venue: arXiv cs.CE 2018
Year: 2018

This paper is devoted to the mechanical buckling analysis of thin composite plates under straight single-walled carbon nanotubes reinforcement with uniform distribution and random orientations. In order to develop the fundamental equations, the B3-Spline finite strip method along with the classical plate theory is employed and the total potential energy is minimized which leads to an eigenvalue problem. For deriving the effective modulus of thin composite plates reinforced with carbon nanotubes, the Mori-Tanaka method is used in which each straight carbon nanotube is modeled as a fiber with transversely isotropic elastic properties. The results of our numerical experiments including the critical buckling loads for rectangular thin composite plates reinforced by carbon nanotubes with various boundary conditions and different volume fractions of nanotubes are provided and the positive effect of using carbon nanotubes reinforcement in mechanical buckling of thin plates is illustrated.
Facial Expression Recognition Based on Complexity Perception Classification Algorithm
Venue: arXiv cs.CV 2018
Year: 2018

Facial expression recognition (FER) has always been a challenging issue in computer vision. The different expressions of emotion and uncontrolled environmental factors lead to inconsistencies in the complexity of FER and variability of between expression categories, which is often overlooked in most facial expression recognition systems. In order to solve this problem effectively, we presented a simple and efficient CNN model to extract facial features, and proposed a complexity perception classification (CPC) algorithm for FER. The CPC algorithm divided the dataset into an easy classification sample subspace and a complex classification sample subspace by evaluating the complexity of facial features that are suitable for classification. The experimental results of our proposed algorithm on Fer2013 and CK-plus datasets demonstrated the algorithm's effectiveness and superiority over other state-of-the-art approaches.
Recover Fine-Grained Spatial Data from Coarse Aggregation
Venue: arXiv cs.NA 2018
Year: 2018

In this paper, we study a new type of spatial sparse recovery problem, that is to infer the fine-grained spatial distribution of certain density data in a region only based on the aggregate observations recorded for each of its subregions. One typical example of this spatial sparse recovery problem is to infer spatial distribution of cellphone activities based on aggregate mobile traffic volumes observed at sparsely scattered base stations. We propose a novel Constrained Spatial Smoothing (CSS) approach, which exploits the local continuity that exists in many types of spatial data to perform sparse recovery via finite-element methods, while enforcing the aggregated observation constraints through an innovative use of the ADMM algorithm. We also improve the approach to further utilize additional geographical attributes. Extensive evaluations based on a large dataset of phone call records and a demographical dataset from the city of Milan show that our approach significantly outperforms various state-of-the-art approaches, including Spatial Spline Regression (SSR).
WRPN & Apprentice: Methods for Training and Inference using Low-Precision Numerics
Venue: arXiv cs.CV 2018
Year: 2018

Today's high performance deep learning architectures involve large models with numerous parameters. Low precision numerics has emerged as a popular technique to reduce both the compute and memory requirements of these large models. However, lowering precision often leads to accuracy degradation. We describe three schemes whereby one can both train and do efficient inference using low precision numerics without hurting accuracy. Finally, we describe an efficient hardware accelerator that can take advantage of the proposed low precision numerics.
Distance Measure Machines
Venue: arXiv cs.LG 2018
Year: 2018

This paper presents a distance-based discriminative framework for learning with probability distributions. Instead of using kernel mean embeddings or generalized radial basis kernels, we introduce embeddings based on dissimilarity of distributions to some reference distributions denoted as templates. Our framework extends the theory of similarity of Balcan et al. (2008) to the population distribution case and we show that, for some learning problems, some dissimilarity on distribution achieves low-error linear decision functions with high probability. Our key result is to prove that the theory also holds for empirical distributions. Algorithmically, the proposed approach consists in computing a mapping based on pairwise dissimilarity where learning a linear decision function is amenable. Our experimental results show that the Wasserstein distance embedding performs better than kernel mean embeddings and computing Wasserstein distance is far more tractable than estimating pairwise Kullback-Leibler divergence of empirical distributions.
Strong Subgraph $k$-connectivity
Venue: arXiv cs.DM 2018
Year: 2018

Generalized connectivity introduced by Hager (1985) has been studied extensively in undirected graphs and become an established area in undirected graph theory. For connectivity problems, directed graphs can be considered as generalizations of undirected graphs. In this paper, we introduce a natural extension of generalized $k$-connectivity of undirected graphs to directed graphs (we call it strong subgraph $k$-connectivity) by replacing connectivity with strong connectivity. We prove NP-completeness results and the existence of polynomial algorithms. We show that strong subgraph $k$--connectivity is, in a sense, harder to compute than generalized $k$-connectivity. However, strong subgraph $k$-connectivity can be computed in polynomial time for semicomplete digraphs and symmetric digraphs. We also provide sharp bounds on strong subgraph $k$-connectivity and pose some open questions.
Hybrid Beamforming Design and Performance with Imperfect Phase Shifters in Multiuser Millimeter Wave Systems
Venue: arXiv cs.IT 2018
Year: 2018

Hybrid beamforming (HBF) includes analog beamforming with phase shifted array in RF domain and digital beamforming in baseband domain. Phase shifted array is usually made up with a large amount of phase shifters. Limited to the manufacturing techniques, phase shifters are unavoidable to have phaseshifting error and gain error. In the paper we study the influence of imperfect phase shifters upon the performance of multiuser mmWave massive MIMO systems1 with the wireless channel modeled by Rice fading. We derive the upper bound of the achievable sum rate with imperfect phase shifters, which can be very tight when the number of the antennas at the base station is much larger than the number of users. Results show that there is a performance ceiling due to phase-shifting error and gain error. Then we propose a novel channel estimation and hybrid beamforming method to settle this problem with low training overhead. It performs well when the channel paths are few and the channel Rician K-factor is large, which can be easily satisfied in outdoor mmWave communication environment. We further make a tradeoff between the performance and the training overhead so that the algorithm can work well in more kinds of propagation environment.
Spatial Lobes Division Based Low Complexity Hybrid Precoding and Diversity Combining for mmWave IoT Systems
Venue: arXiv cs.IT 2018
Year: 2018

This paper focuses on the design of low complexity hybrid analog/digital precoding and diversity combining in millimeter wave (mmWave) Internet of things (IoT) systems. Firstly, by exploiting the sparseness property of the mmWave in the angular domain, we propose a spatial lobes division (SLD) to group the total paths of the mmWave channel into several spatial lobes, where the paths in each spatial lobe form a low-rank sub-channel. Secondly, based on the SLD operation, we propose a low complexity hybrid precoding scheme, named HYP-SLD. Specifically, for each low-rank sub-channel, we formulate the hybrid precoding design as a sparse reconstruction problem and separately maximizes the spectral efficiency. Finally, we further propose a maximum ratio combining based diversity combining scheme, named HYP-SLD-MRC, to improve the bit error rate (BER) performance of mmWave IoT systems. Simulation results demonstrate that, the proposed HYP-SLD scheme significantly reduces the complexity of the classic orthogonal matching pursuit (OMP) scheme. Moreover, the proposed HYP-SLD-MRC scheme achieves great improvement in BER performance compared with the fully digital precoding scheme.
Detecting Volcano Deformation in InSAR using Deep learning
Venue: arXiv cs.CV 2018
Year: 2018

Globally 800 million people live within 100 km of a volcano and currently 1500 volcanoes are considered active, but half of these have no ground-based monitoring. Alternatively, satellite radar (InSAR) can be employed to observe volcanic ground deformation, which has shown a significant statistical link to eruptions. Modern satellites provide large coverage with high resolution signals, leading to huge amounts of data. The explosion in data has brought major challenges associated with timely dissemination of information and distinguishing volcano deformation patterns from noise, which currently relies on manual inspection. Moreover, volcano observatories still lack expertise to exploit satellite datasets, particularly in developing countries. This paper presents a novel approach to detect volcanic ground deformation automatically from wrapped-phase InSAR images. Convolutional neural networks (CNN) are employed to detect unusual patterns within the radar data.
Optimal Accuracy-Privacy Trade-Off for Secure Multi-Party Computations
Venue: arXiv cs.CR 2018
Year: 2018

The purpose of Secure Multi-Party Computation is to enable protocol participants to compute a public function of their private inputs while keeping their inputs secret, without resorting to any trusted third party. However, opening the public output of such computations inevitably reveals some information about the private inputs. We propose a measure generalising both Renyi entropy and g-entropy so as to quantify this information leakage. In order to control and restrain such information flows, we introduce the notion of function substitution which replaces the computation of a function that reveals sensitive information with that of an approximate function. We exhibit theoretical bounds for the privacy gains that this approach provides and experimentally show that this enhances the confidentiality of the inputs while controlling the distortion of computed output values. Finally, we investigate the inherent compromise between accuracy of computation and privacy of inputs and we demonstrate how to realise such optimal trade-offs.