OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Label Learning with Provable Guarantee
Venue: arXiv cs.LG 2016
Year: 2016

Here we study the problem of learning labels for large text corpora where each text can be assigned a variable number of labels. The problem might seem trivial when the label dimensionality is small and can be easily solved using a series of one-vs-all classifiers. However, as the label dimensionality increases to several thousand, the parameter space becomes extremely large, and it is no longer possible to use the one-vs-all technique. Here we propose a model based on the factorization of higher order moments of the words in the corpora, as well as the cross moment between the labels and the words for multi-label prediction. Our model provides guaranteed convergence bounds on the estimated parameters. Further, our model takes only three passes through the training dataset to extract the parameters, resulting in a highly scalable algorithm that can train on GB's of data consisting of millions of documents with hundreds of thousands of labels using a nominal resource of a single processor with 16GB RAM. Our model achieves 10x-15x order of speed-up on large-scale datasets while producing competitive performance in comparison with existing benchmark algorithms.
Learning Sparse Graphs Under Smoothness Prior
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we are interested in learning the underlying graph structure behind training data. Solving this basic problem is essential to carry out any graph signal processing or machine learning task. To realize this, we assume that the data is smooth with respect to the graph topology, and we parameterize the graph topology using an edge sampling function. That is, the graph Laplacian is expressed in terms of a sparse edge selection vector, which provides an explicit handle to control the sparsity level of the graph. We solve the sparse graph learning problem given some training data in both the noiseless and noisy settings. Given the true smooth data, the posed sparse graph learning problem can be solved optimally and is based on simple rank ordering. Given the noisy data, we show that the joint sparse graph learning and denoising problem can be simplified to designing only the sparse edge selection vector, which can be solved using convex optimization.
MUG: A Parameterless No-Reference JPEG Quality Evaluator Robust to Block Size and Misalignment
Venue: arXiv cs.CV 2016
Year: 2016

In this letter, a very simple no-reference image quality assessment (NR-IQA) model for JPEG compressed images is proposed. The proposed metric called median of unique gradients (MUG) is based on the very simple facts of unique gradient magnitudes of JPEG compressed images. MUG is a parameterless metric and does not need training. Unlike other NR-IQAs, MUG is independent to block size and cropping. A more stable index called MUG+ is also introduced. The experimental results on six benchmark datasets of natural images and a benchmark dataset of synthetic images show that MUG is comparable to the state-of-the-art indices in literature. In addition, its performance remains unchanged for the case of the cropped images in which block boundaries are not known. The MATLAB source code of the proposed metrics is available at https://dl.dropboxusercontent.com/u/74505502/MUG.m and https://dl.dropboxusercontent.com/u/74505502/MUGplus.m.
Boosting Nodes for Improving the Spread of Influence
Venue: arXiv cs.SI 2016
Year: 2016

Information diffusion in networks has received a lot of recent attention. Most previous work addresses the influence maximization problem of selecting an appropriate set of seed nodes to initiate the diffusion process so that the largest number of nodes is reached. Since the seed selection problem is NP hard, most solutions are sub-optimal. Furthermore, there may be settings in which the seed nodes are predetermined. Thus, a natural question that arise is: given a set of seed nodes, can we select a small set of nodes such that if we improve their reaction to the diffusion process, the largest increase in diffusion spread is achieved? We call this problem, the boost set selection problem. In this paper, we formalize this problem, study its complexity and propose appropriate algorithms. We also evaluate the effect of boosting in a number of real networks and report the increase of influence spread achieved for different seed sets, time limits in the diffusion process and other diffusion parameters.
Hyperspectral Unmixing with Endmember Variability using Partial Membership Latent Dirichlet Allocation
Venue: arXiv cs.CV 2016
Year: 2016

The application of Partial Membership Latent Dirichlet Allocation(PM-LDA) for hyperspectral endmember estimation and spectral unmixing is presented. PM-LDA provides a model for a hyperspectral image analysis that accounts for spectral variability and incorporates spatial information through the use of superpixel-based 'documents.' In our application of PM-LDA, we employ the Normal Compositional Model in which endmembers are represented as Normal distributions to account for spectral variability and proportion vectors are modeled as random variables governed by a Dirichlet distribution. The use of the Dirichlet distribution enforces positivity and sum-to-one constraints on the proportion values. Algorithm results on real hyperspectral data indicate that PM-LDA produces endmember distributions that represent the ground truth classes and their associated variability.
ZaliQL: A SQL-Based Framework for Drawing Causal Inference from Big Data
Venue: arXiv cs.DB 2016
Year: 2016

Causal inference from observational data is a subject of active research and development in statistics and computer science. Many toolkits have been developed for this purpose that depends on statistical software. However, these toolkits do not scale to large datasets. In this paper we describe a suite of techniques for expressing causal inference tasks from observational data in SQL. This suite supports the state-of-the-art methods for causal inference and run at scale within a database engine. In addition, we introduce several optimization techniques that significantly speedup causal inference, both in the online and offline setting. We evaluate the quality and performance of our techniques by experiments of real datasets.
Introducing Distributed Dynamic Data-intensive (D3) Science: Understanding Applications and Infrastructure
Venue: arXiv cs.DC 2016
Year: 2016

A common feature across many science and engineering applications is the amount and diversity of data and computation that must be integrated to yield insights. Data sets are growing larger and becoming distributed; and their location, availability and properties are often time-dependent. Collectively, these characteristics give rise to dynamic distributed data-intensive applications. While "static" data applications have received significant attention, the characteristics, requirements, and software systems for the analysis of large volumes of dynamic, distributed data, and data-intensive applications have received relatively less attention. This paper surveys several representative dynamic distributed data-intensive application scenarios, provides a common conceptual framework to understand them, and examines the infrastructure used in support of applications.
Dynamic Proximity-aware Resource Allocation in Vehicle-to-Vehicle (V2V) Communications
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, a novel proximity and load-aware resource allocation for vehicle-to-vehicle (V2V) communication is proposed. The proposed approach exploits the spatio-temporal traffic patterns, in terms of load and vehicles' physical proximity, to minimize the total network cost which captures the tradeoffs between load (i.e., service delay) and successful transmissions while satisfying vehicles's quality-of-service (QoS) requirements. To solve the optimization problem under slowly varying channel information, it is decoupled the problem into two interrelated subproblems. First, a dynamic clustering mechanism is proposed to group vehicles in zones based on their traffic patterns and proximity information. Second, a matching game is proposed to allocate resources for each V2V pair within each zone. The problem is cast as many-to-one matching game in which V2V pairs and resource blocks (RBs) rank one another in order to minimize their service delay. The proposed game is shown to belong to the class of matching games with externalities. To solve this game, a distributed algorithm is proposed using which V2V pairs and RBs interact to reach a stable matching. Simulation results for a Manhattan model shown that the proposed scheme yields a higher percentage of V2V pairs satisfying QoS as well as significant gain in terms of the signal-to-interference-plus-noise ratio (SINR) as compared to a state-of-art resource allocation baseline.
Lie-X: Depth Image Based Articulated Object Pose Estimation, Tracking, and Action Recognition on Lie Groups
Venue: arXiv cs.CV 2016
Year: 2016

Pose estimation, tracking, and action recognition of articulated objects from depth images are important and challenging problems, which are normally considered separately. In this paper, a unified paradigm based on Lie group theory is proposed, which enables us to collectively address these related problems. Our approach is also applicable to a wide range of articulated objects. Empirically it is evaluated on lab animals including mouse and fish, as well as on human hand. On these applications, it is shown to deliver competitive results compared to the state-of-the-arts, and non-trivial baselines including convolutional neural networks and regression forest methods.
A Unified Gender-Aware Age Estimation
Venue: arXiv cs.CV 2016
Year: 2016

Human age estimation has attracted increasing researches due to its wide applicability in such as security monitoring and advertisement recommendation. Although a variety of methods have been proposed, most of them focus only on the age-specific facial appearance. However, biological researches have shown that not only gender but also the aging difference between the male and the female inevitably affect the age estimation. To our knowledge, so far there have been two methods that have concerned the gender factor. The first is a sequential method which first classifies the gender and then performs age estimation respectively for classified male and female. Although it promotes age estimation performance because of its consideration on the gender semantic difference, an accumulation risk of estimation errors is unavoidable. To overcome drawbacks of the sequential strategy, the second is to regress the age appended with the gender by concatenating their labels as two dimensional output using Partial Least Squares (PLS). Although leading to promotion of age estimation performance, such a concatenation not only likely confuses the semantics between the gender and age, but also ignores the aging discrepancy between the male and the female. In order to overcome their shortcomings, in this paper we propose a unified framework to perform gender-aware age estimation. The proposed method considers and utilizes not only the semantic relationship between the gender and the age, but also the aging discrepancy between the male and the female. Finally, experimental results demonstrate not only the superiority of our method in performance, but also its good interpretability in revealing the aging discrepancy.
Instrumenting an SMT Solver to Solve Hybrid Network Reachability Problems
Venue: arXiv cs.AI 2016
Year: 2016

PDDL+ planning has its semantics rooted in hybrid automata (HA) and recent work has shown that it can be modeled as a network of HAs. Addressing the complexity of nonlinear PDDL+ planning as HAs requires both space and time efficient reasoning. Unfortunately, existing solvers either do not address nonlinear dynamics or do not natively support networks of automata. We present a new algorithm, called HNSolve, which guides the variable selection of the dReal Satisfiability Modulo Theories (SMT) solver while reasoning about network encodings of nonlinear PDDL+ planning as HAs. HNSolve tightly integrates with dReal by solving a discrete abstraction of the HA network. HNSolve finds composite runs on the HA network that ignore continuous variables, but respect mode jumps and synchronization labels. HNSolve admissibly detects dead-ends in the discrete abstraction, and posts conflict clauses that prune the SMT solver's search. We evaluate the benefits of our HNSolve algorithm on PDDL+ benchmark problems and demonstrate its performance with respect to prior work.
Crafting a multi-task CNN for viewpoint estimation
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional Neural Networks (CNNs) were recently shown to provide state-of-the-art results for object category viewpoint estimation. However different ways of formulating this problem have been proposed and the competing approaches have been explored with very different design choices. This paper presents a comparison of these approaches in a unified setting as well as a detailed analysis of the key factors that impact performance. Followingly, we present a new joint training method with the detection task and demonstrate its benefit. We also highlight the superiority of classification approaches over regression approaches, quantify the benefits of deeper architectures and extended training data, and demonstrate that synthetic data is beneficial even when using ImageNet training data. By combining all these elements, we demonstrate an improvement of approximately 5% mAVP over previous state-of-the-art results on the Pascal3D+ dataset. In particular for their most challenging 24 view classification task we improve the results from 31.1% to 36.1% mAVP.
A Survey of Multi-Objective Optimization in Wireless Sensor Networks: Metrics, Algorithms and Open Problems
Venue: arXiv cs.NI 2016
Year: 2016

Wireless sensor networks (WSNs) have attracted substantial research interest, especially in the context of performing monitoring and surveillance tasks. However, it is challenging to strike compelling trade-offs amongst the various conflicting optimization criteria, such as the network's energy dissipation, packet-loss rate, coverage and lifetime. This paper provides a tutorial and survey of recent research and development efforts addressing this issue by using the technique of multi-objective optimization (MOO). First, we provide an overview of the main optimization objectives used in WSNs. Then, we elaborate on various prevalent approaches conceived for MOO, such as the family of mathematical programming based scalarization methods, the family of heuristics/metaheuristics based optimization algorithms, and a variety of other advanced optimization techniques. Furthermore, we summarize a range of recent studies of MOO in the context of WSNs, which are intended to provide useful guidelines for researchers to understand the referenced literature. Finally, we discuss a range of open problems to be tackled by future research.
Left dihedral codes over Galois rings ${\rm GR}(p^2,m)$
Venue: arXiv cs.IT 2016
Year: 2016

Let $D_{2n}=\langle x,y\mid x^n=1, y^2=1, yxy=x^{-1}\rangle$ be a dihedral group, and $R={\rm GR}(p^2,m)$ be a Galois ring of characteristic $p^2$ and cardinality $p^{2m}$ where $p$ is a prime. Left ideals of the group ring $R[D_{2n}]$ are called left dihedral codes over $R$ of length $2n$, and abbreviated as left $D_{2n}$-codes over $R$. Let ${\rm gcd}(n,p)=1$ in this paper. Then any left $D_{2n}$-code over $R$ is uniquely decomposed into a direct sum of concatenated codes with inner codes ${\cal A}_i$ and outer codes $C_i$, where ${\cal A}_i$ is a cyclic code over $R$ of length $n$ and $C_i$ is a skew cyclic code of length $2$ over an extension Galois ring or principal ideal ring of $R$, and a generator matrix and basic parameters for each outer code $C_i$ is given. Moreover, a formula to count the number of these codes is obtained, the dual code for each left $D_{2n}$-code is determined and all self-dual left $D_{2n}$-codes and self-orthogonal left $D_{2n}$-codes over $R$ are presented, respectively.
Relation-Changing Logics as Fragments of Hybrid Logics
Venue: arXiv cs.LO 2016
Year: 2016

Relation-changing modal logics are extensions of the basic modal logic that allow changes to the accessibility relation of a model during the evaluation of a formula. In particular, they are equipped with dynamic modalities that are able to delete, add, and swap edges in the model, both locally and globally. We provide translations from these logics to hybrid logic along with an implementation. In general, these logics are undecidable, but we use our translations to identify decidable fragments. We also compare the expressive power of relation-changing modal logics with hybrid logics.
A Canonical Model Construction for Iteration-Free PDL with Intersection
Venue: arXiv cs.LO 2016
Year: 2016

We study the axiomatisability of the iteration-free fragment of Propositional Dynamic Logic with Intersection and Tests. The combination of program composition, intersection and tests makes its proof-theory rather difficult. We develop a normal form for formulae which minimises the interaction between these operators, as well as a refined canonical model construction. From these we derive an axiom system and a proof of its strong completeness.
Multi-Buffer Simulations for Trace Language Inclusion
Venue: arXiv cs.FL 2016
Year: 2016

We consider simulation games played between Spoiler and Duplicator on two Büchi automata in which the choices made by Spoiler can be buffered by Duplicator in several buffers before she executes them on her structure. We show that the simulation games are useful to approximate the inclusion of trace closures of languages accepted by finite-state automata, which is known to be undecidable. We study the decidability and complexity and show that the game with bounded buffers can be decided in polynomial time, whereas the game with one unbounded and one bounded buffer is highly undecidable. We also show some sufficient conditions on the automata for Duplicator to win the game (with unbounded buffers).
A joint-optimization NSAF algorithm based on the first-order Markov model
Venue: arXiv cs.SY 2016
Year: 2016

Recently, the normalized subband adaptive filter (NSAF) algorithm has attracted much attention for handling the colored input signals. Based on the first-order Markov model of the optimal tap-weight vector, this paper provides a convergence analysis of the standard NSAF. Following the analysis, both the step size and the regularization parameter in the NSAF are jointly optimized in such a way that minimizes the mean square deviation. The resulting joint-optimization step size and regularization parameter (JOSR-NSAF) algorithm achieves a good tradeoff between fast convergence rate and low steady-state error. Simulation results in the context of acoustic echo cancellation demonstrate good features of the proposed algorithm.
Joint Gender Classification and Age Estimation by Nearly Orthogonalizing Their Semantic Spaces
Venue: arXiv cs.CV 2016
Year: 2016

In human face-based biometrics, gender classification and age estimation are two typical learning tasks. Although a variety of approaches have been proposed to handle them, just a few of them are solved jointly, even so, these joint methods do not yet specifically concern the semantic difference between human gender and age, which is intuitively helpful for joint learning, consequently leaving us a room of further improving the performance. To this end, in this work we firstly propose a general learning framework for jointly estimating human gender and age by specially attempting to formulate such semantic relationships as a form of near-orthogonality regularization and then incorporate it into the objective of the joint learning framework. In order to evaluate the effectiveness of the proposed framework, we exemplify it by respectively taking the widely used binary-class SVM for gender classification, and two threshold-based ordinal regression methods (i.e., the discriminant learning for ordinal regression and support vector ordinal regression) for age estimation, and crucially coupling both through the proposed semantic formulation. Moreover, we develop its kernelized nonlinear counterpart by deriving a representer theorem for the joint learning strategy. Finally, through extensive experiments on three aging datasets FG-NET, Morph Album I and Morph Album II, we demonstrate the effectiveness and superiority of the proposed joint learning strategy.
Every Schnyder Drawing is a Greedy Embedding
Venue: arXiv cs.CG 2016
Year: 2016

Geographic routing is a routing paradigm, which uses geographic coordinates of network nodes to determine routes. Greedy routing, the simplest form of geographic routing forwards a packet to the closest neighbor towards the destination. A greedy embedding is a embedding of a graph on a geometric space such that greedy routing always guarantees delivery. A Schnyder drawing is a classical way to draw a planar graph. In this manuscript, we show that every Schnyder drawing is a greedy embedding, based on a generalized definition of greedy routing.
Liveness of Parameterized Timed Networks
Venue: arXiv cs.LO 2016
Year: 2016

We consider the model checking problem of infinite state systems given in the form of parameterized discrete timed networks with multiple clocks. We show that this problem is decidable with respect to specifications given by B- or S-automata. Such specifications are very expressive (they strictly subsume omega-regular specifications), and easily express complex liveness and safety properties. Our results are obtained by modeling the passage of time using symmetric broadcast, and by solving the model checking problem of parameterized systems of un-timed processes communicating using k-wise rendezvous and symmetric broadcast. Our decidability proof makes use of automata theory, rational linear programming, and geometric reasoning for solving certain reachability questions in vector addition systems; we believe these proof techniques will be useful in solving related problems.
Modemless Multiple Access Communications over Powerlines for DC Microgrid Control
Venue: arXiv cs.IT 2016
Year: 2016

We present a communication solution tailored specifically for DC microgrids (MGs) that exploits: (i) the communication potential residing in power electronic converters interfacing distributed generators to powerlines and (ii) the multiple access nature of the communication channel presented by powerlines. The communication is achieved by modulating the parameters of the primary control loop implemented by the converters, fostering execution of the upper layer control applications. We present the proposed solution in the context of the distributed optimal economic dispatch, where the generators periodically transmit information about their local generation capacity, and, simultaneously, using the properties of the multiple access channel, detect the aggregate generation capacity of the remote peers, with an aim of distributed computation of the optimal dispatch policy. We evaluate the potential of the proposed solution and illustrate its inherent trade-offs.