OpenRaiser/Intern-Atlas huggingface dataset:
Spherical Conformal Parameterization of Genus-0 Point Clouds for Meshing
Venue: arXiv cs.CG 2016
Year: 2016

Point cloud is the most fundamental representation of 3D geometric objects. Analyzing and processing point cloud surfaces is important in computer graphics and computer vision. However, most of the existing algorithms for surface analysis require connectivity information. Therefore, it is desirable to develop a mesh structure on point clouds. This task can be simplified with the aid of a parameterization. In particular, conformal parameterizations are advantageous in preserving the geometric information of the point cloud data. In this paper, we extend a state-of-the-art spherical conformal parameterization algorithm for genus-0 closed meshes to the case of point clouds, using an improved approximation of the Laplace-Beltrami operator on data points. Then, we propose an iterative scheme called the North-South reiteration for achieving a spherical conformal parameterization. A balancing scheme is introduced to enhance the distribution of the spherical parameterization. High quality triangulations and quadrangulations can then be built on the point clouds with the aid of the parameterizations. Also, the meshes generated are guaranteed to be genus-0 closed meshes. Moreover, using our proposed spherical conformal parameterization, multilevel representations of point clouds can be easily constructed. Experimental results demonstrate the effectiveness of our proposed framework.
Word Representations, Tree Models and Syntactic Functions
Venue: arXiv cs.CL 2016
Year: 2016

Word representations induced from models with discrete latent variables (e.g.\ HMMs) have been shown to be beneficial in many NLP applications. In this work, we exploit labeled syntactic dependency trees and formalize the induction problem as unsupervised learning of tree-structured hidden Markov models. Syntactic functions are used as additional observed variables in the model, influencing both transition and emission components. Such syntactic information can potentially lead to capturing more fine-grain and functional distinctions between words, which, in turn, may be desirable in many NLP applications. We evaluate the word representations on two tasks -- named entity recognition and semantic frame identification. We observe improvements from exploiting syntactic function information in both cases, and the results rivaling those of state-of-the-art representation learning methods. Additionally, we revisit the relationship between sequential and unlabeled-tree models and find that the advantage of the latter is not self-evident.
Distributed Binary Detection over Fading Channels: Cooperative and Parallel Architectures
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers the problem of binary distributed detection of a known signal in correlated Gaussian sensing noise in a wireless sensor network, where the sensors are restricted to use likelihood ratio test (LRT), and communicate with the fusion center (FC) over bandwidth-constrained channels that are subject to fading and noise. To mitigate the deteriorating effect of fading encountered in the conventional parallel fusion architecture, in which the sensors directly communicate with the FC, we propose new fusion architectures that enhance the detection performance, via harvesting cooperative gain (so-called decision diversity gain). In particular, we propose: (i) cooperative fusion architecture with Alamouti's space-time coding (STC) scheme at sensors, (ii) cooperative fusion architecture with signal fusion at sensors, and (iii) parallel fusion architecture with local threshold changing at sensors. For these schemes, we derive the LRT and majority fusion rules at the FC, and provide upper bounds on the average error probabilities for homogeneous sensors, subject to uncorrelated Gaussian sensing noise, in terms of signal-to-noise ratio (SNR) of communication and sensing channels. Our simulation results indicate that, when the FC employs the LRT rule, unless for low communication SNR and moderate/high sensing SNR, performance improvement is feasible with the new fusion architectures. When the FC utilizes the majority rule, such improvement is possible, unless for high sensing SNR.
In-Band $α$-Duplex Scheme for Cellular Networks: A Stochastic Geometry Approach
Venue: arXiv cs.IT 2016
Year: 2016

In-band full-duplex (FD) communications have been optimistically promoted to improve the spectrum utilization and efficiency. However, the penetration of FD communications to the cellular networks domain is challenging due to the imposed uplink/downlink interference. This paper presents a tractable framework, based on stochastic geometry, to study FD communications in cellular networks. Particularly, we assess the FD communications effect on the network performance and quantify the associated gains. The study proves the vulnerability of the uplink to the downlink interference and shows that the improved FD rate gains harvested in the downlink (up to $97\%$) comes at the expense of a significant degradation in the uplink rate (up to $94\%$). Therefore, we propose a novel fine-grained duplexing scheme, denoted as $α$-duplex scheme, which allows a partial overlap between the uplink and the downlink frequency bands. We derive the required conditions to harvest rate gains from the $α$-duplex scheme and show its superiority to both the FD and half-duplex (HD) schemes. In particular, we show that the $α$-duplex scheme provides a simultaneous improvement of $28\%$ for the downlink rate and $56\%$ for the uplink rate. Finally, we show that the amount of the overlap can be optimized based on the network design objective.
Adaptive Control of Uncertain Pure-feedback Nonlinear Systems
Venue: arXiv cs.SY 2016
Year: 2016

A novel adaptive control approach is proposed to solve the globally asymptotic state stabilization problem for uncertain pure-feedback nonlinear systems which can be transformed into the pseudo-affine form. The pseudo-affine pure-feedback nonlinear system under consideration is with non-linearly parameterised uncertainties and possibly unknown control coefficients. Based on the parameter separation technique, a backstepping controller is designed by adopting the adaptive high gain idea. The rigorous stability analysis shows that the proposed controller could guarantee, for any initial system condition, boundedness of the closed-loop signals and globally asymptotic stabilization of the state. A numerical and a realistic examples are employed to demonstrate the effectiveness of the proposed control method.
Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization
Venue: arXiv cs.NA 2016
Year: 2016

Given a symmetric nonnegative matrix $A$, symmetric nonnegative matrix factorization (symNMF) is the problem of finding a nonnegative matrix $H$, usually with much fewer columns than $A$, such that $A \approx HH^T$. SymNMF can be used for data analysis and in particular for various clustering tasks. In this paper, we propose simple and very efficient coordinate descent schemes to solve this problem, and that can handle large and sparse input matrices. The effectiveness of our methods is illustrated on synthetic and real-world data sets, and we show that they perform favorably compared to recent state-of-the-art methods.
On repeated zero-sum games with incomplete information and asymptotically bounded values
Venue: arXiv cs.GT 2016
Year: 2016

We consider repeated zero-sum games with incomplete information on the side of Player 2 with the total payoff given by the non-normalized sum of stage gains. In the classical examples the value $V_N$ of such an $N$-stage game is of the order of $N$ or $\sqrt{N}$ as $N\to \infty$. Our aim is to find what is causing another type of asymptotic behavior of the value $V_N$ observed for the discrete version of the financial market model introduced by De Meyer and Saley. For this game Domansky and independently De Meyer with Marino found that $V_N$ remains bounded as $N\to\infty$ and converges to the limit value. This game is almost-fair, i.e., if Player 1 forgets his private information the value becomes zero. We describe a class of almost-fair games having bounded values in terms of an easy-checkable property of the auxiliary non-revealing game. We call this property the piecewise property, and it says that there exists an optimal strategy of Player 2 that is piecewise-constant as a function of a prior distribution $p$. Discrete market models have the piecewise property. We show that for non-piecewise almost-fair games with an additional non-degeneracy condition $V_N$ is of the order of $\sqrt{N}$.
The MIMO Wiretap Channel Decomposed
Venue: arXiv cs.IT 2016
Year: 2016

The problem of sending a secret message over the Gaussian multiple-input multiple-output (MIMO) wiretap channel is studied. While the capacity of this channel is known, it is not clear how to construct optimal coding schemes that achieve this capacity. In this work, we use linear operations along with successive interference cancellation to attain effective parallel single-antenna wiretap channels. By using independent scalar Gaussian wiretap codebooks over the resulting parallel channels, the capacity of the MIMO wiretap channel is achieved. The derivation of the schemes is based upon joint triangularization of the channel matrices. We find that the same technique can be used to re-derive capacity expressions for the MIMO wiretap channel in a way that is simple and closely connected to a transmission scheme. This technique allows to extend the previously proven strong security for scalar Gaussian channels to the MIMO case. We further consider the problem of transmitting confidential messages over a two-user broadcast MIMO channel. For that problem, we find that derivation of both the capacity and a transmission scheme is a direct corollary of the proposed analysis for the MIMO wiretap channel.
Stable Matching with Evolving Preferences
Venue: arXiv cs.GT 2016
Year: 2016

We consider the problem of stable matching with dynamic preference lists. At each time step, the preference list of some player may change by swapping random adjacent members. The goal of a central agency (algorithm) is to maintain an approximately stable matching (in terms of number of blocking pairs) at all times. The changes in the preference lists are not reported to the algorithm, but must instead be probed explicitly by the algorithm. We design an algorithm that in expectation and with high probability maintains a matching that has at most $O((log (n))^2)$ blocking pairs.
Lipschitz Continuity and Approximate Equilibria
Venue: arXiv cs.GT 2016
Year: 2016

In this paper, we study games with continuous action spaces and non-linear payoff functions. Our key insight is that Lipschitz continuity of the payoff function allows us to provide algorithms for finding approximate equilibria in these games. We begin by studying Lipschitz games, which encompass, for example, all concave games with Lipschitz continuous payoff functions. We provide an efficient algorithm for computing approximate equilibria in these games. Then we turn our attention to penalty games, which encompass biased games and games in which players take risk into account. Here we show that if the penalty function is Lipschitz continuous, then we can provide a quasi-polynomial time approximation scheme. Finally, we study distance biased games, where we present simple strongly polynomial time algorithms for finding best responses in $L_1$, $L_2^2$, and $L_\infty$ biased games, and then use these algorithms to provide strongly polynomial algorithms that find $2/3$, $5/7$, and $2/3$ approximations for these norms, respectively.
Dissecting GPU Memory Hierarchy through Microbenchmarking
Venue: arXiv cs.AR 2016
Year: 2016

Memory access efficiency is a key factor in fully utilizing the computational power of graphics processing units (GPUs). However, many details of the GPU memory hierarchy are not released by GPU vendors. In this paper, we propose a novel fine-grained microbenchmarking approach and apply it to three generations of NVIDIA GPUs, namely Fermi, Kepler and Maxwell, to expose the previously unknown characteristics of their memory hierarchies. Specifically, we investigate the structures of different GPU cache systems, such as the data cache, the texture cache and the translation look-aside buffer (TLB). We also investigate the throughput and access latency of GPU global memory and shared memory. Our microbenchmark results offer a better understanding of the mysterious GPU memory hierarchy, which will facilitate the software optimization and modelling of GPU architectures. To the best of our knowledge, this is the first study to reveal the cache properties of Kepler and Maxwell GPUs, and the superiority of Maxwell in shared memory performance under bank conflict.
Characterizing and Adapting the Consistency-Latency Tradeoff in Distributed Key-value Stores
Venue: arXiv cs.DC 2016
Year: 2016

The CAP theorem is a fundamental result that applies to distributed storage systems. In this paper, we first present and prove two CAP-like impossibility theorems. To state these theorems, we present probabilistic models to characterize the three important elements of the CAP theorem: consistency (C), availability or latency (A), and partition tolerance (P). The theorems show the un-achievable envelope, i.e., which combinations of the parameters of the three models make them impossible to achieve together. Next, we present the design of a class of systems called PCAP that perform close to the envelope described by our theorems. In addition, these systems allow applications running on a single data-center to specify either a latency SLA or a consistency SLA. The PCAP systems automatically adapt, in real-time and under changing network conditions, to meet the SLA while optimizing the other C/A metric. We incorporate PCAP into two popular key-value stores -- Apache Cassandra and Riak. Our experiments with these two deployments, under realistic workloads, reveal that the PCAP system satisfactorily meets SLAs, and performs close to the achievable envelope. We also extend PCAP from a single data-center to multiple geo-distributed data-centers.
STC: A Simple to Complex Framework for Weakly-supervised Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Recently, significant improvement has been made on semantic object segmentation due to the development of deep convolutional neural networks (DCNNs). Training such a DCNN usually relies on a large number of images with pixel-level segmentation masks, and annotating these images is very costly in terms of both finance and human effort. In this paper, we propose a simple to complex (STC) framework in which only image-level annotations are utilized to learn DCNNs for semantic segmentation. Specifically, we first train an initial segmentation network called Initial-DCNN with the saliency maps of simple images (i.e., those with a single category of major object(s) and clean background). These saliency maps can be automatically obtained by existing bottom-up salient object detection techniques, where no supervision information is needed. Then, a better network called Enhanced-DCNN is learned with supervision from the predicted segmentation masks of simple images based on the Initial-DCNN as well as the image-level annotations. Finally, more pixel-level segmentation masks of complex images (two or more categories of objects with cluttered background), which are inferred by using Enhanced-DCNN and image-level annotations, are utilized as the supervision information to learn the Powerful-DCNN for semantic segmentation. Our method utilizes $40$K simple images from Flickr.com and 10K complex images from PASCAL VOC for step-wisely boosting the segmentation network. Extensive experimental results on PASCAL VOC 2012 segmentation benchmark well demonstrate the superiority of the proposed STC framework compared with other state-of-the-arts.
A reliable order-statistics-based approximate nearest neighbor search algorithm
Venue: arXiv cs.CV 2016
Year: 2016

We propose a new algorithm for fast approximate nearest neighbor search based on the properties of ordered vectors. Data vectors are classified based on the index and sign of their largest components, thereby partitioning the space in a number of cones centered in the origin. The query is itself classified, and the search starts from the selected cone and proceeds to neighboring ones. Overall, the proposed algorithm corresponds to locality sensitive hashing in the space of directions, with hashing based on the order of components. Thanks to the statistical features emerging through ordering, it deals very well with the challenging case of unstructured data, and is a valuable building block for more complex techniques dealing with structured data. Experiments on both simulated and real-world data prove the proposed algorithm to provide a state-of-the-art performance.
Bio-Inspired Human Action Recognition using Hybrid Max-Product Neuro-Fuzzy Classifier and Quantum-Behaved PSO
Venue: arXiv cs.AI 2016
Year: 2016

Studies on computational neuroscience through functional magnetic resonance imaging (fMRI) and following biological inspired system stated that human action recognition in the brain of mammalian leads two distinct pathways in the model, which are specialized for analysis of motion (optic flow) and form information. Principally, we have defined a novel and robust form features applying active basis model as form extractor in form pathway in the biological inspired model. An unbalanced synergetic neural net-work classifies shapes and structures of human objects along with tuning its attention parameter by quantum particle swarm optimization (QPSO) via initiation of Centroidal Voronoi Tessellations. These tools utilized and justified as strong tools for following biological system model in form pathway. But the final decision has done by combination of ultimate outcomes of both pathways via fuzzy inference which increases novality of proposed model. Combination of these two brain pathways is done by considering each feature sets in Gaussian membership functions with fuzzy product inference method. Two configurations have been proposed for form pathway: applying multi-prototype human action templates using two time synergetic neural network for obtaining uniform template regarding each actions, and second scenario that it uses abstracting human action in four key-frames. Experimental results showed promising accuracy performance on different datasets (KTH and Weizmann).
Sparse Multinomial Logistic Regression via Approximate Message Passing
Venue: arXiv cs.IT 2016
Year: 2016

For the problem of multi-class linear classification and feature selection, we propose approximate message passing approaches to sparse multinomial logistic regression (MLR). First, we propose two algorithms based on the Hybrid Generalized Approximate Message Passing (HyGAMP) framework: one finds the maximum a posteriori (MAP) linear classifier and the other finds an approximation of the test-error-rate minimizing linear classifier. Then we design computationally simplified variants of these two algorithms. Next, we detail methods to tune the hyperparameters of their assumed statistical models using Stein's unbiased risk estimate (SURE) and expectation-maximization (EM), respectively. Finally, using both synthetic and real-world datasets, we demonstrate improved error-rate and runtime performance relative to existing state-of-the-art approaches to sparse MLR.
Rehearsal: A Configuration Verification Tool for Puppet
Venue: arXiv cs.PL 2016
Year: 2016

Large-scale data centers and cloud computing have turned system configuration into a challenging problem. Several widely-publicized outages have been blamed not on software bugs, but on configuration bugs. To cope, thousands of organizations use system configuration languages to manage their computing infrastructure. Of these, Puppet is the most widely used with thousands of paying customers and many more open-source users. The heart of Puppet is a domain-specific language that describes the state of a system. Puppet already performs some basic static checks, but they only prevent a narrow range of errors. Furthermore, testing is ineffective because many errors are only triggered under specific machine states that are difficult to predict and reproduce. With several examples, we show that a key problem with Puppet is that configurations can be non-deterministic. This paper presents Rehearsal, a verification tool for Puppet configurations. Rehearsal implements a sound, complete, and scalable determinacy analysis for Puppet. To develop it, we (1) present a formal semantics for Puppet, (2) use several analyses to shrink our models to a tractable size, and (3) frame determinism-checking as decidable formulas for an SMT solver. Rehearsal then leverages the determinacy analysis to check other important properties, such as idempotency. Finally, we apply Rehearsal to several real-world Puppet configurations.
DeXpression: Deep Convolutional Neural Network for Expression Recognition
Venue: arXiv cs.CV 2016
Year: 2016

We propose a convolutional neural network (CNN) architecture for facial expression recognition. The proposed architecture is independent of any hand-crafted feature extraction and performs better than the earlier proposed convolutional neural network based approaches. We visualize the automatically extracted features which have been learned by the network in order to provide a better understanding. The standard datasets, i.e. Extended Cohn-Kanade (CKP) and MMI Facial Expression Databse are used for the quantitative evaluation. On the CKP set the current state of the art approach, using CNNs, achieves an accuracy of 99.2%. For the MMI dataset, currently the best accuracy for emotion recognition is 93.33%. The proposed architecture achieves 99.6% for CKP and 98.63% for MMI, therefore performing better than the state of the art using CNNs. Automatic facial expression recognition has a broad spectrum of applications such as human-computer interaction and safety systems. This is due to the fact that non-verbal cues are important forms of communication and play a pivotal role in interpersonal communication. The performance of the proposed architecture endorses the efficacy and reliable usage of the proposed work for real world applications.
Stable reconstructions for the analysis formulation of $\ell^p$-minimization using redundant systems
Venue: arXiv cs.IT 2016
Year: 2016

In compressed sensing sparse solutions are usually obtained by solving an $\ell^1$-minimization problem. Furthermore, the sparsity of the signal does need not be directly given. In fact, it is sufficient to have a signal that is sparse after an application of a suitable transform. In this paper we consider the stability of solutions obtained from $\ell^p$-minimization for arbitrary $0<p \leq1$. Further we suppose that the signals are sparse with respect to general redundant transforms associated to not necessarily tight frames. Since we are considering general frames the role of the dual frame has to be additionally discussed. For our stability analysis we will introduce a new concept of so-called \emph{frames with identifiable duals}. Further, we numerically highlight a gap between the theory and the applications of compressed sensing for some specific redundant transforms.