OpenRaiser/Intern-Atlas huggingface dataset:
TribeFlow: Mining & Predicting User Trajectories
Venue: arXiv cs.SI 2016
Year: 2016

Which song will Smith listen to next? Which restaurant will Alice go to tomorrow? Which product will John click next? These applications have in common the prediction of user trajectories that are in a constant state of flux over a hidden network (e.g. website links, geographic location). What users are doing now may be unrelated to what they will be doing in an hour from now. Mindful of these challenges we propose TribeFlow, a method designed to cope with the complex challenges of learning personalized predictive models of non-stationary, transient, and time-heterogeneous user trajectories. TribeFlow is a general method that can perform next product recommendation, next song recommendation, next location prediction, and general arbitrary-length user trajectory prediction without domain-specific knowledge. TribeFlow is more accurate and up to 413x faster than top competitors.
Efficient Algorithms with Asymmetric Read and Write Costs
Venue: arXiv cs.DS 2016
Year: 2016

In several emerging technologies for computer memory (main memory), the cost of reading is significantly cheaper than the cost of writing. Such asymmetry in memory costs poses a fundamentally different model from the RAM for algorithm design. In this paper we study lower and upper bounds for various problems under such asymmetric read and write costs. We consider both the case in which all but $O(1)$ memory has asymmetric cost, and the case of a small cache of symmetric memory. We model both cases using the $(M,ω)$-ARAM, in which there is a small (symmetric) memory of size $M$ and a large unbounded (asymmetric) memory, both random access, and where reading from the large memory has unit cost, but writing has cost $ω\gg 1$. For FFT and sorting networks we show a lower bound cost of $Ω(ωn\log_{ωM} n)$, which indicates that it is not possible to achieve asymptotic improvements with cheaper reads when $ω$ is bounded by a polynomial in $M$. Also, there is an asymptotic gap (of $\min(ω,\log n)/\log(ωM)$) between the cost of sorting networks and comparison sorting in the model. This contrasts with the RAM, and most other models. We also show a lower bound for computations on an $n\times n$ diamond DAG of $Ω(ωn^2/M)$ cost, which indicates no asymptotic improvement is achievable with fast reads. However, we show that for the edit distance problem (and related problems), which would seem to be a diamond DAG, there exists an algorithm with only $O(ωn^2/(M\min(ω^{1/3},M^{1/2})))$ cost. To achieve this we make use of a "path sketch" technique that is forbidden in a strict DAG computation. Finally, we show several interesting upper bounds for shortest path problems, minimum spanning trees, and other problems. A common theme in many of the upper bounds is to have redundant computation to tradeoff between reads and writes.
Image-Based Correction of Continuous and Discontinuous Non-Planar Axial Distortion in Serial Section Microscopy
Venue: arXiv cs.CV 2016
Year: 2016

Motivation: Serial section microscopy is an established method for detailed anatomy reconstruction of biological specimen. During the last decade, high resolution electron microscopy (EM) of serial sections has become the de-facto standard for reconstruction of neural connectivity at ever increasing scales (EM connectomics). In serial section microscopy, the axial dimension of the volume is sampled by physically removing thin sections from the embedded specimen and subsequently imaging either the block-face or the section series. This process has limited precision leading to inhomogeneous non-planar sampling of the axial dimension of the volume which, in turn, results in distorted image volumes. This includes that section series may be collected and imaged in unknown order. Results: We developed methods to identify and correct these distortions through image-based signal analysis without any additional physical apparatus or measurements. We demonstrate the efficacy of our methods in proof of principle experiments and application to real world problems. Availability and Implementation: We made our work available as libraries for the ImageJ distribution Fiji and for deployment in a high performance parallel computing environment. Our sources are open and available at http://github.com/saalfeldla/section-sort, http://github.com/saalfeldlab/em-thickness-estimation, and http://github.com/saalfeldlab/z-spacing-spark. Contact: saalfelds@janelia.hhmi.org
Asymptotic Approximations for TCP Compound
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we derive an approximation for throughput of TCP Compound connections under random losses. Throughput expressions for TCP Compound under a deterministic loss model exist in the literature. These are obtained assuming the window sizes are continuous, i.e., a fluid behaviour is assumed. We validate this model theoretically. We show that under the deterministic loss model, the TCP window evolution for TCP Compound is periodic and is independent of the initial window size. We then consider the case when packets are lost randomly and independently of each other. We discuss Markov chain models to analyze performance of TCP in this scenario. We use insights from the deterministic loss model to get an appropriate scaling for the window size process and show that these scaled processes, indexed by p, the packet error rate, converge to a limit Markov chain process as p goes to 0. We show the existence and uniqueness of the stationary distribution for this limit process. Using the stationary distribution for the limit process, we obtain approximations for throughput, under random losses, for TCP Compound when packet error rates are small. We compare our results with ns2 simulations which show a good match.
Learning in Auctions: Regret is Hard, Envy is Easy
Venue: arXiv cs.GT 2016
Year: 2016

A line of recent work provides welfare guarantees of simple combinatorial auction formats, such as selling m items via simultaneous second price auctions (SiSPAs) (Christodoulou et al. 2008, Bhawalkar and Roughgarden 2011, Feldman et al. 2013). These guarantees hold even when the auctions are repeatedly executed and players use no-regret learning algorithms. Unfortunately, off-the-shelf no-regret algorithms for these auctions are computationally inefficient as the number of actions is exponential. We show that this obstacle is insurmountable: there are no polynomial-time no-regret algorithms for SiSPAs, unless RP$\supseteq$ NP, even when the bidders are unit-demand. Our lower bound raises the question of how good outcomes polynomially-bounded bidders may discover in such auctions. To answer this question, we propose a novel concept of learning in auctions, termed "no-envy learning." This notion is founded upon Walrasian equilibrium, and we show that it is both efficiently implementable and results in approximately optimal welfare, even when the bidders have fractionally subadditive (XOS) valuations (assuming demand oracles) or coverage valuations (without demand oracles). No-envy learning outcomes are a relaxation of no-regret outcomes, which maintain their approximate welfare optimality while endowing them with computational tractability. Our results extend to other auction formats that have been studied in the literature via the smoothness paradigm. Our results for XOS valuations are enabled by a novel Follow-The-Perturbed-Leader algorithm for settings where the number of experts is infinite, and the payoff function of the learner is non-linear. This algorithm has applications outside of auction settings, such as in security games. Our result for coverage valuations is based on a novel use of convex rounding schemes and a reduction to online convex optimization.
Complexity of Steiner Tree in Split Graphs - Dichotomy Results
Venue: arXiv cs.DM 2016
Year: 2016

Given a connected graph $G$ and a terminal set $R \subseteq V(G)$, {\em Steiner tree} asks for a tree that includes all of $R$ with at most $r$ edges for some integer $r \geq 0$. It is known from [ND12,Garey et. al \cite{steinernpc}] that Steiner tree is NP-complete in general graphs. {\em Split graph} is a graph which can be partitioned into a clique and an independent set. K. White et. al \cite{white} has established that Steiner tree in split graphs is NP-complete. In this paper, we present an interesting dichotomy: we show that Steiner tree on $K_{1,4}$-free split graphs is polynomial-time solvable, whereas, Steiner tree on $K_{1,5}$-free split graphs is NP-complete. We investigate $K_{1,4}$-free and $K_{1,3}$-free (also known as claw-free) split graphs from a structural perspective. Further, using our structural study, we present polynomial-time algorithms for Steiner tree in $K_{1,4}$-free and $K_{1,3}$-free split graphs. Although, polynomial-time solvability of $K_{1,3}$-free split graphs is implied from $K_{1,4}$-free split graphs, we wish to highlight our structural observations on $K_{1,3}$-free split graphs which may be used in other combinatorial problems.
Convolutional Neural Network for Stereotypical Motor Movement Detection in Autism
Venue: arXiv cs.NE 2016
Year: 2016

Autism Spectrum Disorders (ASDs) are often associated with specific atypical postural or motor behaviors, of which Stereotypical Motor Movements (SMMs) have a specific visibility. While the identification and the quantification of SMM patterns remain complex, its automation would provide support to accurate tuning of the intervention in the therapy of autism. Therefore, it is essential to develop automatic SMM detection systems in a real world setting, taking care of strong inter-subject and intra-subject variability. Wireless accelerometer sensing technology can provide a valid infrastructure for real-time SMM detection, however such variability remains a problem also for machine learning methods, in particular whenever handcrafted features extracted from accelerometer signal are considered. Here, we propose to employ the deep learning paradigm in order to learn discriminating features from multi-sensor accelerometer signals. Our results provide preliminary evidence that feature learning and transfer learning embedded in the deep architecture achieve higher accurate SMM detectors in longitudinal scenarios.
Non-deterministic self-assembly of two tile types on a lattice
Venue: arXiv cs.ET 2016
Year: 2016

Self-assembly is ubiquitous in nature, particularly in biology, where it underlies the formation of protein quaternary structure and protein aggregation. Quaternary structure assembles deterministically and performs a wide range of important functions in the cell, whereas protein aggregation is the hallmark of a number of diseases and represents a non-deterministic self-assembly process. Here we build on previous work on a lattice model of deterministic self-assembly to investigate non-deterministic self-assembly of single lattice tiles and mixtures of two tiles at varying relative concentrations. Despite limiting the simplicity of the model to two interface types, which results in 13 topologically distinct single tiles and 106 topologically distinct sets of two tiles, we observe a wide variety of concentration-dependent behaviours. Several two-tile sets display critical behaviours in form of a sharp transition from bound to unbound structures as the relative concentration of one tile to another increases. Other sets exhibit gradual monotonic changes in structural density, or non-monotonic changes, while again others show no concentration dependence at all. We catalogue this extensive range of behaviours and present a model that provides a reasonably good estimate of the critical concentrations for a subset of the critical transitions. In addition we show that the structures resulting from these tile sets are fractal, with one of two different fractal dimensions.
OmniShare: Securely Accessing Encrypted Cloud Storage from Multiple Authorized Devices
Venue: arXiv cs.CR 2016
Year: 2016

Cloud storage services like Dropbox and Google Drive are widely used by individuals and businesses. Two attractive features of these services are 1) the automatic synchronization of files between multiple client devices and 2) the possibility to share files with other users. However, privacy of cloud data is a growing concern for both individuals and businesses. Encrypting data on the client-side before uploading it is an effective privacy safeguard, but it requires all client devices to have the decryption key. Current solutions derive these keys solely from user-chosen passwords, which have low entropy and are easily guessed. We present OmniShare, the first scheme to allow client-side encryption with high-entropy keys whilst providing an intuitive key distribution mechanism to enable access from multiple client devices. Instead of passwords, we use low bandwidth uni-directional out-of-band (OOB) channels, such as QR codes, to authenticate new devices. To complement these OOB channels, the cloud storage itself is used as a communication channel between devices in our protocols. We rely on a directory-based key hierarchy with individual file keys to limit the consequences of key compromise and allow efficient sharing of files without requiring re-encryption. OmniShare is open source software and currently available for Android and Windows with other platforms in development. We describe the design and implementation of OmniShare, and explain how we evaluated its security using formal methods, its performance via real-world benchmarks, and its usability through a cognitive walkthrough.
Deep Recurrent Neural Networks for Sequential Phenotype Prediction in Genomics
Venue: arXiv cs.NE 2016
Year: 2016

In analyzing of modern biological data, we are often dealing with ill-posed problems and missing data, mostly due to high dimensionality and multicollinearity of the dataset. In this paper, we have proposed a system based on matrix factorization (MF) and deep recurrent neural networks (DRNNs) for genotype imputation and phenotype sequences prediction. In order to model the long-term dependencies of phenotype data, the new Recurrent Linear Units (ReLU) learning strategy is utilized for the first time. The proposed model is implemented for parallel processing on central processing units (CPUs) and graphic processing units (GPUs). Performance of the proposed model is compared with other training algorithms for learning long-term dependencies as well as the sparse partial least square (SPLS) method on a set of genotype and phenotype data with 604 samples, 1980 single-nucleotide polymorphisms (SNPs), and two traits. The results demonstrate performance of the ReLU training algorithm in learning long-term dependencies in RNNs.
Norm minimized Scattering Data from Intensity Spectra
Venue: arXiv cs.IT 2016
Year: 2016

We apply the $l_1$ minimizing technique of compressive sensing (CS) to non-linear quadratic observations. For the example of coherent X-ray scattering we provide the formulae for a Kalman filter approach to quadratic CS and show how to reconstruct the scattering data from their spatial intensity distribution.
Multiple Instance Dictionary Learning using Functions of Multiple Instances
Venue: arXiv cs.CV 2016
Year: 2016

A multiple instance dictionary learning method using functions of multiple instances (DL-FUMI) is proposed to address target detection and two-class classification problems with inaccurate training labels. Given inaccurate training labels, DL-FUMI learns a set of target dictionary atoms that describe the most distinctive and representative features of the true positive class as well as a set of nontarget dictionary atoms that account for the shared information found in both the positive and negative instances. Experimental results show that the estimated target dictionary atoms found by DL-FUMI are more representative prototypes and identify better discriminative features of the true positive class than existing methods in the literature. DL-FUMI is shown to have significantly better performance on several target detection and classification problems as compared to other multiple instance learning (MIL) dictionary learning algorithms on a variety of MIL problems.
Co-word Maps and Topic Modeling: A Comparison Using Small and Medium-Sized Corpora (n < 1000)
Venue: arXiv cs.DL 2016
Year: 2016

Induced by "big data," "topic modeling" has become an attractive alternative to mapping co-words in terms of co-occurrences and co-absences using network techniques. Does topic modeling provide an alternative for co-word mapping in research practices using moderately sized document collections? We return to the word/document matrix using first a single text with a strong argument ("The Leiden Manifesto") and then upscale to a sample of moderate size (n = 687) to study the pros and cons of the two approaches in terms of the resulting possibilities for making semantic maps that can serve an argument. The results from co-word mapping (using two different routines) versus topic modeling are significantly uncorrelated. Whereas components in the co-word maps can easily be designated, the topic models provide sets of words that are very differently organized. In these samples, the topic models seem to reveal similarities other than semantic ones (e.g., linguistic ones). In other words, topic modeling does not replace co-word mapping in small and medium-sized sets; but the paper leaves open the possibility that topic modeling would work well for the semantic mapping of large sets.
Asynchronous Decentralized 20 Questions for Adaptive Search
Venue: arXiv cs.MA 2016
Year: 2016

This paper considers the problem of adaptively searching for an unknown target using multiple agents connected through a time-varying network topology. Agents are equipped with sensors capable of fast information processing, and we propose a decentralized collaborative algorithm for controlling their search given noisy observations. Specifically, we propose decentralized extensions of the adaptive query-based search strategy that combines elements from the 20 questions approach and social learning. Under standard assumptions on the time-varying network dynamics, we prove convergence to correct consensus on the value of the parameter as the number of iterations go to infinity. The convergence analysis takes a novel approach using martingale-based techniques combined with spectral graph theory. Our results establish that stability and consistency can be maintained even with one-way updating and randomized pairwise averaging, thus providing a scalable low complexity method with performance guarantees. We illustrate the effectiveness of our algorithm for random network topologies.
Label Efficient Learning by Exploiting Multi-class Output Codes
Venue: arXiv cs.LG 2016
Year: 2016

We present a new perspective on the popular multi-class algorithmic techniques of one-vs-all and error correcting output codes. Rather than studying the behavior of these techniques for supervised learning, we establish a connection between the success of these methods and the existence of label-efficient learning procedures. We show that in both the realizable and agnostic cases, if output codes are successful at learning from labeled data, they implicitly assume structure on how the classes are related. By making that structure explicit, we design learning algorithms to recover the classes with low label complexity. We provide results for the commonly studied cases of one-vs-all learning and when the codewords of the classes are well separated. We additionally consider the more challenging case where the codewords are not well separated, but satisfy a boundary features condition that captures the natural intuition that every bit of the codewords should be significant.
An Analytic Expression of Relative Approximation Error for a Class of Evolutionary Algorithms
Venue: arXiv cs.NE 2016
Year: 2016

An important question in evolutionary computation is how good solutions evolutionary algorithms can produce. This paper aims to provide an analytic analysis of solution quality in terms of the relative approximation error, which is defined by the error between 1 and the approximation ratio of the solution found by an evolutionary algorithm. Since evolutionary algorithms are iterative methods, the relative approximation error is a function of generations. With the help of matrix analysis, it is possible to obtain an exact expression of such a function. In this paper, an analytic expression for calculating the relative approximation error is presented for a class of evolutionary algorithms, that is, (1+1) strictly elitist evolution algorithms. Furthermore, analytic expressions of the fitness value and the average convergence rate in each generation are also derived for this class of evolutionary algorithms. The approach is promising, and it can be extended to non-elitist or population-based algorithms too.
Optimal Pricing to Manage Electric Vehicles in Coupled Power and Transportation Networks
Venue: arXiv cs.SY 2016
Year: 2016

We study the system-level effects of the introduction of large populations of Electric Vehicles on the power and transportation networks. We assume that each EV owner solves a decision problem to pick a cost-minimizing charge and travel plan. This individual decision takes into account traffic congestion in the transportation network, affecting travel times, as well as as congestion in the power grid, resulting in spatial variations in electricity prices for battery charging. We show that this decision problem is equivalent to finding the shortest path on an "extended" transportation graph, with virtual arcs that represent charging options. Using this extended graph, we study the collective effects of a large number of EV owners individually solving this path planning problem. We propose a scheme in which independent power and transportation system operators can collaborate to manage each network towards a socially optimum operating point while keeping the operational data of each system private. We further study the optimal reserve capacity requirements for pricing in the absence of such collaboration. We showcase numerically that a lack of attention to interdependencies between the two infrastructures can have adverse operational effects.
Shearlet-Based Detection of Flame Fronts
Venue: arXiv cs.CV 2016
Year: 2016

Identifying and characterizing flame fronts is the most common task in the computer-assisted analysis of data obtained from imaging techniques such as planar laser-induced fluorescence (PLIF), laser Rayleigh scattering (LRS), or particle imaging velocimetry (PIV). We present a novel edge and ridge (line) detection algorithm based on complex-valued wavelet-like analyzing functions -- so-called complex shearlets -- displaying several traits useful for the extraction of flame fronts. In addition to providing a unified approach to the detection of edges and ridges, our method inherently yields estimates of local tangent orientations and local curvatures. To examine the applicability for high-frequency recordings of combustion processes, the algorithm is applied to mock images distorted with varying degrees of noise and real-world PLIF images of both OH and CH radicals. Furthermore, we compare the performance of the newly proposed complex shearlet-based measure to well-established edge and ridge detection techniques such as the Canny edge detector, another shearlet-based edge detector, and the phase congruency measure.