OpenRaiser/Intern-Atlas huggingface dataset:
Gradual DropIn of Layers to Train Very Deep Neural Networks
Venue: arXiv cs.NE 2015
Year: 2015

We introduce the concept of dynamically growing a neural network during training. In particular, an untrainable deep network starts as a trainable shallow network and newly added layers are slowly, organically added during training, thereby increasing the network's depth. This is accomplished by a new layer, which we call DropIn. The DropIn layer starts by passing the output from a previous layer (effectively skipping over the newly added layers), then increasingly including units from the new layers for both feedforward and backpropagation. We show that deep networks, which are untrainable with conventional methods, will converge with DropIn layers interspersed in the architecture. In addition, we demonstrate that DropIn provides regularization during training in an analogous way as dropout. Experiments are described with the MNIST dataset and various expanded LeNet architectures, CIFAR-10 dataset with its architecture expanded from 3 to 11 layers, and on the ImageNet dataset with the AlexNet architecture expanded to 13 layers and the VGG 16-layer architecture.
Binary Linear Locally Repairable Codes
Venue: arXiv cs.IT 2015
Year: 2015

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size $q$, i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this work, we present an upper bound on the minimum distance $d$ of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length $n$, dimension $k$, locality $r$, availability $t$, and field size $q$. Then, we study binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed-Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared to other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and $4$-cycle free regular low-density parity-check (LDPC) codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code.
A General Framework for the Design and Analysis of Sparse FIR Linear Equalizers
Venue: arXiv cs.IT 2015
Year: 2015

Complexity of linear finite-impulse-response (FIR) equalizers is proportional to the square of the number of nonzero taps in the filter. This makes equalization of channels with long impulse responses using either zero-forcing or minimum mean square error (MMSE) filters computationally expensive. Sparse equalization is a widely-used technique to solve this problem. In this paper, a general framework is provided that transforms the problem of sparse linear equalizers (LEs) design into the problem of sparsest-approximation of a vector in different dictionaries. In addition, some possible choices of sparsifying dictionaries in this framework are discussed. Furthermore, the worst-case coherence of some of these dictionaries, which determines their sparsifying strength, are analytically and/or numerically evaluated. Finally, the usefulness of the proposed framework for the design of sparse FIR LEs is validated through numerical experiments.
Trading Safety Versus Performance: Rapid Deployment of Robotic Swarms with Robust Performance Constraints
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we consider a stochastic deployment problem, where a robotic swarm is tasked with the objective of positioning at least one robot at each of a set of pre-assigned targets while meeting a temporal deadline. Travel times and failure rates are stochastic but related, inasmuch as failure rates increase with speed. To maximize chances of success while meeting the deadline, a control strategy has therefore to balance safety and performance. Our approach is to cast the problem within the theory of constrained Markov Decision Processes, whereby we seek to compute policies that maximize the probability of successful deployment while ensuring that the expected duration of the task is bounded by a given deadline. To account for uncertainties in the problem parameters, we consider a robust formulation and we propose efficient solution algorithms, which are of independent interest. Numerical experiments confirming our theoretical results are presented and discussed.
Non-Sentential Utterances in Dialogue: Experiments in Classification and Interpretation
Venue: arXiv cs.CL 2015
Year: 2015

Non-sentential utterances (NSUs) are utterances that lack a complete sentential form but whose meaning can be inferred from the dialogue context, such as "OK", "where?", "probably at his apartment". The interpretation of non-sentential utterances is an important problem in computational linguistics since they constitute a frequent phenomena in dialogue and they are intrinsically context-dependent. The interpretation of NSUs is the task of retrieving their full semantic content from their form and the dialogue context. The first half of this thesis is devoted to the NSU classification task. Our work builds upon Fernández et al. (2007) which present a series of machine-learning experiments on the classification of NSUs. We extended their approach with a combination of new features and semi-supervised learning techniques. The empirical results presented in this thesis show a modest but significant improvement over the state-of-the-art classification performance. The consecutive, yet independent, problem is how to infer an appropriate semantic representation of such NSUs on the basis of the dialogue context. Fernández (2006) formalizes this task in terms of "resolution rules" built on top of the Type Theory with Records (TTR). Our work is focused on the reimplementation of the resolution rules from Fernández (2006) with a probabilistic account of the dialogue state. The probabilistic rules formalism Lison (2014) is particularly suited for this task because, similarly to the framework developed by Ginzburg (2012) and Fernández (2006), it involves the specification of update rules on the variables of the dialogue state to capture the dynamics of the conversation. However, the probabilistic rules can also encode probabilistic knowledge, thereby providing a principled account of ambiguities in the NSU resolution process.
Performance Analysis of Apriori Algorithm with Different Data Structures on Hadoop Cluster
Venue: arXiv cs.DC 2015
Year: 2015

Mining frequent itemsets from massive datasets is always being a most important problem of data mining. Apriori is the most popular and simplest algorithm for frequent itemset mining. To enhance the efficiency and scalability of Apriori, a number of algorithms have been proposed addressing the design of efficient data structures, minimizing database scan and parallel and distributed processing. MapReduce is the emerging parallel and distributed technology to process big datasets on Hadoop Cluster. To mine big datasets it is essential to re-design the data mining algorithm on this new paradigm. In this paper, we implement three variations of Apriori algorithm using data structures hash tree, trie and hash table trie i.e. trie with hash technique on MapReduce paradigm. We emphasize and investigate the significance of these three data structures for Apriori algorithm on Hadoop cluster, which has not been given attention yet. Experiments are carried out on both real life and synthetic datasets which shows that hash table trie data structures performs far better than trie and hash tree in terms of execution time. Moreover the performance in case of hash tree becomes worst.
Anvaya: An Algorithm and Case-Study on Improving the Goodness of Software Process Models generated by Mining Event-Log Data in Issue Tracking System
Venue: arXiv cs.SE 2015
Year: 2015

Issue Tracking Systems (ITS) such as Bugzilla can be viewed as Process Aware Information Systems (PAIS) generating event-logs during the life-cycle of a bug report. Process Mining consists of mining event logs generated from PAIS for process model discovery, conformance and enhancement. We apply process map discovery techniques to mine event trace data generated from ITS of open source Firefox browser project to generate and study process models. Bug life-cycle consists of diversity and variance. Therefore, the process models generated from the event-logs are spaghetti-like with large number of edges, inter-connections and nodes. Such models are complex to analyse and difficult to comprehend by a process analyst. We improve the Goodness (fitness and structural complexity) of the process models by splitting the event-log into homogeneous subsets by clustering structurally similar traces. We adapt the K-Medoid clustering algorithm with two different distance metrics: Longest Common Subsequence (LCS) and Dynamic Time Warping (DTW). We evaluate the goodness of the process models generated from the clusters using complexity and fitness metrics. We study back-forth \& self-loops, bug reopening, and bottleneck in the clusters obtained and show that clustering enables better analysis. We also propose an algorithm to automate the clustering process -the algorithm takes as input the event log and returns the best cluster set.
Fine-grained pose prediction, normalization, and recognition
Venue: arXiv cs.CV 2015
Year: 2015

Pose variation and subtle differences in appearance are key challenges to fine-grained classification. While deep networks have markedly improved general recognition, many approaches to fine-grained recognition rely on anchoring networks to parts for better accuracy. Identifying parts to find correspondence discounts pose variation so that features can be tuned to appearance. To this end previous methods have examined how to find parts and extract pose-normalized features. These methods have generally separated fine-grained recognition into stages which first localize parts using hand-engineered and coarsely-localized proposal features, and then separately learn deep descriptors centered on inferred part positions. We unify these steps in an end-to-end trainable network supervised by keypoint locations and class labels that localizes parts by a fully convolutional network to focus the learning of feature representations for the fine-grained classification task. Experiments on the popular CUB200 dataset show that our method is state-of-the-art and suggest a continuing role for strong supervision.
Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs
Venue: arXiv cs.CC 2015
Year: 2015

Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a polynomial size depth-$3$ circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time $2^{\tilde{O}(n^{1-1/2^{k-1}})}$ and needs white box access only to know the order in which the variables appear in the ABP.
Convex Optimization Based State Estimation against Sparse Integrity Attacks
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of robust estimation in the presence of integrity attacks. There are m sensors monitoring the state and p of them are under attack. The malicious measurements collected by the compromised sensors can be manipulated arbitrarily by the attacker. The classical estimators such as the least squares estimator may not provide a reliable estimate under the so-called (p,m)-sparse attack. In this work, we are not restricting our efforts in studying whether any specific estimator is resilient to the attack or not, but instead we aim to present some generic sufficient and necessary conditions for robustness by considering a general class of convex optimization based estimators. The sufficient and necessary conditions are shown to be tight, with a trivial gap.
Construction of Unit-Memory MDS Convolutional Codes
Venue: arXiv cs.IT 2015
Year: 2015

Maximum-distance separable (MDS) convolutional codes form an optimal family of convolutional codes, the study of which is of great importance. There are very few general algebraic constructions of MDS convolutional codes. In this paper, we construct a large family of unit-memory MDS convolutional codes over $\F$ with flexible parameters. Compared with previous works, the field size $q$ required to define these codes is much smaller. The construction also leads to many new strongly-MDS convolutional codes, an important subclass of MDS convolutional codes proposed and studied in \cite{GL2}. Many examples are presented at the end of the paper.
Learning Simple Algorithms from Examples
Venue: arXiv cs.AI 2015
Year: 2015

We present an approach for learning simple algorithms such as copying, multi-digit addition and single digit multiplication directly from examples. Our framework consists of a set of interfaces, accessed by a controller. Typical interfaces are 1-D tapes or 2-D grids that hold the input and output data. For the controller, we explore a range of neural network-based models which vary in their ability to abstract the underlying algorithm from training instances and generalize to test examples with many thousands of digits. The controller is trained using $Q$-learning with several enhancements and we show that the bottleneck is in the capabilities of the controller rather than in the search incurred by $Q$-learning.
Harnessing Mobile Phone Social Network Topology to Infer Users Demographic Attributes
Venue: arXiv cs.SI 2015
Year: 2015

We study the structure of the social graph of mobile phone users in the country of Mexico, with a focus on demographic attributes of the users (more specifically the users' age). We examine assortativity patterns in the graph, and observe a strong age homophily in the communications preferences. We propose a graph based algorithm for the prediction of the age of mobile phone users. The algorithm exploits the topology of the mobile phone network, together with a subset of known users ages (seeds), to infer the age of remaining users. We provide the details of the methodology, and show experimental results on a network GT with more than 70 million users. By carefully examining the topological relations of the seeds to the rest of the nodes in GT, we find topological metrics which have a direct influence on the performance of the algorithm. In particular we characterize subsets of users for which the accuracy of the algorithm is 62% when predicting between 4 age categories (whereas a pure random guess would yield an accuracy of 25%). We also show that we can use the probabilistic information computed by the algorithm to further increase its inference power to 72% on a significant subset of users.
Path Loss, Shadow Fading, and Line-Of-Sight Probability Models for 5G Urban Macro-Cellular Scenarios
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents key parameters including the line-of-sight (LOS) probability, large-scale path loss, and shadow fading models for the design of future fifth generation (5G) wireless communication systems in urban macro-cellular (UMa) scenarios, using the data obtained from propagation measurements at 38 GHz in Austin, US, and at 2, 10, 18, and 28 GHz in Aalborg, Denmark. A comparison of different LOS probability models is performed for the Aalborg environment. Alpha-betagamma and close-in reference distance path loss models are studied in depth to show their value in channel modeling. Additionally, both single-slope and dual-slope omnidirectional path loss models are investigated to analyze and contrast their root-mean-square (RMS) errors on measured path loss values. While the results show that the dual-slope large-scale path loss model can slightly reduce RMS errors compared to its singleslope counterpart in non-line-of-sight (NLOS) conditions, the improvement is not significant enough to warrant adopting the dual-slope path loss model. Furthermore, the shadow fading magnitude versus distance is explored, showing a slight increasing trend in LOS and a decreasing trend in NLOS based on the Aalborg data, but more measurements are necessary to gain a better knowledge of the UMa channels at centimeter- and millimeter-wave frequency bands.
An Efficient Multiple-Groupcast Coded Multicasting Scheme for Finite Fractional Caching
Venue: arXiv cs.IT 2015
Year: 2015

Coded multicasting has been shown to improve the caching performance of content delivery networks with multiple caches downstream of a common multicast link. However, the schemes that have been shown to achieve order-optimal perfor- mance require content items to be partitioned into a number of packets that grows exponentially with the number of users [1]. In this paper, we first extend the analysis of the achievable scheme in [2] to the case of heterogeneous cache sizes and demand distribu- tions, providing an achievable scheme and an upper bound on the limiting average performance when the number of packets goes to infinity while the remaining system parameters are kept constant. We then show how the scheme achieving this upper bound can very quickly loose its multiplicative caching gain for finite content packetization. To overcome this limitation, we design a novel polynomial-time algorithm based on greedy local graph-coloring that, while keeping the same content packetization, recovers a significant part of the multiplicative caching gain. Our results show that the achievable schemes proposed to date to quantify the limiting performance, must be properly designed for practical finite system parameters.
Mobile Service-Based Cooperative Scheduling for High-Mobility Vehicular Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the downlink scheduling for relay-aided high-mobility vehicular networks, where the vehicles with good vehicle-to-infrastructure (V2I) links are employed as cooperative relay nodes to help the ones with poor V2I links forward information via vehicle-to-vehicle (V2V) links. In existing works, instantaneous achievable information rate was widely adopted to perform the link scheduling, but it is not efficient for vehicular networks, especially for high-mobility scenarios. Different from them, in this paper, we introduce the mobile service to describe the mobile link capacity of vehicular networks and then we propose a mobile service based relaying scheduling (MSRS) for high mobility vehicular networks. In order to explore the system information transmission performance limit, we formulate an optimization problem to maximize the mobile service amount of MSRS by jointly scheduling the V2I and V2V links. Since it is a combinational optimization problem which is too complex to solve, we design an efficient algorithm with low-complexity for it, where Sort-then-Select, Hungarian algorithm and Bisection search are employed. Simulation results demonstrate that our proposed MSRS is able to achieve the optimal results with an optimal approximation ratio larger than 96.5%. It is also shown that our proposed MSRS is much more efficient for high-mobility vehicular systems, which can improve the system average throughput with increment of 3.63% compared with existing instantaneous achievable information rate based scheduling method, and with 15% increment compared with traditional non-cooperation scheduling method, respectively.
Picking a Conveyor Clean by an Autonomously Learning Robot
Venue: arXiv cs.RO 2015
Year: 2015

We present a research picking prototype related to our company's industrial waste sorting application. The goal of the prototype is to be as autonomous as possible and it both calibrates itself and improves its picking with minimal human intervention. The system learns to pick objects better based on a feedback sensor in its gripper and uses machine learning to choosing the best proposal from a random sample produced by simple hard-coded geometric models. We show experimentally the system improving its picking autonomously by measuring the pick success rate as function of time. We also show how this system can pick a conveyor belt clean, depositing 70 out of 80 objects in a difficult to manipulate pile of novel objects into the correct chute. We discuss potential improvements and next steps in this direction.
Mouse Pose Estimation From Depth Images
Venue: arXiv cs.CV 2015
Year: 2015

We focus on the challenging problem of efficient mouse 3D pose estimation based on static images, and especially single depth images. We introduce an approach to discriminatively train the split nodes of trees in random forest to improve their performance on estimation of 3D joint positions of mouse. Our algorithm is capable of working with different types of rodents and with different types of depth cameras and imaging setups. In particular, it is demonstrated in this paper that when a top-mounted depth camera is combined with a bottom-mounted color camera, the final system is capable of delivering full-body pose estimation including four limbs and the paws. Empirical examinations on synthesized and real-world depth images confirm the applicability of our approach on mouse pose estimation, as well as the closely related task of part-based labeling of mouse.
Multivariate Complexity Analysis of Geometric {\sc Red Blue Set Cover}
Venue: arXiv cs.DS 2015
Year: 2015

We investigate the parameterized complexity of GENERALIZED RED BLUE SET COVER (Gen-RBSC), a generalization of the classic SET COVER problem and the more recently studied RED BLUE SET COVER problem. Given a universe $U$ containing $b$ blue elements and $r$ red elements, positive integers $k_\ell$ and $k_r$, and a family $\F$ of $\ell$ sets over $U$, the \srbsc\ problem is to decide whether there is a subfamily $\F'\subseteq \F$ of size at most $k_\ell$ that covers all blue elements, but at most $k_r$ of the red elements. This generalizes SET COVER and thus in full generality it is intractable in the parameterized setting. In this paper, we study a geometric version of this problem, called Gen-RBSC-lines, where the elements are points in the plane and sets are defined by lines. We study this problem for an array of parameters, namely, $k_\ell, k_r, r, b$, and $\ell$, and all possible combinations of them. For all these cases, we either prove that the problem is W-hard or show that the problem is fixed parameter tractable (FPT). In particular, on the algorithmic side, our study shows that a combination of $k_\ell$ and $k_r$ gives rise to a nontrivial algorithm for Gen-RBSC-lines. On the hardness side, we show that the problem is para-NP-hard when parameterized by $k_r$, and W[1]-hard when parameterized by $k_\ell$. Finally, for the combination of parameters for which Gen-RBSC-lines admits FPT algorithms, we ask for the existence of polynomial kernels. We are able to provide a complete kernelization dichotomy by either showing that the problem admits a polynomial kernel or that it does not contain a polynomial kernel unless $\CoNP \subseteq \NP/\mbox{poly}$.