OpenRaiser/Intern-Atlas huggingface dataset:
Kernel Alignment Inspired Linear Discriminant Analysis
Venue: arXiv cs.LG 2016
Year: 2016

Kernel alignment measures the degree of similarity between two kernels. In this paper, inspired from kernel alignment, we propose a new Linear Discriminant Analysis (LDA) formulation, kernel alignment LDA (kaLDA). We first define two kernels, data kernel and class indicator kernel. The problem is to find a subspace to maximize the alignment between subspace-transformed data kernel and class indicator kernel. Surprisingly, the kernel alignment induced kaLDA objective function is very similar to classical LDA and can be expressed using between-class and total scatter matrices. This can be extended to multi-label data. We use a Stiefel-manifold gradient descent algorithm to solve this problem. We perform experiments on 8 single-label and 6 multi-label data sets. Results show that kaLDA has very good performance on many single-label and multi-label problems.
Message-passing algorithms for synchronization problems over compact groups
Venue: arXiv cs.IT 2016
Year: 2016

Various alignment problems arising in cryo-electron microscopy, community detection, time synchronization, computer vision, and other fields fall into a common framework of synchronization problems over compact groups such as Z/L, U(1), or SO(3). The goal of such problems is to estimate an unknown vector of group elements given noisy relative observations. We present an efficient iterative algorithm to solve a large class of these problems, allowing for any compact group, with measurements on multiple 'frequency channels' (Fourier modes, or more generally, irreducible representations of the group). Our algorithm is a highly efficient iterative method following the blueprint of approximate message passing (AMP), which has recently arisen as a central technique for inference problems such as structured low-rank estimation and compressed sensing. We augment the standard ideas of AMP with ideas from representation theory so that the algorithm can work with distributions over compact groups. Using standard but non-rigorous methods from statistical physics we analyze the behavior of our algorithm on a Gaussian noise model, identifying phases where the problem is easy, (computationally) hard, and (statistically) impossible. In particular, such evidence predicts that our algorithm is information-theoretically optimal in many cases, and that the remaining cases show evidence of statistical-to-computational gaps.
Application of Global Route-Planning Algorithms with Geodesy
Venue: arXiv cs.DS 2016
Year: 2016

Global Route-Planning Algorithms (GRPA) are required to compute paths between several points located on Earth's surface. A geodesic algorithm is employed as an auxiliary tool, increasing the precision of distance calculations. This work presents a novel simulator for GRPA, which compares and evaluates three GRPAs implemented to solve the shortest path problem for points located at different cities: A*, LPA*, and D*Lite. The performance of each algorithm is investigated with a set of experiments, which are executed to check the answers provided by the algorithms and to compare their execution time. It is shown that GRPAs implementations with consistent heuristics lead to optimal paths. The noticeable differences among those algorithms are related to the time execution after successive executions.
On plant roots logical gates
Venue: arXiv cs.ET 2016
Year: 2016

Theoretical constructs of logical gates implemented with plant roots are morphological computing asynchronous devices. Values of Boolean variables are represented by plant roots. A presence of a plant root at a given site symbolises the logical {\sc True}, an absence the logical {\sc False}. Logical functions are calculated via interaction between roots. Two types of two-inputs-two-outputs gates are proposed: a gate $\langle x, y \rangle \rightarrow \langle xy, x+y \rangle$ where root apexes are guided by gravity and a gate $\langle x, y \rangle \rightarrow \langle \overline{x}y, x \rangle$ where root apexes are guided by humidity. We propose a design of binary half-adder based on the gates.
Refinement Reflection (or, how to turn your favorite language into a proof assistant using SMT)
Venue: arXiv cs.PL 2016
Year: 2016

Refinement Reflection turns your favorite programming language into a proof assistant by reflecting the code implementing a user-defined function into the function's (output) refinement type. As a consequence, at uses of the function, the function definition is unfolded into the refinement logic in a precise, predictable and most importantly, programmer controllable way. In the logic, we encode functions and lambdas using uninterpreted symbols preserving SMT-based decidable verification. In the language, we provide a library of combinators that lets programmers compose proofs from basic refinements and function definitions. We have implemented our approach in the Liquid Haskell system, thereby converting Haskell into an interactive proof assistant, that we used to verify a variety of properties ranging from arithmetic properties of higher order, recursive functions to the Monoid, Applicative, Functor and Monad type class laws for a variety of instances.
A Closed Form Solution to Multi-View Low-Rank Regression
Venue: arXiv cs.LG 2016
Year: 2016

Real life data often includes information from different channels. For example, in computer vision, we can describe an image using different image features, such as pixel intensity, color, HOG, GIST feature, SIFT features, etc.. These different aspects of the same objects are often called multi-view (or multi-modal) data. Low-rank regression model has been proved to be an effective learning mechanism by exploring the low-rank structure of real life data. But previous low-rank regression model only works on single view data. In this paper, we propose a multi-view low-rank regression model by imposing low-rank constraints on multi-view regression model. Most importantly, we provide a closed-form solution to the multi-view low-rank regression model. Extensive experiments on 4 multi-view datasets show that the multi-view low-rank regression model outperforms single-view regression model and reveals that multi-view low-rank structure is very helpful.
ExpressPass: End-to-End Credit-based Congestion Control for Datacenters
Venue: arXiv cs.NI 2016
Year: 2016

As link speeds increase in datacenter networks, existing congestion control algorithms become less effective in providing fast convergence. TCP-based algorithms that probe for bandwidth take a long time to reach the fair-share and lead to long flow completion times. An ideal congestion control algorithms for datacenter must provide 1) zero data loss, 2) fast convergence, and 3) low buffer occupancy. However, these requirements present conflicting goals. For fast convergence,flows must ramp up quickly, but this risks packet losses and large queues. Thus, even the state-of-the-art algorithms, such as TIMELY and DCQCN, rely on link layer flow control (e.g.,Priority-based Flow Control) to achieve zero loss. This paper presents a new approach, called ExpressPass, an end-to-end credit-based congestion control algorithm for datacenters. ExpressPass is inspired by credit-based flow control, but extends it to work end-to-end. The switches control the amount of credit packets by rate limiting and ensure data packets flow in the reverse direction without any loss. ExpressPass leverages this to ramp up aggressively. ExpressPass converges up to 80 times faster than DCTCP at 10Gbps link, and the gap increases as link speeds become faster. Our simulation with realistic workload shows that ExpressPass significantly reduces the flow completion time especially for small and medium size flows compared to DCTCP, HULL, and DX.
A New Perspective on Randomized Gossip Algorithms
Venue: arXiv cs.DC 2016
Year: 2016

In this short note we propose a new approach for the design and analysis of randomized gossip algorithms which can be used to solve the average consensus problem. We show how that Randomized Block Kaczmarz (RBK) method - a method for solving linear systems - works as gossip algorithm when applied to a special system encoding the underlying network. The famous pairwise gossip algorithm arises as a special case. Subsequently, we reveal a hidden duality of randomized gossip algorithms, with the dual iterative process maintaining a set of numbers attached to the edges as opposed to nodes of the network. We prove that RBK obtains a superlinear speedup in the size of the block, and demonstrate this effect through experiments.
Preserving the value of large scale data analytics over time through selective re-computation
Venue: arXiv cs.DB 2016
Year: 2016

A pervasive problem in Data Science is that the knowledge generated by possibly expensive analytics processes is subject to decay over time, as the data used to compute it drifts, the algorithms used in the processes are improved, and the external knowledge embodied by reference datasets used in the computation evolves. Deciding when such knowledge outcomes should be refreshed, following a sequence of data change events, requires problem-specific functions to quantify their value and its decay over time, as well as models for estimating the cost of their re-computation. What makes this problem challenging is the ambition to develop a decision support system for informing data analytics re-computation decisions over time, that is both generic and customisable. With the help of a case study from genomics, in this vision paper we offer an initial formalisation of this problem, highlight research challenges, and outline a possible approach based on the collection and analysis of metadata from a history of past computations.
Semi-Supervised Source Localization on Multiple-Manifolds with Distributed Microphones
Venue: arXiv cs.SD 2016
Year: 2016

The problem of source localization with ad hoc microphone networks in noisy and reverberant enclosures, given a training set of prerecorded measurements, is addressed in this paper. The training set is assumed to consist of a limited number of labelled measurements, attached with corresponding positions, and a larger amount of unlabelled measurements from unknown locations. However, microphone calibration is not required. We use a Bayesian inference approach for estimating a function that maps measurement-based feature vectors to the corresponding positions. The central issue is how to combine the information provided by the different microphones in a unified statistical framework. To address this challenge, we model this function using a Gaussian process with a covariance function that encapsulates both the connections between pairs of microphones and the relations among the samples in the training set. The parameters of the process are estimated by optimizing a maximum likelihood (ML) criterion. In addition, a recursive adaptation mechanism is derived where the new streaming measurements are used to update the model. Performance is demonstrated for 2-D localization of both simulated data and real-life recordings in a variety of reverberation and noise levels.
On Finding Small Sets that Influence Large Networks
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of selecting a minimum size subset of nodes in a network, that allows to activate all the nodes of the network. We present a fast and simple algorithm that, in real-life networks, produces solutions that outperform the ones obtained by using the best algorithms in the literature. We also investigate the theoretical performances of our algorithm and give proofs of optimality for some classes of graphs. From an experimental perspective, experiments also show that the performance of the algorithms correlates with the modularity of the analyzed network. Moreover, the more the influence among communities is hard to propagate, the less the performances of the algorithms differ. On the other hand, when the network allows some propagation of influence between different communities, the gap between the solutions returned by the proposed algorithm and by the previous algorithms in the literature increases.
Efficient Rectangular Maximal-Volume Algorithm for Rating Elicitation in Collaborative Filtering
Venue: arXiv cs.IR 2016
Year: 2016

Cold start problem in Collaborative Filtering can be solved by asking new users to rate a small seed set of representative items or by asking representative users to rate a new item. The question is how to build a seed set that can give enough preference information for making good recommendations. One of the most successful approaches, called Representative Based Matrix Factorization, is based on Maxvol algorithm. Unfortunately, this approach has one important limitation --- a seed set of a particular size requires a rating matrix factorization of fixed rank that should coincide with that size. This is not necessarily optimal in the general case. In the current paper, we introduce a fast algorithm for an analytical generalization of this approach that we call Rectangular Maxvol. It allows the rank of factorization to be lower than the required size of the seed set. Moreover, the paper includes the theoretical analysis of the method's error, the complexity analysis of the existing methods and the comparison to the state-of-the-art approaches.
Digital Makeup from Internet Images
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel approach of color transfer between images by exploring their high-level semantic information. First, we set up a database which consists of the collection of downloaded images from the internet, which are segmented automatically by using matting techniques. We then, extract image foregrounds from both source and multiple target images. Then by using image matting algorithms, the system extracts the semantic information such as faces, lips, teeth, eyes, eyebrows, etc., from the extracted foregrounds of the source image. And, then the color is transferred between corresponding parts with the same semantic information. Next we get the color transferred result by seamlessly compositing different parts together using alpha blending. In the final step, we present an efficient method of color consistency to optimize the color of a collection of images showing the common scene. The main advantage of our method over existing techniques is that it does not need face matching, as one could use more than one target images. It is not restricted to head shot images as we can also change the color style in the wild. Moreover, our algorithm does not require to choose the same color style, same pose and image size between source and target images. Our algorithm is not restricted to one-to-one image color transfer and can make use of more than one target images to transfer the color in different parts in the source image. Comparing with other approaches, our algorithm is much better in color blending in the input data.
What is the Best Way for Extracting Meaningful Attributes from Pictures?
Venue: arXiv cs.CV 2016
Year: 2016

Automatic attribute discovery methods have gained in popularity to extract sets of visual attributes from images or videos for various tasks. Despite their good performance in some classification tasks, it is difficult to evaluate whether the attributes discovered by these methods are meaningful and which methods are the most appropriate to discover attributes for visual descriptions. In its simplest form, such an evaluation can be performed by manually verifying whether there is any consistent identifiable visual concept distinguishing between positive and negative exemplars labelled by an attribute. This manual checking is tedious, expensive and labour intensive. In addition, comparisons between different methods could also be problematic as it is not clear how one could quantitatively decide which attribute is more meaningful than the others. In this paper, we propose a novel attribute meaningfulness metric to address this challenging problem. With this metric, automatic quantitative evaluation can be performed on the attribute sets; thus, reducing the enormous effort to perform manual evaluation. The proposed metric is applied to some recent automatic attribute discovery and hashing methods on four attribute-labelled datasets. To further validate the efficacy of the proposed method, we conducted a user study. In addition, we also compared our metric with a semi-supervised attribute discover method using the mixture of probabilistic PCA. In our evaluation, we gleaned several insights that could be beneficial in developing new automatic attribute discovery methods.
Improvements in Sub-optimal Solving of the $(N^2-1)$-Puzzle via Joint Relocation of Pebbles and its Applications to Rule-based Cooperative Path-Finding
Venue: arXiv cs.AI 2016
Year: 2016

The problem of solving $(n^2-1)$-puzzle and cooperative path-finding (CPF) sub-optimally by rule based algorithms is addressed in this manuscript. The task in the puzzle is to rearrange $n^2-1$ pebbles on the square grid of the size of n x n using one vacant position to a desired goal configuration. An improvement to the existent polynomial-time algorithm is proposed and experimentally analyzed. The improved algorithm is trying to move pebbles in a more efficient way than the original algorithm by grouping them into so-called snakes and moving them jointly within the snake. An experimental evaluation showed that the algorithm using snakes produces solutions that are 8% to 9% shorter than solutions generated by the original algorithm. The snake-based relocation has been also integrated into rule-based algorithms for solving the CPF problem sub-optimally, which is a closely related task. The task in CPF is to relocate a group of abstract robots that move over an undirected graph to given goal vertices. Robots can move to unoccupied neighboring vertices and at most one robot can be placed in each vertex. The $(n^2-1)$-puzzle is a special case of CPF where the underlying graph is represented by a 4-connected grid and there is only one vacant vertex. Two major rule-based algorithms for CPF were included in our study - BIBOX and PUSH-and-SWAP (PUSH-and-ROTATE). Improvements gained by using snakes in the BIBOX algorithm were stable around 30% in $(n^2-1)$-puzzle solving and up to 50% in CPFs over bi-connected graphs with various ear decompositions and multiple vacant vertices. In the case of the PUSH-and-SWAP algorithm the improvement achieved by snakes was around 5% to 8%. However, the improvement was unstable and hardly predictable in the case of PUSH-and-SWAP.
Identification of Intended Arm Movement Using Electrocorticographic Signals
Venue: arXiv cs.HC 2016
Year: 2016

A Brain Computer Interface (BCI) is a communication system that receives neurological signals from the brain and translates them into control commands for electrical (e.g., computer mouse) and electromechanical (e.g., Wheelchair) devices. The development of such systems was intended originally to aid individuals with a condition called locked-in syndrome. Individuals with this condition have lost all their voluntary muscle control but remain cognitively intact (i.e., mentally aware of their surroundings- can feel emotions, recognize objects/people but are unable to move). This means that they are trapped in their own bodies. The use of BCI may one day improve the independence and quality of life of people with this disability.
Encoding the Local Connectivity Patterns of fMRI for Cognitive State Classification
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we propose a novel framework to encode the local connectivity patterns of brain, using Fisher Vectors (FV), Vector of Locally Aggregated Descriptors (VLAD) and Bag-of-Words (BoW) methods. We first obtain local descriptors, called Mesh Arc Descriptors (MADs) from fMRI data, by forming local meshes around anatomical regions, and estimating their relationship within a neighborhood. Then, we extract a dictionary of relationships, called \textit{brain connectivity dictionary} by fitting a generative Gaussian mixture model (GMM) to a set of MADs, and selecting the codewords at the mean of each component of the mixture. Codewords represent the connectivity patterns among anatomical regions. We also encode MADs by VLAD and BoW methods using the k-Means clustering. We classify the cognitive states of Human Connectome Project (HCP) task fMRI dataset, where we train support vector machines (SVM) by the encoded MADs. Results demonstrate that, FV encoding of MADs can be successfully employed for classification of cognitive tasks, and outperform the VLAD and BoW representations. Moreover, we identify the significant Gaussians in mixture models by computing energy of their corresponding FV parts, and analyze their effect on classification accuracy. Finally, we suggest a new method to visualize the codewords of brain connectivity dictionary.
Internet of Things Applications: Animal Monitoring with Unmanned Aerial Vehicle
Venue: arXiv cs.AI 2016
Year: 2016

In animal monitoring applications, both animal detection and their movement prediction are major tasks. While a variety of animal monitoring strategies exist, most of them rely on mounting devices. However, in real world, it is difficult to find these animals and install mounting devices. In this paper, we propose an animal monitoring application by utilizing wireless sensor networks (WSNs) and unmanned aerial vehicle (UAV). The objective of the application is to detect locations of endangered species in large-scale wildlife areas and monitor movement of animals without any attached devices. In this application, sensors deployed throughout the observation area are responsible for gathering animal information. The UAV flies above the observation area and collects the information from sensors. To achieve the information efficiently, we propose a path planning approach for the UAV based on a Markov decision process (MDP) model. The UAV receives a certain amount of reward from an area if some animals are detected at that location. We solve the MDP using Q-learning such that the UAV prefers going to those areas that animals are detected before. Meanwhile, the UAV explores other areas as well to cover the entire network and detects changes in the animal positions. We first define the mathematical model underlying the animal monitoring problem in terms of the value of information (VoI) and rewards. We propose a network model including clusters of sensor nodes and a single UAV that acts as a mobile sink and visits the clusters. Then, one MDP-based path planning approach is designed to maximize the VoI while reducing message delays. The effectiveness of the proposed approach is evaluated using two real-world movement datasets of zebras and leopard. Simulation results show that our approach outperforms greedy, random heuristics and the path planning based on the traveling salesman problem.
Sequential Learning without Feedback
Venue: arXiv cs.LG 2016
Year: 2016

In many security and healthcare systems a sequence of features/sensors/tests are used for detection and diagnosis. Each test outputs a prediction of the latent state, and carries with it inherent costs. Our objective is to {\it learn} strategies for selecting tests to optimize accuracy \& costs. Unfortunately it is often impossible to acquire in-situ ground truth annotations and we are left with the problem of unsupervised sensor selection (USS). We pose USS as a version of stochastic partial monitoring problem with an {\it unusual} reward structure (even noisy annotations are unavailable). Unsurprisingly no learner can achieve sublinear regret without further assumptions. To this end we propose the notion of weak-dominance. This is a condition on the joint probability distribution of test outputs and latent state and says that whenever a test is accurate on an example, a later test in the sequence is likely to be accurate as well. We empirically verify that weak dominance holds on real datasets and prove that it is a maximal condition for achieving sublinear regret. We reduce USS to a special case of multi-armed bandit problem with side information and develop polynomial time algorithms that achieve sublinear regret.