OpenRaiser/Intern-Atlas huggingface dataset:
Towards Biologically Plausible Deep Learning
Venue: arXiv cs.LG 2016
Year: 2016

Neuroscientists have long criticised deep learning algorithms as incompatible with current knowledge of neurobiology. We explore more biologically plausible versions of deep representation learning, focusing here mostly on unsupervised learning but developing a learning mechanism that could account for supervised, unsupervised and reinforcement learning. The starting point is that the basic learning rule believed to govern synaptic weight updates (Spike-Timing-Dependent Plasticity) arises out of a simple update rule that makes a lot of sense from a machine learning point of view and can be interpreted as gradient descent on some objective function so long as the neuronal dynamics push firing rates towards better values of the objective function (be it supervised, unsupervised, or reward-driven). The second main idea is that this corresponds to a form of the variational EM algorithm, i.e., with approximate rather than exact posteriors, implemented by neural dynamics. Another contribution of this paper is that the gradients required for updating the hidden states in the above variational interpretation can be estimated using an approximation that only requires propagating activations forward and backward, with pairs of layers learning to form a denoising auto-encoder. Finally, we extend the theory about the probabilistic interpretation of auto-encoders to justify improved sampling schemes based on the generative interpretation of denoising auto-encoders, and we validate all these ideas on generative learning tasks.
The Linearization of Belief Propagation on Pairwise Markov Networks
Venue: arXiv cs.AI 2016
Year: 2016

Belief Propagation (BP) is a widely used approximation for exact probabilistic inference in graphical models, such as Markov Random Fields (MRFs). In graphs with cycles, however, no exact convergence guarantees for BP are known, in general. For the case when all edges in the MRF carry the same symmetric, doubly stochastic potential, recent works have proposed to approximate BP by linearizing the update equations around default values, which was shown to work well for the problem of node classification. The present paper generalizes all prior work and derives an approach that approximates loopy BP on any pairwise MRF with the problem of solving a linear equation system. This approach combines exact convergence guarantees and a fast matrix implementation with the ability to model heterogenous networks. Experiments on synthetic graphs with planted edge potentials show that the linearization has comparable labeling accuracy as BP for graphs with weak potentials, while speeding-up inference by orders of magnitude.
Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes
Venue: arXiv cs.CC 2016
Year: 2016

We give polynomial time algorithms for quantitative (and qualitative) reachability analysis for Branching Markov Decision Processes (BMDPs). Specifically, given a BMDP, and given an initial population, where the objective of the controller is to maximize (or minimize) the probability of eventually reaching a population that contains an object of a desired (or undesired) type, we give algorithms for approximating the supremum (infimum) reachability probability, within desired precision epsilon > 0, in time polynomial in the encoding size of the BMDP and in log(1/epsilon). We furthermore give P-time algorithms for computing epsilon-optimal strategies for both maximization and minimization of reachability probabilities. We also give P-time algorithms for all associated qualitative analysis problems, namely: deciding whether the optimal (supremum or infimum) reachability probabilities are 0 or 1. Prior to this paper, approximation of optimal reachability probabilities for BMDPs was not even known to be decidable. Our algorithms exploit the following basic fact: we show that for any BMDP, its maximum (minimum) non-reachability probabilities are given by the greatest fixed point (GFP) solution g* in [0,1]^n of a corresponding monotone max (min) Probabilistic Polynomial System of equations (max/min-PPS), x=P(x), which are the Bellman optimality equations for a BMDP with non-reachability objectives. We show how to compute the GFP of max/min PPSs to desired precision in P-time. We also study more general Branching Simple Stochastic Games (BSSGs) with (non-)reachability objectives. We show that: (1) the value of these games is captured by the GFP of a corresponding max-minPPS; (2) the quantitative problem of approximating the value is in TFNP; and (3) the qualitative problems associated with the value are all solvable in P-time.
Regularization and Kernelization of the Maximin Correlation Approach
Venue: arXiv cs.CV 2016
Year: 2016

Robust classification becomes challenging when each class consists of multiple subclasses. Examples include multi-font optical character recognition and automated protein function prediction. In correlation-based nearest-neighbor classification, the maximin correlation approach (MCA) provides the worst-case optimal solution by minimizing the maximum misclassification risk through an iterative procedure. Despite the optimality, the original MCA has drawbacks that have limited its wide applicability in practice. That is, the MCA tends to be sensitive to outliers, cannot effectively handle nonlinearities in datasets, and suffers from having high computational complexity. To address these limitations, we propose an improved solution, named regularized maximin correlation approach (R-MCA). We first reformulate MCA as a quadratically constrained linear programming (QCLP) problem, incorporate regularization by introducing slack variables in the primal problem of the QCLP, and derive the corresponding Lagrangian dual. The dual formulation enables us to apply the kernel trick to R-MCA so that it can better handle nonlinearities. Our experimental results demonstrate that the regularization and kernelization make the proposed R-MCA more robust and accurate for various classification tasks than the original MCA. Furthermore, when the data size or dimensionality grows, R-MCA runs substantially faster by solving either the primal or dual (whichever has a smaller variable dimension) of the QCLP.
When Social Influence Meets Item Inference
Venue: arXiv cs.SI 2016
Year: 2016

Research issues and data mining techniques for product recommendation and viral marketing have been widely studied. Existing works on seed selection in social networks do not take into account the effect of product recommendations in e-commerce stores. In this paper, we investigate the seed selection problem for viral marketing that considers both effects of social influence and item inference (for product recommendation). We develop a new model, Social Item Graph (SIG), that captures both effects in form of hyperedges. Accordingly, we formulate a seed selection problem, called Social Item Maximization Problem (SIMP), and prove the hardness of SIMP. We design an efficient algorithm with performance guarantee, called Hyperedge-Aware Greedy (HAG), for SIMP and develop a new index structure, called SIG-index, to accelerate the computation of diffusion process in HAG. Moreover, to construct realistic SIG models for SIMP, we develop a statistical inference based framework to learn the weights of hyperedges from data. Finally, we perform a comprehensive evaluation on our proposals with various baselines. Experimental result validates our ideas and demonstrates the effectiveness and efficiency of the proposed model and algorithms over baselines.
Multilevel Diversity Coding with Regeneration
Venue: arXiv cs.IT 2016
Year: 2016

Digital contents in large scale distributed storage systems may have different reliability and access delay requirements, and for this reason, erasure codes with different strengths need to be utilized to achieve the best storage efficiency. At the same time, in such large scale distributed storage systems, nodes fail on a regular basis, and the contents stored on them need to be regenerated and stored on other healthy nodes, the efficiency of which is an important factor affecting the overall quality of service. In this work, we formulate the problem of multilevel diversity coding with regeneration to address these considerations, for which the storage vs. repair-bandwidth tradeoff is investigated. We show that the extreme point on this tradeoff corresponding to the minimum possible storage can be achieved by a simple coding scheme, where contents with different reliability requirements are encoded separately with individual regenerating codes without any mixing. On the other hand, we establish the complete storage-repair-bandwidth tradeoff for the case of four storage nodes, which reveals that codes mixing different contents can strictly improve this tradeoff over the separate coding solution.
The Routing of Complex Contagion in Kleinberg's Small-World Networks
Venue: arXiv cs.SI 2016
Year: 2016

In Kleinberg's small-world network model, strong ties are modeled as deterministic edges in the underlying base grid and weak ties are modeled as random edges connecting remote nodes. The probability of connecting a node $u$ with node $v$ through a weak tie is proportional to $1/|uv|^α$, where $|uv|$ is the grid distance between $u$ and $v$ and $α\ge 0$ is the parameter of the model. Complex contagion refers to the propagation mechanism in a network where each node is activated only after $k \ge 2$ neighbors of the node are activated. In this paper, we propose the concept of routing of complex contagion (or complex routing), where we can activate one node at one time step with the goal of activating the targeted node in the end. We consider decentralized routing scheme where only the weak ties from the activated nodes are revealed. We study the routing time of complex contagion and compare the result with simple routing and complex diffusion (the diffusion of complex contagion, where all nodes that could be activated are activated immediately in the same step with the goal of activating all nodes in the end). We show that for decentralized complex routing, the routing time is lower bounded by a polynomial in $n$ (the number of nodes in the network) for all range of $α$ both in expectation and with high probability (in particular, $Ω(n^{\frac{1}{α+2}})$ for $α\le 2$ and $Ω(n^{\fracα{2(α+2)}})$ for $α> 2$ in expectation), while the routing time of simple contagion has polylogarithmic upper bound when $α= 2$. Our results indicate that complex routing is harder than complex diffusion and the routing time of complex contagion differs exponentially compared to simple contagion at sweetspot.
Graphical Representation for Heterogeneous Face Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Heterogeneous face recognition (HFR) refers to matching face images acquired from different sources (i.e., different sensors or different wavelengths) for identification. HFR plays an important role in both biometrics research and industry. In spite of promising progresses achieved in recent years, HFR is still a challenging problem due to the difficulty to represent two heterogeneous images in a homogeneous manner. Existing HFR methods either represent an image ignoring the spatial information, or rely on a transformation procedure which complicates the recognition task. Considering these problems, we propose a novel graphical representation based HFR method (G-HFR) in this paper. Markov networks are employed to represent heterogeneous image patches separately, which takes the spatial compatibility between neighboring image patches into consideration. A coupled representation similarity metric (CRSM) is designed to measure the similarity between obtained graphical representations. Extensive experiments conducted on multiple HFR scenarios (viewed sketch, forensic sketch, near infrared image, and thermal infrared image) show that the proposed method outperforms state-of-the-art methods.
What Is an Emerging Technology?
Venue: arXiv cs.OH 2016
Year: 2016

There is considerable and growing interest in the emergence of novel technologies, especially from the policy-making perspective. Yet as an area of study, emerging technologies lacks key foundational elements, namely a consensus on what classifies a technology as 'emergent' and strong research designs that operationalize central theoretical concepts. The present paper aims to fill this gap by developing a definition of 'emerging technologies' and linking this conceptual effort with the development of a framework for the operationalisation of technological emergence. The definition is developed by combining a basic understanding of the term and in particular the concept of 'emergence' with a review of key innovation studies dealing with definitional issues of technological emergence. The resulting definition identifies five attributes that feature in the emergence of novel technologies. These are: (i) radical novelty, (ii) relatively fast growth, (iii) coherence, (iv) prominent impact, and (v) uncertainty and ambiguity. The framework for operationalising emerging technologies is then elaborated on the basis of the proposed attributes. To do so, we identify and review major empirical approaches (mainly in, although not limited to, the scientometric domain) for the detection and study of emerging technologies (these include indicators and trend analysis, citation analysis, co-word analysis, overlay mapping, and combinations thereof) and elaborate on how these can be used to operationalise the different attributes of emergence.
Cooperative Base Station Coloring for Pair-wise Multi-Cell Coordination
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a method for designing BS clusters and cluster patterns for pair-wise BS coordination. The key idea is that each BS cluster is formed by using the 2nd-order Voronoi region, and the BS clusters are assigned to a specific cluster pattern by using edge-coloring for a graph drawn by Delaunay triangulation. The main advantage of the proposed method is that the BS selection conflict problem is prevented, while selected users are guaranteed to communicate with their two closest BSs in any irregular BS topology. With the proposed coordination method, analytical expressions for the rate distribution and the ergodic spectral efficiency are derived as a function of relevant system parameters in a fixed irregular network model. In a random network model with a homogeneous Poisson point process, a lower bound on the ergodic spectral efficiency is characterized. Through system level simulations, the performance of the proposed method is compared with that of conventional coordination methods: dynamic clustering and static clustering. Our major finding is that, when users are dense enough in a network, the proposed method provides the same level of coordination benefit with dynamic clustering to edge users.
TED: A Tolerant Edit Distance for Segmentation Evaluation
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present a novel error measure to compare a segmentation against ground truth. This measure, which we call Tolerant Edit Distance (TED), is motivated by two observations: (1) Some errors, like small boundary shifts, are tolerable in practice. Which errors are tolerable is application dependent and should be a parameter of the measure. (2) Non-tolerable errors have to be corrected manually. The time needed to do so should be reflected by the error measure. Using integer linear programming, the TED finds the minimal weighted sum of split and merge errors exceeding a given tolerance criterion, and thus provides a time-to-fix estimate. In contrast to commonly used measures like Rand index or variation of information, the TED (1) does not count small, but tolerable, differences, (2) provides intuitive numbers, (3) gives a time-to-fix estimate, and (4) can localize and classify the type of errors. By supporting both isotropic and anisotropic volumes and having a flexible tolerance criterion, the TED can be adapted to different requirements. On example segmentations for 3D neuron segmentation, we demonstrate that the TED is capable of counting topological errors, while ignoring small boundary shifts.
Model Predictive Control under Timing Constraints induced by Controller Area Networks
Venue: arXiv cs.SY 2016
Year: 2016

When multiple model predictive controllers are implemented on a shared control area network (CAN), their performance may degrade due to the inhomogeneous timing and delays among messages. The priority based real-time scheduling of messages on the CAN introduces complex timing of events, especially when the types and number of messages change at runtime. This paper introduces a novel hybrid timing model to make runtime predictions on the timing of the messages for a finite time window. Controllers can be designed using the optimization algorithms for model predictive control by considering the timing as optimization constraints. This timing model allows multiple controllers to share a CAN without significant degradation in the controller performance. The timing model also provides a convenient way to check the schedulability of messages on the CAN at runtime. Simulation results demonstrate that the timing model is accurate and computationally efficient to meet the needs of real-time implementation. Simulation results also demonstrate that model predictive controllers designed when considering the timing constraints have superior performance than the controllers designed without considering the timing constraints.
Low-Delay Adaptive Video Streaming Based on Short-Term TCP Throughput Prediction
Venue: arXiv cs.NI 2016
Year: 2016

Recently, HTTP-Based Adaptive Streaming has become the de facto standard for video streaming over the Internet. It allows the client to adapt media characteristics to varying network conditions in order to maximize Quality of Experience (QoE). In the case of live streaming this task becomes particularly challenging. An important factor than might help improving performance is the capability to correctly predict network throughput dynamics on short to medium timescales. It becomes notably difficult in wireless networks that are often subject to continuous throughput fluctuations. In the present work, we develop an adaptation algorithm for HTTP-Based Adaptive Live Streaming that, for each adaptation decision, maximizes a QoE-based utility function depending on the probability of playback interruptions, average video quality, and the amount of video quality fluctuations. To compute the utility function the algorithm leverages throughput predictions, and dynamically estimated prediction accuracy. We are trying to close the gap created by the lack of studies analyzing TCP throughput on short to medium timescales. We study several time series prediction methods and their error distributions. We observe that Simple Moving Average performs best in most cases. We also observe that the relative underestimation error is best represented by a truncated normal distribution, while the relative overestimation error is best represented by a Lomax distribution. Moreover, underestimations and overestimations exhibit a temporal correlation that we use to further improve prediction accuracy. We compare the proposed algorithm with a baseline approach that uses a fixed margin between past throughput and selected media bit rate, and an oracle-based approach that has perfect knowledge over future throughput for a certain time horizon.
New upper bounds on binary linear codes and a $\mathbb Z_4$-code with a better-than-linear Gray image
Venue: arXiv cs.IT 2016
Year: 2016

Using integer linear programming and table-lookups we prove that there is no binary linear $[1988, 12, 992]$ code. As a by-product, the non-existence of binary linear codes with the parameters $[324, 10, 160]$, $[356, 10, 176]$, $[772,11,384]$, and $[836,11,416]$ is shown. Our work is motivated by the recent construction of the extended dualized Kerdock code $\hat{\mathcal{K}}^*_{6}$, which is a $\mathbb{Z}_4$-linear code having a non-linear binary Gray image with the parameters $(1988,2^{12},992)$. By our result, the code $\hat{\mathcal{K}}^*_{6}$ can be added to the small list of $\mathbb{Z}_4$-codes for which it is known that the Gray image is better than any binary linear code.
Two-User Erasure Interference Channels with Local Delayed CSIT
Venue: arXiv cs.IT 2016
Year: 2016

We study the capacity region of two-user erasure interference channels with local delayed channel state information at the transmitters. In our model, transmitters have local mismatched outdated knowledge of the channel gains. We propose a transmission strategy that only relies on the delayed knowledge of the {\it outgoing} links at each transmitter and achieves the outer-bound for the scenario in which transmitters learn the entire channel state with delay. Our result reveals the subset of the channel state information that affects the capacity region the most. We also identify cases in which local delayed knowledge of the channel state does not provide any gain over the zero knowledge assumption. To do so, we revisit a long-known intuition about interference channels that as long as the marginal distributions at the receivers are conserved, the capacity remains the same. We take this intuition and impose a certain spatial correlation among channel gains such that the marginal distributions remain unchanged. Then we provide an outer-bound on the capacity region of the channel with correlation that matches the capacity region when transmitters do not have access to channel state information.
Bio-Inspired Framework for Allocation of Protection Resources in Cyber-Physical Networks
Venue: arXiv cs.SI 2016
Year: 2016

In this chapter, we consider the problem of designing protection strategies to contain spreading processes in complex cyber-physical networks. We illustrate our ideas using a family of bio-motivated spreading models originally proposed in the epidemiological literature, e.g., the Susceptible-Infected-Susceptible (SIS) model. We first introduce a framework in which we are allowed to distribute two types of resources in order to contain the spread, namely, (i) preventive resources able to reduce the spreading rate, and (ii) corrective resources able to increase the recovery rate of nodes in which the resources are allocated. In practice, these resources have an associated cost that depends on either the resiliency level achieved by the preventive resource, or the restoration efficiency of the corrective resource. We present a mathematical framework, based on dynamic systems theory and convex optimization, to find the cost-optimal distribution of protection resources in a network to contain the spread. We also present two extensions to this framework in which (i) we consider generalized epidemic models, beyond the simple SIS model, and (ii) we assume uncertainties in the contact network in which the spreading is taking place. We compare these protection strategies with common heuristics previously proposed in the literature and illustrate our results with numerical simulations using the air traffic network.