OpenRaiser/Intern-Atlas huggingface dataset:
Navigo: Interest Forwarding by Geolocations in Vehicular Named Data Networking
Venue: arXiv cs.NI 2015
Year: 2015

This paper proposes Navigo, a location based packet forwarding mechanism for vehicular Named Data Networking (NDN). Navigo takes a radically new approach to address the challenges of frequent connectivity disruptions and sudden network changes in a vehicle network. Instead of forwarding packets to a specific moving car, Navigo aims to fetch specific pieces of data from multiple potential carriers of the data. The design provides (1) a mechanism to bind NDN data names to the producers' geographic area(s); (2) an algorithm to guide Interests towards data producers using a specialized shortest path over the road topology; and (3) an adaptive discovery and selection mechanism that can identify the best data source across multiple geographic areas, as well as quickly react to changes in the V2X network.
EmoNets: Multimodal deep learning approaches for emotion recognition in video
Venue: arXiv cs.LG 2015
Year: 2015

The task of the emotion recognition in the wild (EmotiW) Challenge is to assign one of seven emotions to short video clips extracted from Hollywood style movies. The videos depict acted-out emotions under realistic conditions with a large degree of variation in attributes such as pose and illumination, making it worthwhile to explore approaches which consider combinations of features from multiple modalities for label assignment. In this paper we present our approach to learning several specialist models using deep learning techniques, each focusing on one modality. Among these are a convolutional neural network, focusing on capturing visual information in detected faces, a deep belief net focusing on the representation of the audio stream, a K-Means based "bag-of-mouths" model, which extracts visual features around the mouth region and a relational autoencoder, which addresses spatio-temporal aspects of videos. We explore multiple methods for the combination of cues from these modalities into one common classifier. This achieves a considerably greater accuracy than predictions from our strongest single-modality classifier. Our method was the winning submission in the 2013 EmotiW challenge and achieved a test set accuracy of 47.67% on the 2014 dataset.
Deep Clustered Convolutional Kernels
Venue: arXiv cs.LG 2015
Year: 2015

Deep neural networks have recently achieved state of the art performance thanks to new training algorithms for rapid parameter estimation and new regularization methods to reduce overfitting. However, in practice the network architecture has to be manually set by domain experts, generally by a costly trial and error procedure, which often accounts for a large portion of the final system performance. We view this as a limitation and propose a novel training algorithm that automatically optimizes network architecture, by progressively increasing model complexity and then eliminating model redundancy by selectively removing parameters at training time. For convolutional neural networks, our method relies on iterative split/merge clustering of convolutional kernels interleaved by stochastic gradient descent. We present a training algorithm and experimental results on three different vision tasks, showing improved performance compared to similarly sized hand-crafted architectures.
Estimation of the parameters of an infectious disease model using neural networks
Venue: arXiv cs.NE 2015
Year: 2015

In this paper, we propose a realistic mathematical model taking into account the mutual interference among the interacting populations. This model attempts to describe the control (vaccination) function as a function of the number of infective individuals, which is an improvement over the existing susceptible infective epidemic models. Regarding the growth of the epidemic as a nonlinear phenomenon we have developed a neural network architecture to estimate the vital parameters associated with this model. This architecture is based on a recently developed new class of neural networks known as co-operative and supportive neural networks. The application of this architecture to the present study involves preprocessing of the input data, and this renders an efficient estimation of the rate of spread of the epidemic. It is observed that the proposed new neural network outperforms a simple feed-forward neural network and polynomial regression.
Linear-time list recovery of high-rate expander codes
Venue: arXiv cs.IT 2015
Year: 2015

We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have been useful recently in constructing efficiently list-decodable codes, as well as explicit constructions of matrices for compressive sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most 1/2; in contrast, our codes can have rate $1 - ε$ for any $ε> 0$. We can plug our high-rate codes into a construction of Meir (2014) to obtain linear-time list recoverable codes of arbitrary rates, which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code. While list-recovery is interesting on its own, our primary motivation is applications to list-decoding. A slight strengthening of our result would implies linear-time and optimally list-decodable codes for all rates, and our work is a step in the direction of solving this important problem.
Qualitative Analysis of Integration Adapter Modeling
Venue: arXiv cs.SE 2015
Year: 2015

Integration Adapters are a fundamental part of an integration system, since they provide (business) applications access to its messaging channel. However, their modeling and configuration remain under-represented. In previous work, the integration control and data flow syntax and semantics have been expressed in the Business Process Model and Notation (BPMN) as a semantic model for message-based integration, while adapter and the related quality of service modeling were left for further studies. In this work we specify common adapter capabilities and derive general modeling patterns, for which we define a compliant representation in BPMN. The patterns extend previous work by the adapter flow, evaluated syntactically and semantically for common adapter characteristics.
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout
Venue: arXiv cs.LG 2015
Year: 2015

Training deep belief networks (DBNs) requires optimizing a non-convex function with an extremely large number of parameters. Naturally, existing gradient descent (GD) based methods are prone to arbitrarily poor local minima. In this paper, we rigorously show that such local minima can be avoided (upto an approximation error) by using the dropout technique, a widely used heuristic in this domain. In particular, we show that by randomly dropping a few nodes of a one-hidden layer neural network, the training objective function, up to a certain approximation error, decreases by a multiplicative factor. On the flip side, we show that for training convex empirical risk minimizers (ERM), dropout in fact acts as a "stabilizer" or regularizer. That is, a simple dropout based GD method for convex ERMs is stable in the face of arbitrary changes to any one of the training points. Using the above assertion, we show that dropout provides fast rates for generalization error in learning (convex) generalized linear models (GLM). Moreover, using the above mentioned stability properties of dropout, we design dropout based differentially private algorithms for solving ERMs. The learned GLM thus, preserves privacy of each of the individual training points while providing accurate predictions for new test points. Finally, we empirically validate our stability assertions for dropout in the context of convex ERMs and show that surprisingly, dropout significantly outperforms (in terms of prediction accuracy) the L2 regularization based methods for several benchmark datasets.
Estimation after Parameter Selection: Performance Analysis and Estimation Methods
Venue: arXiv cs.IT 2015
Year: 2015

In many practical parameter estimation problems, prescreening and parameter selection are performed prior to estimation. In this paper, we consider the problem of estimating a preselected unknown deterministic parameter chosen from a parameter set based on observations according to a predetermined selection rule, $Ψ$. The data-based parameter selection process may impact the subsequent estimation by introducing a selection bias and creating coupling between decoupled parameters. This paper introduces a post-selection mean squared error (PSMSE) criterion as a performance measure. A corresponding Cramér-Rao-type bound on the PSMSE of any $Ψ$-unbiased estimator is derived, where the $Ψ$-unbiasedness is in the Lehmann-unbiasedness sense. The post-selection maximum-likelihood (PSML) estimator is presented .It is proved that if there exists an $Ψ$-unbiased estimator that achieves the $Ψ$-Cramér-Rao bound (CRB), i.e. an $Ψ$-efficient estimator, then it is produced by the PSML estimator. In addition, iterative methods are developed for the practical implementation of the PSML estimator. Finally, the proposed $Ψ$-CRB and PSML estimator are examined in estimation after parameter selection with different distributions.
Band selection in RKHS for fast nonlinear unmixing of hyperspectral images
Venue: arXiv cs.CV 2015
Year: 2015

The profusion of spectral bands generated by the acquisition process of hyperspectral images generally leads to high computational costs. Such difficulties arise in particular with nonlinear unmixing methods, which are naturally more complex than linear ones. This complexity, associated with the high redundancy of information within the complete set of bands, make the search of band selection algorithms relevant. With this work, we propose a band selection strategy in reproducing kernel Hilbert spaces that allows to drastically reduce the processing time required by nonlinear unmixing techniques. Simulation results show a complexity reduction of two orders of magnitude without compromising unmixing performance.
Sparse Bayesian Dictionary Learning with a Gaussian Hierarchical Model
Venue: arXiv cs.LG 2015
Year: 2015

We consider a dictionary learning problem whose objective is to design a dictionary such that the signals admits a sparse or an approximate sparse representation over the learned dictionary. Such a problem finds a variety of applications such as image denoising, feature extraction, etc. In this paper, we propose a new hierarchical Bayesian model for dictionary learning, in which a Gaussian-inverse Gamma hierarchical prior is used to promote the sparsity of the representation. Suitable priors are also placed on the dictionary and the noise variance such that they can be reasonably inferred from the data. Based on the hierarchical model, a variational Bayesian method and a Gibbs sampling method are developed for Bayesian inference. The proposed methods have the advantage that they do not require the knowledge of the noise variance \emph{a priori}. Numerical results show that the proposed methods are able to learn the dictionary with an accuracy better than existing methods, particularly for the case where there is a limited number of training signals.
Adaptive Power Allocation and Control in Time-Varying Multi-Carrier MIMO Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we examine the fundamental trade-off between radiated power and achieved throughput in wireless multi-carrier, multiple-input and multiple-output (MIMO) systems that vary with time in an unpredictable fashion (e.g. due to changes in the wireless medium or the users' QoS requirements). Contrary to the static/stationary channel regime, there is no optimal power allocation profile to target (either static or in the mean), so the system's users must adapt to changes in the environment "on the fly", without being able to predict the system's evolution ahead of time. In this dynamic context, we formulate the users' power/throughput trade-off as an online optimization problem and we provide a matrix exponential learning algorithm that leads to no regret - i.e. the proposed transmit policy is asymptotically optimal in hindsight, irrespective of how the system evolves over time. Furthermore, we also examine the robustness of the proposed algorithm under imperfect channel state information (CSI) and we show that it retains its regret minimization properties under very mild conditions on the measurement noise statistics. As a result, users are able to track the evolution of their individually optimum transmit profiles remarkably well, even under rapidly changing network conditions and high uncertainty. Our theoretical analysis is validated by extensive numerical simulations corresponding to a realistic network deployment and providing further insights in the practical implementation aspects of the proposed algorithm.
Higher Weights of Affine Grassmann Codes and Their Duals
Venue: arXiv cs.IT 2015
Year: 2015

We consider the question of determining the higher weights or the generalized Hamming weights of affine Grassmann codes and their duals. Several initial as well as terminal higher weights of affine Grassmann codes of an arbitrary level are determined explicitly. In the case of duals of these codes, we give a formula for many initial as well as terminal higher weights. As a special case, we obtain an alternative simpler proof of the formula of Beelen et al for the minimum distance of the dual of an affine Grasmann code.
Containment for Conditional Tree Patterns
Venue: arXiv cs.LO 2015
Year: 2015

A Conditional Tree Pattern (CTP) expands an XML tree pattern with labels attached to the descendant edges. These labels can be XML element names or Boolean CTPs. The meaning of a descendant edge labelled by A and ending in a node labelled by B is a path of child steps ending in a B node such that all intermediate nodes are A nodes. In effect this expresses the until B, A holds construction from temporal logic.This paper studies the containment problem for CTP. For tree patterns (TP), this problem is known to be coNP-complete. We show that it is PSPACE-complete for CTP. This increase in complexity is due to the fact that CTP is expressive enough to encode an unrestricted form of label negation: ${*}\setminus a$, meaning "any node except an a-node". Containment of TP expanded with this type of negation is already PSPACE-hard. CTP is a positive, forward, first order fragment of Regular XPath. Unlike TP, CTP expanded with disjunction is not equivalent to unions of CTP's. Like TP, CTP is a natural fragment to consider: CTP is closed under intersections and CTP with disjunction is equally expressive as positive existential first order logic expanded with the until operator.
Bounding the Bethe and the Degree-$M$ Bethe Permanents
Venue: arXiv cs.IT 2015
Year: 2015

It was recently conjectured that the permanent of a ${P}$-lifting $θ^{\uparrow{P}}$ of a matrix $θ$ of degree $M$ is less than or equal to the $M$th power of the permanent perm$(θ)$, i.e., perm$(θ^{\uparrow{P}})\leq(\text{perm}(θ))^M$ and, consequently, that the degree-$M$ Bethe permanent $\text{perm}_{M,\mathrm{B}} (θ)$ of a matrix $θ$ is less than or equal to the permanent perm$(θ)$ of $θ$, i.e., perm$_{M, \mathrm{B}} (θ)\leq \text{perm}(θ)$. In this paper, we prove these related conjectures and show in addition a few properties of the permanent of block matrices that are lifts of a matrix. As a corollary, we obtain an alternative proof of the inequality perm$_{\mathrm{B}} (θ)\leq \text{perm}(θ)$ on the Bethe permanent of the base matrix $θ$ that uses only the combinatorial definition of the Bethe permanent.
An Analysis of a Virtually Synchronous Protocol
Venue: arXiv cs.DC 2015
Year: 2015

Enterprise-scale systems such as those used for cloud computing require a scalable and highly available infrastructure. One crucial ingredient of such an infrastructure is the ability to replicate data coherently among a group of cooperating processes in the presence of process failures and group membership changes. The last few decades have seen prolific research into efficient protocols for such data replication. One family of such protocols are the virtually synchronous protocols. Virtually synchronous protocols achieve their efficiency by limiting their synchronicity guarantee to messages that bear a causal relationship to each other. Such protocols have found wide-ranging commercial uses over the years. One protocol in particular, the CBCAST protocol developed by Birman, Schiper and Stephenson in 1991 and used in their ISIS platform was particularly promising due to its unique no-wait properties, but has suffered from seemingly intractable race conditions. In this paper we describe a corrected version of this protocol and prove its formal properties.
Three-Source Extractors for Polylogarithmic Min-Entropy
Venue: arXiv cs.CC 2015
Year: 2015

We continue the study of constructing explicit extractors for independent general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method --- an extractor for two independent $n$-bit weak random sources with min-entropy as small as $\log n+O(1)$. Previously, the best known result in the two-source case is an extractor by Bourgain \cite{Bourgain05}, which works for min-entropy $0.49n$; and the best known result in the general case is an earlier work of the author \cite{Li13b}, which gives an extractor for a constant number of independent sources with min-entropy $\mathsf{polylog(n)}$. However, the constant in the construction of \cite{Li13b} depends on the hidden constant in the best known seeded extractor, and can be large; moreover the error in that construction is only $1/\mathsf{poly(n)}$. In this paper, we make two important improvements over the result in \cite{Li13b}. First, we construct an explicit extractor for \emph{three} independent sources on $n$ bits with min-entropy $k \geq \mathsf{polylog(n)}$. In fact, our extractor works for one independent source with poly-logarithmic min-entropy and another independent block source with two blocks each having poly-logarithmic min-entropy. Thus, our result is nearly optimal, and the next step would be to break the $0.49n$ barrier in two-source extractors. Second, we improve the error of the extractor from $1/\mathsf{poly(n)}$ to $2^{-k^{Ω(1)}}$, which is almost optimal and crucial for cryptographic applications. Some of the techniques developed here may be of independent interests.
Understanding Image Virality
Venue: arXiv cs.SI 2015
Year: 2015

Virality of online content on social networking websites is an important but esoteric phenomenon often studied in fields like marketing, psychology and data mining. In this paper we study viral images from a computer vision perspective. We introduce three new image datasets from Reddit, and define a virality score using Reddit metadata. We train classifiers with state-of-the-art image features to predict virality of individual images, relative virality in pairs of images, and the dominant topic of a viral image. We also compare machine performance to human performance on these tasks. We find that computers perform poorly with low level features, and high level information is critical for predicting virality. We encode semantic information through relative attributes. We identify the 5 key visual attributes that correlate with virality. We create an attribute-based characterization of images that can predict relative virality with 68.10% accuracy (SVM+Deep Relative Attributes) -- better than humans at 60.12%. Finally, we study how human prediction of image virality varies with different `contexts' in which the images are viewed, such as the influence of neighbouring images, images recently viewed, as well as the image title or caption. This work is a first step in understanding the complex but important phenomenon of image virality. Our datasets and annotations will be made publicly available.
Measuring Technological Distance for Patent Mapping
Venue: arXiv cs.SI 2015
Year: 2015

Recent works in the information science literature have presented cases of using patent databases and patent classification information to construct network maps of technology fields, which aim to aid in competitive intelligence analysis and innovation decision making. Constructing such a patent network requires a proper measure of the distance between different classes of patents in the patent classification systems. Despite the existence of various distance measures in the literature, it is unclear how to consistently assess and compare them, and which ones to select for constructing patent technology network maps. This ambiguity has limited the development and applications of such technology maps. Herein, we propose to compare alternative distance measures and identify the superior ones by analyzing the differences and similarities in the structural properties of resulting patent network maps. Using United States patent data from 1976 to 2006 and International Patent Classification system, we compare 12 representative distance measures, which quantify inter-field knowledge base proximity, field-crossing diversification likelihood or frequency of innovation agents, and co-occurrences of patent classes in the same patents. Our comparative analyses suggest the patent technology network maps based on normalized co-reference and inventor diversification likelihood measures are the best representatives.
Riemann-Roch Spaces and Linear Network Codes
Venue: arXiv cs.IT 2015
Year: 2015

We construct linear network codes utilizing algebraic curves over finite fields and certain associated Riemann-Roch spaces and present methods to obtain their parameters. In particular we treat the Hermitian curve and the curves associated with the Suzuki and Ree groups all having the maximal number of points for curves of their respective genera. Linear network coding transmits information in terms of a basis of a vector space and the information is received as a basis of a possibly altered vector space. Ralf Koetter and Frank R. Kschischang %\cite{DBLP:journals/tit/KoetterK08} introduced a metric on the set of vector spaces and showed that a minimal distance decoder for this metric achieves correct decoding if the dimension of the intersection of the transmitted and received vector space is sufficiently large. The vector spaces in our construction have minimal distance bounded from below in the above metric making them suitable for linear network coding.
Stochastic Service Placement
Venue: arXiv cs.DS 2015
Year: 2015

Resource allocation for cloud services is a complex task due to the diversity of the services and the dynamic workloads. One way to address this is by overprovisioning which results in high cost due to the unutilized resources. A much more economical approach, relying on the stochastic nature of the demand, is to allocate just the right amount of resources and use additional more expensive mechanisms in case of overflow situations where demand exceeds the capacity. In this paper we study this approach and show both by comprehensive analysis for independent normal distributed demands and simulation on synthetic data that it is significantly better than currently deployed methods.