OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Diffusion on Region Manifolds: Recovering Small Objects with Compact CNN Representations
Venue: arXiv cs.CV 2019
Year: 2019

Query expansion is a popular method to improve the quality of image retrieval with both conventional and CNN representations. It has been so far limited to global image similarity. This work focuses on diffusion, a mechanism that captures the image manifold in the feature space. The diffusion is carried out on descriptors of overlapping image regions rather than on a global image descriptor like in previous approaches. An efficient off-line stage allows optional reduction in the number of stored regions. In the on-line stage, the proposed handling of unseen queries in the indexing stage removes additional computation to adjust the precomputed data. We perform diffusion through a sparse linear system solver, yielding practical query times well below one second. Experimentally, we observe a significant boost in performance of image retrieval with compact CNN descriptors on standard benchmarks, especially when the query object covers only a small part of the image. Small objects have been a common failure case of CNN-based retrieval.
Slow links, fast links, and the cost of gossip
Venue: arXiv cs.DC 2019
Year: 2019

Consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e., sending a message from one node to another takes some amount of time. We first generalize the idea of conductance to weighted graphs by defining $ϕ_*$ to be the "critical conductance" and $\ell_*$ to be the "critical latency". One goal of this paper is to argue that $ϕ_*$ characterizes the connectivity of a weighted graph with latencies in much the same way that conductance characterizes the connectivity of unweighted graphs. We give near tight lower and upper bounds on the problem of information dissemination, up to polylogarithmic factors. Specifically, we show that in a graph with (weighted) diameter $D$ (with latencies as weights) and maximum degree $Δ$, any information dissemination algorithm requires at least $Ω(\min(D+Δ, \ell_*/ϕ_*))$ time % in the worst case. We show several variants of the lower bound (e.g., for graphs with small diameter, graphs with small max-degree, etc.) by reduction to a simple combinatorial game. We then give nearly matching algorithms, showing that information dissemination can be solved in $O(\min((D+Δ)\log^3{n}, (\ell_*/ϕ_*)\log n)$ time. This is achieved by combining two cases. We show that the classical push-pull algorithm is (near) optimal when the diameter or the maximum degree is large. For the case where the diameter and the maximum degree are small, we give an alternative strategy in which we first discover the latencies and then use an algorithm for known latencies based on a weighted spanner construction. (Our algorithms are within polylogarithmic factors of being tight both for known and unknown latencies.)
The polysemy of the words that children learn over time
Venue: arXiv cs.CL 2019
Year: 2019

Here we study polysemy as a potential learning bias in vocabulary learning in children. Words of low polysemy could be preferred as they reduce the disambiguation effort for the listener. However, such preference could be a side-effect of another bias: the preference of children for nouns in combination with the lower polysemy of nouns with respect to other part-of-speech categories. Our results show that mean polysemy in children increases over time in two phases, i.e. a fast growth till the 31st month followed by a slower tendency towards adult speech. In contrast, this evolution is not found in adults interacting with children. This suggests that children have a preference for non-polysemous words in their early stages of vocabulary acquisition. Interestingly, the evolutionary pattern described above weakens when controlling for syntactic category (noun, verb, adjective or adverb) but it does not disappear completely, suggesting that it could result from acombination of a standalone bias for low polysemy and a preference for nouns.
Factored Contextual Policy Search with Bayesian Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Scarce data is a major challenge to scaling robot learning to truly complex tasks, as we need to generalize locally learned policies over different "contexts". Bayesian optimization approaches to contextual policy search (CPS) offer data-efficient policy learning that generalize over a context space. We propose to improve data-efficiency by factoring typically considered contexts into two components: target-type contexts that correspond to a desired outcome of the learned behavior, e.g. target position for throwing a ball; and environment type contexts that correspond to some state of the environment, e.g. initial ball position or wind speed. Our key observation is that experience can be directly generalized over target-type contexts. Based on that we introduce Factored Contextual Policy Search with Bayesian Optimization for both passive and active learning settings. Preliminary results show faster policy generalization on a simulated toy problem. A full paper extension is available at arXiv:1904.11761
Sub-Linear Privacy-Preserving Near-Neighbor Search
Venue: arXiv cs.CR 2019
Year: 2019

In Near-Neighbor Search (NNS), a new client queries a database (held by a server) for the most similar data (near-neighbors) given a certain similarity metric. The Privacy-Preserving variant (PP-NNS) requires that neither server nor the client shall learn information about the other party's data except what can be inferred from the outcome of NNS. The overwhelming growth in the size of current datasets and the lack of a truly secure server in the online world render the existing solutions impractical; either due to their high computational requirements or non-realistic assumptions which potentially compromise privacy. PP-NNS having query time {\it sub-linear} in the size of the database has been suggested as an open research direction by Li et al. (CCSW'15). In this paper, we provide the first such algorithm, called Secure Locality Sensitive Indexing (SLSI) which has a sub-linear query time and the ability to handle honest-but-curious parties. At the heart of our proposal lies a secure binary embedding scheme generated from a novel probabilistic transformation over locality sensitive hashing family. We provide information theoretic bound for the privacy guarantees and support our theoretical claims using substantial empirical evidence on real-world datasets.
Random Spanning Trees for Expanders, Sparsifiers, and Virtual Network Security
Venue: arXiv cs.NI 2019
Year: 2019

This work describes probabilistic methods for utilizing random spanning trees generated via a random walk process. Goyal et al. showed that the union of random spanning trees approximates the expansion of every cut of a graph. First, we generalize the method by Goyal et al. for weighted graphs and show that it is possible to approximate the expansion of every cut in a weighted graph with the union of random spanning trees generated by a random walk on a weighted graph. Second, we show that our union of random spanning trees is a spectral sparsifier of the graph. Moreover, we show that $O(\log n /ε^2)$ random spanning trees are required in order to spectrally approximate a bounded degree graph. This result closes a previously open question on the number of random spanning trees required for saprsification. Third, we show that our random spanning trees based construction provides security features for virtual networks, in the context of Software-Defined Networking. Network virtualization coupled with Software-Defined Networking allows new on-demand management capabilities. We demonstrate such a service, namely, on-demand efficient monitoring or anonymity. The proposed service is based on network virtualization of expanders or sparsifiers over the physical network. The defined virtual (or overlay) communication graphs coupled with a multi-hop extension of Valiant randomization based routing lets us monitor the entire traffic in the network, with a very few monitoring nodes. We propose methods that theoretically improve services provided by existing monitoring or anonymity networks, and optimize the degree of monitoring or anonymity.
Image biomarker standardisation initiative
Venue: arXiv cs.CV 2019
Year: 2019

The image biomarker standardisation initiative (IBSI) is an independent international collaboration which works towards standardising the extraction of image biomarkers from acquired imaging for the purpose of high-throughput quantitative image analysis (radiomics). Lack of reproducibility and validation of high-throughput quantitative image analysis studies is considered to be a major challenge for the field. Part of this challenge lies in the scantiness of consensus-based guidelines and definitions for the process of translating acquired imaging into high-throughput image biomarkers. The IBSI therefore seeks to provide image biomarker nomenclature and definitions, benchmark data sets, and benchmark values to verify image processing and image biomarker calculations, as well as reporting guidelines, for high-throughput image analysis.
Robust Classification of Graph-Based Data
Venue: arXiv cs.LG 2019
Year: 2019

A graph-based classification method is proposed for semi-supervised learning in the case of Euclidean data and for classification in the case of graph data. Our manifold learning technique is based on a convex optimization problem involving a convex quadratic regularization term and a concave quadratic loss function with a trade-off parameter carefully chosen so that the objective function remains convex. As shown empirically, the advantage of considering a concave loss function is that the learning problem becomes more robust in the presence of noisy labels. Furthermore, the loss function considered here is then more similar to a classification loss while several other methods treat graph-based classification problems as regression problems.
Joint attack detection and secure state estimation of cyber-physical systems
Venue: arXiv cs.SY 2019
Year: 2019

This paper deals with secure state estimation of cyber-physical systems subject to switching (on/off) attack signals and injection of fake packets (via either packet substitution or insertion of extra packets). The random set paradigm is adopted in order to model, via Random Finite Sets (RFSs), the switching nature of both system attacks and the injection of fake measurements. The problem of detecting an attack on the system and jointly estimating its state, possibly in the presence of fake measurements, is then formulated and solved in the Bayesian framework for systems with and without direct feedthrough of the attack input to the output. This leads to the analytical derivation of a hybrid Bernoulli filter (HBF) that updates in real-time the joint posterior density of a Bernoulli attack RFS and of the state vector. A closed-form Gaussian-mixture implementation of the proposed hybrid Bernoulli filter is fully derived in the case of invertible direct feedthrough. Finally, the effectiveness of the developed tools for joint attack detection and secure state estimation is tested on two case-studies concerning a benchmark system for unknown input estimation and a standard IEEE power network application.
Cofree coalgebras and differential linear logic
Venue: arXiv cs.LO 2019
Year: 2019

We prove that the semantics of intuitionistic linear logic in vector spaces which uses cofree coalgebras is also a model of differential linear logic, and that the Cartesian closed category of cofree coalgebras is a model of the simply-typed differential lambda calculus.
Neural Personalized Response Generation as Domain Adaptation
Venue: arXiv cs.CL 2019
Year: 2019

In this paper, we focus on the personalized response generation for conversational systems. Based on the sequence to sequence learning, especially the encoder-decoder framework, we propose a two-phase approach, namely initialization then adaptation, to model the responding style of human and then generate personalized responses. For evaluation, we propose a novel human aided method to evaluate the performance of the personalized response generation models by online real-time conversation and offline human judgement. Moreover, the lexical divergence of the responses generated by the 5 personalized models indicates that the proposed two-phase approach achieves good results on modeling the responding style of human and generating personalized responses for the conversational systems.
Limited individual attention and online virality of low-quality information
Venue: arXiv cs.SI 2019
Year: 2019

Social media are massive marketplaces where ideas and news compete for our attention. Previous studies have shown that quality is not a necessary condition for online virality and that knowledge about peer choices can distort the relationship between quality and popularity. However, these results do not explain the viral spread of low-quality information, such as the digital misinformation that threatens our democracy. We investigate quality discrimination in a stylized model of online social network, where individual agents prefer quality information, but have behavioral limitations in managing a heavy flow of information. We measure the relationship between the quality of an idea and its likelihood to become prevalent at the system level. We find that both information overload and limited attention contribute to a degradation in the market's discriminative power. A good tradeoff between discriminative power and diversity of information is possible according to the model. However, calibration with empirical data characterizing information load and finite attention in real social media reveals a weak correlation between quality and popularity of information. In these realistic conditions, the model predicts that high-quality information has little advantage over low-quality information.
The empirical Christoffel function with applications in data analysis
Venue: arXiv cs.LG 2019
Year: 2019

We illustrate the potential applications in machine learning of the Christoffel function, or more precisely, its empirical counterpart associated with a counting measure uniformly supported on a finite set of points. Firstly, we provide a thresholding scheme which allows to approximate the support of a measure from a finite subset of its moments with strong asymptotic guaranties. Secondly, we provide a consistency result which relates the empirical Christoffel function and its population counterpart in the limit of large samples. Finally, we illustrate the relevance of our results on simulated and real world datasets for several applications in statistics and machine learning: (a) density and support estimation from finite samples, (b) outlier and novelty detection and (c) affine matching.
On the Sample Complexity of Graphical Model Selection for Non-Stationary Processes
Venue: arXiv cs.LG 2019
Year: 2019

We characterize the sample size required for accurate graphical model selection from non-stationary samples. The observed data is modeled as a vector-valued zero-mean Gaussian random process whose samples are uncorrelated but have different covariance matrices. This model contains as special cases the standard setting of i.i.d. samples as well as the case of samples forming a stationary or underspread (non-stationary) processes. More generally, our model applies to any process model for which an efficient decorrelation can be obtained. By analyzing a particular model selection method, we derive a sufficient condition on the required sample size for accurate graphical model selection based on non-stationary data.
Coded Computation over Heterogeneous Clusters
Venue: arXiv cs.DC 2019
Year: 2019

In large-scale distributed computing clusters, such as Amazon EC2, there are several types of "system noise" that can result in major degradation of performance: bottlenecks due to limited communication bandwidth, latency due to straggler nodes, etc. On the other hand, these systems enjoy abundance of redundancy - a vast number of computing nodes and large storage capacity. There have been recent results that demonstrate the impact of coding for efficient utilization of computation and storage redundancy to alleviate the effect of stragglers and communication bottlenecks in homogeneous clusters. In this paper, we focus on general heterogeneous distributed computing clusters consisting of a variety of computing machines with different capabilities. We propose a coding framework for speeding up distributed computing in heterogeneous clusters by trading redundancy for reducing the latency of computation. In particular, we propose Heterogeneous Coded Matrix Multiplication (HCMM) algorithm for performing distributed matrix multiplication over heterogeneous clusters that is provably asymptotically optimal for a broad class of processing time distributions. Moreover, we show that HCMM is unboundedly faster than any uncoded scheme. To demonstrate practicality of HCMM, we carry out experiments over Amazon EC2 clusters where HCMM is found to be up to $61\%$, $46\%$ and $36\%$ respectively faster than three benchmark load allocation schemes - Uniform Uncoded, Load-balanced Uncoded, and Uniform Coded. Additionally, we provide a generalization to the problem of optimal load allocation in heterogeneous settings, where we take into account the monetary costs associated with the clusters. We argue that HCMM is asymptotically optimal for budget-constrained scenarios as well, and we develop a heuristic algorithm for (HCMM) load allocation for budget-limited computation tasks.
Experimentally-based Cross-layer Optimization for Distributed Wireless Body-to-body Networks
Venue: arXiv cs.NI 2019
Year: 2019

We investigate cross-layer optimization to route information across distributed wireless body-to-body networks, based on real-life experimental measurements. At the network layer, the best possible route is selected according to channel state information (e.g., expected transmission count, hop count) from the physical layer. Two types of dynamic routing are applied: shortest path routing (SPR), and cooperative multi-path routing (CMR) associated with selection combining. An open-access experimental dataset incorporating `everyday' mixed-activities is used for analyzing and comparing the cross-layer optimization with different wireless sensor network protocols (i.e., ORPL, LOADng). Negligible packet error rate is achieved by applying CMR and SPR techniques with reasonably sensitive receivers. Moreover, at 10% outage probability, CMR gains up to 8, 7, and 6 dB improvements over ORPL, SPR, and LOADng, respectively. We show that CMR achieves the highest throughput (packets/s) while providing acceptable amount of average end-to-end delay (47.5 ms), at -100 dBm receive sensitivity. The use of alternate paths in CMR reduces retransmissions and increases packet success rate, which significantly reduces the maximum amount of end-to-end delay and energy consumption for CMR with respect to other protocols. It is also shown that the combined channel gains across SPR and CMR are gamma and Rician distributed, correspondingly.
On the Information Dimension of Stochastic Processes
Venue: arXiv cs.IT 2019
Year: 2019

In 1959, Rényi proposed the information dimension and the $d$-dimensional entropy to measure the information content of general random variables. This paper proposes a generalization of information dimension to stochastic processes by defining the information dimension rate as the entropy rate of the uniformly-quantized stochastic process divided by minus the logarithm of the quantizer step size $1/m$ in the limit as $m\to\infty$. It is demonstrated that the information dimension rate coincides with the rate-distortion dimension, defined as twice the rate-distortion function $R(D)$ of the stochastic process divided by $-\log(D)$ in the limit as $D\downarrow 0$. It is further shown that, among all multivariate stationary processes with a given (matrix-valued) spectral distribution function (SDF), the Gaussian process has the largest information dimension rate, and that the information dimension rate of multivariate stationary Gaussian processes is given by the average rank of the derivative of the SDF. The presented results reveal that the fundamental limits of almost zero-distortion recovery via compressible signal pursuit and almost lossless analog compression are different in general.
Optimal Experimental Design of Field Trials using Differential Evolution
Venue: arXiv cs.NE 2019
Year: 2019

When setting up field experiments, to test and compare a range of genotypes (e.g. maize hybrids), it is important to account for any possible field effect that may otherwise bias performance estimates of genotypes. To do so, we propose a model-based method aimed at optimizing the allocation of the tested genotypes and checks between fields and placement within field, according to their kinship. This task can be formulated as a combinatorial permutation-based problem. We used Differential Evolution concept to solve this problem. We then present results of optimal strategies for between-field and within-field placements of genotypes and compare them to existing optimization strategies, both in terms of convergence time and result quality. The new algorithm gives promising results in terms of convergence and search space exploration.
Measuring Motivations of Crowdworkers: The Multidimensional Crowdworker Motivation Scale
Venue: arXiv cs.SI 2019
Year: 2019

Crowd employment is a new form of short-term and flexible employment which has emerged during the past decade. In order to understand this new form of employment, it is crucial to illuminate the underlying motivations of the workforce involved in it. This paper introduces the Multidimensional Crowdworker Motivation Scale (MCMS), a scale for measuring the motivation of crowdworkers on micro-task platforms. The MCMS is theoretically grounded in self-determination theory and tailored specifically to the context of paid crowdsourced micro-labor. The scale measures the motivation of crowdworkers along six motivational dimensions, ranging from amotivation to intrinsic motivation. We validated the MCMS on data collected in ten countries and three income groups. Factor analyses demonstrated that the MCMS's six dimensions showed good model fit, validity, and reliability. Furthermore, our measurement invariance tests showed that motivations measured with the MCMS are comparable across countries and income groups, and we present a first cross-country comparison of crowdworker motivations. This work constitutes an important first step towards understanding the motivations of the international crowd workforce.
Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
Venue: arXiv cs.LG 2019
Year: 2019

In recent years, stochastic variance reduction algorithms have attracted considerable attention for minimizing the average of a large but finite number of loss functions. This paper proposes a novel Riemannian extension of the Euclidean stochastic variance reduced gradient (R-SVRG) algorithm to a manifold search space. The key challenges of averaging, adding, and subtracting multiple gradients are addressed with retraction and vector transport. For the proposed algorithm, we present a global convergence analysis with a decaying step size as well as a local convergence rate analysis with a fixed step size under some natural assumptions. In addition, the proposed algorithm is applied to the computation problem of the Riemannian centroid on the symmetric positive definite (SPD) manifold as well as the principal component analysis and low-rank matrix completion problems on the Grassmann manifold. The results show that the proposed algorithm outperforms the standard Riemannian stochastic gradient descent algorithm in each case.