OpenRaiser/Intern-Atlas huggingface dataset:
On the Weight Hierarchy of Locally Repairable Codes
Venue: arXiv cs.IT 2017
Year: 2017

An $(n,k,r)$ \emph{locally repairable code} (LRC) is an $[n,k,d]$ linear code where every code symbol can be repaired from at most $r$ other code symbols. An LRC is said to be optimal if the minimum distance attains the Singleton-like bound $d \le n-k-\lceil k/r \rceil +2$. The \emph{generalized Hamming weights} (GHWs) of linear codes are fundamental parameters which have many useful applications. Generally it is difficult to determine the GHWs of linear codes. In this paper, we study the GHWs of LRCs. Firstly, we obtain a generalized Singleton-like bound on the $i$-th $(1\le i \le k)$ GHWs of general $(n,k,r)$ LRCs. Then, it is shown that for an optimal $(n,k,r)$ LRC with $r \mid k$, its weight hierarchy can be completely determined, and the $i$-th GHW of an optimal $(n,k,r)$ LRC with $r \mid k$ attains the proposed generalized Singleton-like bound for all $1\le i \le k$. For an optimal $(n,k,r)$ LRC with $r \nmid k$, we give lower bounds on the GHWs of the LRC and its dual code. Finally, two general bounds on linear codes in terms of the GHWs are presented. Moreover, it is also shown that some previous results on the bounds of minimum distances of linear codes can also be explained or refined in terms of the GHWs.
Multi-Sensor Control for Multi-Object Bayes Filters
Venue: arXiv cs.SY 2017
Year: 2017

Sensor management in multi-object stochastic systems is a theoretically and computationally challenging problem. This paper presents a novel approach to the multi-target multi-sensor control problem within the partially observed Markov decision process (POMDP) framework. We model the multi-object state as a labeled multi-Bernoulli random finite set (RFS), and use the labeled multi-Bernoulli filter in conjunction with minimizing a task-driven control objective function: posterior expected error of cardinality and state (PEECS). A major contribution is a guided search for multi-dimensional optimization in the multi-sensor control command space, using coordinate descent method. In conjunction with the Generalized Covariance Intersection method for multi-sensor fusion, a fast multi-sensor algorithm is achieved. Numerical studies are presented in several scenarios where numerous controllable (mobile) sensors track multiple moving targets with different levels of observability. The results show that our method works significantly faster than the approach taken by a state of art method, with similar tracking errors.
Multiplicities of Character Values of Binary Sidel'nikov-Lempel-Cohn-Eastman Sequences
Venue: arXiv cs.IT 2017
Year: 2017

Binary Sidel'nikov-Lempel-Cohn-Eastman sequences (or SLCE sequences) over F 2 have even period and almost perfect autocorrelation. However, the evaluation of the linear complexity of these sequences is really difficult. In this paper, we continue the study of [1]. We first express the multiple roots of character polynomials of SLCE sequences into certain kinds of Jacobi sums. Then by making use of Gauss sums and Jacobi sums in the "semiprimitive" case, we derive new divisibility results for SLCE sequences.
Cosine Normalization: Using Cosine Similarity Instead of Dot Product in Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Traditionally, multi-layer neural networks use dot product between the output vector of previous layer and the incoming weight vector as the input to activation function. The result of dot product is unbounded, thus increases the risk of large variance. Large variance of neuron makes the model sensitive to the change of input distribution, thus results in poor generalization, and aggravates the internal covariate shift which slows down the training. To bound dot product and decrease the variance, we propose to use cosine similarity or centered cosine similarity (Pearson Correlation Coefficient) instead of dot product in neural networks, which we call cosine normalization. We compare cosine normalization with batch, weight and layer normalization in fully-connected neural networks as well as convolutional networks on the data sets of MNIST, 20NEWS GROUP, CIFAR-10/100 and SVHN. Experiments show that cosine normalization achieves better performance than other normalization techniques.
From Photo Streams to Evolving Situations
Venue: arXiv cs.MM 2017
Year: 2017

Photos are becoming spontaneous, objective, and universal sources of information. This paper develops evolving situation recognition using photo streams coming from disparate sources combined with the advances of deep learning. Using visual concepts in photos together with space and time information, we formulate the situation detection into a semi-supervised learning framework and propose new graph-based models to solve the problem. To extend the method for unknown situations, we introduce a soft label method which enables the traditional semi-supervised learning framework to accurately predict predefined labels as well as effectively form new clusters. To overcome the noisy data which degrades graph quality, leading to poor recognition results, we take advantage of two kinds of noise-robust norms which can eliminate the adverse effects of outliers in visual concepts and improve the accuracy of situation recognition. Finally, we demonstrate the idea and the effectiveness of the proposed model on Yahoo Flickr Creative Commons 100 Million.
Mobility Increases the Data Offloading Ratio in D2D Caching Networks
Venue: arXiv cs.IT 2017
Year: 2017

Caching at mobile devices, accompanied by device-to-device (D2D) communications, is one promising technique to accommodate the exponentially increasing mobile data traffic. While most previous works ignored user mobility, there are some recent works taking it into account. However, the duration of user contact times has been ignored, making it difficult to explicitly characterize the effect of mobility. In this paper, we adopt the alternating renewal process to model the duration of both the contact and inter-contact times, and investigate how the caching performance is affected by mobility. The data offloading ratio, i.e., the proportion of requested data that can be delivered via D2D links, is taken as the performance metric. We first approximate the distribution of the communication time for a given user by beta distribution through moment matching. With this approximation, an accurate expression of the data offloading ratio is derived. For the homogeneous case where the average contact and inter-contact times of different user pairs are identical, we prove that the data offloading ratio increases with the user moving speed, assuming that the transmission rate remains the same. Simulation results are provided to show the accuracy of the approximate result, and also validate the effect of user mobility.
$δ$-Greedy $t$-spanner
Venue: arXiv cs.CG 2017
Year: 2017

We introduce a new geometric spanner, $δ$-Greedy, whose construction is based on a generalization of the known Path-Greedy and Gap-Greedy spanners. The $δ$-Greedy spanner combines the most desirable properties of geometric spanners both in theory and in practice. More specifically, it has the same theoretical and practical properties as the Path-Greedy spanner: a natural definition, small degree, linear number of edges, low weight, and strong $(1+\varepsilon)$-spanner for every $\varepsilon>0$. The $δ$-Greedy algorithm is an improvement over the Path-Greedy algorithm with respect to the number of shortest path queries and hence with respect to its construction time. We show how to construct such a spanner for a set of $n$ points in the plane in $O(n^2 \log n)$ time. The $δ$-Greedy spanner has an additional parameter, $δ$, which indicates how close it is to the Path-Greedy spanner on the account of the number of shortest path queries. For $δ= t$ the output spanner is identical to the Path-Greedy spanner, while the number of shortest path queries is, in practice, linear. Finally, we show that for a set of $n$ points placed independently at random in a unit square the expected construction time of the $δ$-Greedy algorithm is $O(n \log n)$. Our analysis indicates that the $δ$-Greedy spanner gives the best results among the known spanners of expected $O(n \log n)$ time for random point sets. Moreover, the analysis implies that by setting $δ= t$, the $δ$-Greedy algorithm provides a spanner identical to the Path-Greedy spanner in expected $O(n \log n)$ time.
An Efficient Method for online Detection of Polychronous Patterns in Spiking Neural Network
Venue: arXiv cs.NE 2017
Year: 2017

Polychronous neural groups are effective structures for the recognition of precise spike-timing patterns but the detection method is an inefficient multi-stage brute force process that works off-line on pre-recorded simulation data. This work presents a new model of polychronous patterns that can capture precise sequences of spikes directly in the neural simulation. In this scheme, each neuron is assigned a randomized code that is used to tag the post-synaptic neurons whenever a spike is transmitted. This creates a polychronous code that preserves the order of pre-synaptic activity and can be registered in a hash table when the post-synaptic neuron spikes. A polychronous code is a sub-component of a polychronous group that will occur, along with others, when the group is active. We demonstrate the representational and pattern recognition ability of polychronous codes on a direction selective visual task involving moving bars that is typical of a computation performed by simple cells in the cortex. The computational efficiency of the proposed algorithm far exceeds existing polychronous group detection methods and is well suited for online detection.
Automatic Liver and Tumor Segmentation of CT and MRI Volumes using Cascaded Fully Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Automatic segmentation of the liver and hepatic lesions is an important step towards deriving quantitative biomarkers for accurate clinical diagnosis and computer-aided decision support systems. This paper presents a method to automatically segment liver and lesions in CT and MRI abdomen images using cascaded fully convolutional neural networks (CFCNs) enabling the segmentation of a large-scale medical trial or quantitative image analysis. We train and cascade two FCNs for a combined segmentation of the liver and its lesions. In the first step, we train a FCN to segment the liver as ROI input for a second FCN. The second FCN solely segments lesions within the predicted liver ROIs of step 1. CFCN models were trained on an abdominal CT dataset comprising 100 hepatic tumor volumes. Validations on further datasets show that CFCN-based semantic liver and lesion segmentation achieves Dice scores over 94% for liver with computation times below 100s per volume. We further experimentally demonstrate the robustness of the proposed method on an 38 MRI liver tumor volumes and the public 3DIRCAD dataset.
An Extended Framework for Marginalized Domain Adaptation
Venue: arXiv cs.CV 2017
Year: 2017

We propose an extended framework for marginalized domain adaptation, aimed at addressing unsupervised, supervised and semi-supervised scenarios. We argue that the denoising principle should be extended to explicitly promote domain-invariant features as well as help the classification task. Therefore we propose to jointly learn the data auto-encoders and the target classifiers. First, in order to make the denoised features domain-invariant, we propose a domain regularization that may be either a domain prediction loss or a maximum mean discrepancy between the source and target data. The noise marginalization in this case is reduced to solving the linear matrix system $AX=B$ which has a closed-form solution. Second, in order to help the classification, we include a class regularization term. Adding this component reduces the learning problem to solving a Sylvester linear matrix equation $AX+BX=C$, for which an efficient iterative procedure exists as well. We did an extensive study to assess how these regularization terms improve the baseline performance in the three domain adaptation scenarios and present experimental results on two image and one text benchmark datasets, conventionally used for validating domain adaptation methods. We report our findings and comparison with state-of-the-art methods.
Learning Non-Discriminatory Predictors
Venue: arXiv cs.LG 2017
Year: 2017

We consider learning a predictor which is non-discriminatory with respect to a "protected attribute" according to the notion of "equalized odds" proposed by Hardt et al. [2016]. We study the problem of learning such a non-discriminatory predictor from a finite training set, both statistically and computationally. We show that a post-hoc correction approach, as suggested by Hardt et al, can be highly suboptimal, present a nearly-optimal statistical procedure, argue that the associated computational problem is intractable, and suggest a second moment relaxation of the non-discrimination definition for which learning is tractable.
On the Consistency of $k$-means++ algorithm
Venue: arXiv cs.LG 2017
Year: 2017

We prove in this paper that the expected value of the objective function of the $k$-means++ algorithm for samples converges to population expected value. As $k$-means++, for samples, provides with constant factor approximation for $k$-means objectives, such an approximation can be achieved for the population with increase of the sample size. This result is of potential practical relevance when one is considering using subsampling when clustering large data sets (large data bases).
Developing a comprehensive framework for multimodal feature extraction
Venue: arXiv cs.CV 2017
Year: 2017

Feature extraction is a critical component of many applied data science workflows. In recent years, rapid advances in artificial intelligence and machine learning have led to an explosion of feature extraction tools and services that allow data scientists to cheaply and effectively annotate their data along a vast array of dimensions---ranging from detecting faces in images to analyzing the sentiment expressed in coherent text. Unfortunately, the proliferation of powerful feature extraction services has been mirrored by a corresponding expansion in the number of distinct interfaces to feature extraction services. In a world where nearly every new service has its own API, documentation, and/or client library, data scientists who need to combine diverse features obtained from multiple sources are often forced to write and maintain ever more elaborate feature extraction pipelines. To address this challenge, we introduce a new open-source framework for comprehensive multimodal feature extraction. Pliers is an open-source Python package that supports standardized annotation of diverse data types (video, images, audio, and text), and is expressly with both ease-of-use and extensibility in mind. Users can apply a wide range of pre-existing feature extraction tools to their data in just a few lines of Python code, and can also easily add their own custom extractors by writing modular classes. A graph-based API enables rapid development of complex feature extraction pipelines that output results in a single, standardized format. We describe the package's architecture, detail its major advantages over previous feature extraction toolboxes, and use a sample application to a large functional MRI dataset to illustrate how pliers can significantly reduce the time and effort required to construct sophisticated feature extraction workflows while increasing code clarity and maintainability.
Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization
Venue: arXiv cs.LG 2017
Year: 2017

This paper concerns the problem of recovering an unknown but structured signal $x \in R^n$ from $m$ quadratic measurements of the form $y_r=|<a_r,x>|^2$ for $r=1,2,...,m$. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal ($m<<n$). We formulate the recovery problem as a nonconvex optimization problem where prior structural information about the signal is enforced through constrains on the optimization variables. We prove that projected gradient descent, when initialized in a neighborhood of the desired signal, converges to the unknown signal at a linear rate. These results hold for any constraint set (convex or nonconvex) providing convergence guarantees to the global optimum even when the objective function and constraint set is nonconvex. Furthermore, these results hold with a number of measurements that is only a constant factor away from the minimal number of measurements required to uniquely identify the unknown signal. Our results provide the first provably tractable algorithm for this data-poor regime, breaking local sample complexity barriers that have emerged in recent literature. In a companion paper we demonstrate favorable properties for the optimization problem that may enable similar results to continue to hold more globally (over the entire ambient space). Collectively these two papers utilize and develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics. The mathematical results in this paper also pave the way for a new generation of data-driven phase-less imaging systems that can utilize prior information to significantly reduce acquisition time and enhance image reconstruction, enabling nano-scale imaging at unprecedented speeds and resolutions.
A Graphical Evolutionary Game Approach to Social Learning
Venue: arXiv cs.GT 2017
Year: 2017

In this work, we study the social learning problem, in which agents of a networked system collaborate to detect the state of the nature based on their private signals. A novel distributed graphical evolutionary game theoretic learning method is proposed. In the proposed game-theoretic method, agents only need to communicate their binary decisions rather than the real-valued beliefs with their neighbors, which endows the method with low communication complexity. Under mean field approximations, we theoretically analyze the steady state equilibria of the game and show that the evolutionarily stable states (ESSs) coincide with the decisions of the benchmark centralized detector. Numerical experiments are implemented to confirm the effectiveness of the proposed game-theoretic learning method.
A $(1.4 + ε)$-approximation algorithm for the $2$-Max-Duo problem
Venue: arXiv cs.DS 2017
Year: 2017

The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. $k$-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most $k$ times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree $Δ\le 6(k-1)$. In particular, $2$-Max-Duo can then be approximated arbitrarily close to $1.8$ using the state-of-the-art approximation algorithm for the MIS problem. $2$-Max-Duo was proved APX-hard and very recently a $(1.6 + ε)$-approximation was claimed, for any $ε> 0$. In this paper, we present a vertex-degree reduction technique, based on which, we show that $2$-Max-Duo can be approximated arbitrarily close to $1.4$.
Convolutional Recurrent Neural Networks for Polyphonic Sound Event Detection
Venue: arXiv cs.LG 2017
Year: 2017

Sound events often occur in unstructured environments where they exhibit wide variations in their frequency content and temporal structure. Convolutional neural networks (CNN) are able to extract higher level features that are invariant to local spectral and temporal variations. Recurrent neural networks (RNNs) are powerful in learning the longer term temporal context in the audio signals. CNNs and RNNs as classifiers have recently shown improved performances over established methods in various sound recognition tasks. We combine these two approaches in a Convolutional Recurrent Neural Network (CRNN) and apply it on a polyphonic sound event detection task. We compare the performance of the proposed CRNN method with CNN, RNN, and other established methods, and observe a considerable improvement for four different datasets consisting of everyday sound events.
Towards a Common Implementation of Reinforcement Learning for Multiple Robotic Tasks
Venue: arXiv cs.AI 2017
Year: 2017

Mobile robots are increasingly being employed for performing complex tasks in dynamic environments. Reinforcement learning (RL) methods are recognized to be promising for specifying such tasks in a relatively simple manner. However, the strong dependency between the learning method and the task to learn is a well-known problem that restricts practical implementations of RL in robotics, often requiring major modifications of parameters and adding other techniques for each particular task. In this paper we present a practical core implementation of RL which enables the learning process for multiple robotic tasks with minimal per-task tuning or none. Based on value iteration methods, this implementation includes a novel approach for action selection, called Q-biased softmax regression (QBIASSR), which avoids poor performance of the learning process when the robot reaches new unexplored states. Our approach takes advantage of the structure of the state space by attending the physical variables involved (e.g., distances to obstacles, X,Y,θ pose, etc.), thus experienced sets of states may favor the decision-making process of unexplored or rarely-explored states. This improvement has a relevant role in reducing the tuning of the algorithm for particular tasks. Experiments with real and simulated robots, performed with the software framework also introduced here, show that our implementation is effectively able to learn different robotic tasks without tuning the learning method. Results also suggest that the combination of true online SARSA(λ) with QBIASSR can outperform the existing RL core algorithms in low-dimensional robotic tasks.
Edge-Fog Cloud: A Distributed Cloud for Internet of Things Computations
Venue: arXiv cs.DC 2017
Year: 2017

Internet of Things typically involves a significant number of smart sensors sensing information from the environment and sharing it to a cloud service for processing. Various architectural abstractions, such as Fog and Edge computing, have been proposed to localize some of the processing near the sensors and away from the central cloud servers. In this paper, we propose Edge-Fog Cloud which distributes task processing on the participating cloud resources in the network. We develop the Least Processing Cost First (LPCF) method for assigning the processing tasks to nodes which provide the optimal processing time and near optimal networking costs. We evaluate LPCF in a variety of scenarios and demonstrate its effectiveness in finding the processing task assignments.
Hybrid Dialog State Tracker with ASR Features
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents a hybrid dialog state tracker enhanced by trainable Spoken Language Understanding (SLU) for slot-filling dialog systems. Our architecture is inspired by previously proposed neural-network-based belief-tracking systems. In addition, we extended some parts of our modular architecture with differentiable rules to allow end-to-end training. We hypothesize that these rules allow our tracker to generalize better than pure machine-learning based systems. For evaluation, we used the Dialog State Tracking Challenge (DSTC) 2 dataset - a popular belief tracking testbed with dialogs from restaurant information system. To our knowledge, our hybrid tracker sets a new state-of-the-art result in three out of four categories within the DSTC2.