OpenRaiser/Intern-Atlas huggingface dataset:
On the Simultaneous Preservation of Privacy and Community Structure in Anonymized Networks
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of performing community detection on a network, while maintaining privacy, assuming that the adversary has access to an auxiliary correlated network. We ask the question "Does there exist a regime where the network cannot be deanonymized perfectly, yet the community structure could be learned?." To answer this question, we derive information theoretic converses for the perfect deanonymization problem using the Stochastic Block Model and edge sub-sampling. We also provide an almost tight achievability result for perfect deanonymization. We also evaluate the performance of percolation based deanonymization algorithm on Stochastic Block Model data-sets that satisfy the conditions of our converse. Although our converse applies to exact deanonymization, the algorithm fails drastically when the conditions of the converse are met. Additionally, we study the effect of edge sub-sampling on the community structure of a real world dataset. Results show that the dataset falls under the purview of the idea of this paper. There results suggest that it may be possible to prove stronger partial deanonymizability converses, which would enable better privacy guarantees.
An Empirical Study of Dimensional Reduction Techniques for Facial Action Units Detection
Venue: arXiv cs.CV 2016
Year: 2016

Biologically inspired features, such as Gabor filters, result in very high dimensional measurement. Does reducing the dimensionality of the feature space afford advantages beyond computational efficiency? Do some approaches to dimensionality reduction (DR) yield improved action unit detection? To answer these questions, we compared DR approaches in two relatively large databases of spontaneous facial behavior (45 participants in total with over 2 minutes of FACS-coded video per participant). Facial features were tracked and aligned using active appearance models (AAM). SIFT and Gabor features were extracted from local facial regions. We compared linear (PCA and KPCA), manifold (LPP and LLE), supervised (LDA and KDA) and hybrid approaches (LSDA) to DR with respect to AU detection. For further comparison, a no-DR control condition was included as well. Linear support vector machine classifiers with independent train and test sets were used for AU detection. AU detection was quantified using area under the ROC curve and F1. Baseline results for PCA with Gabor features were comparable with previous research. With some notable exceptions, DR improved AU detection relative to no-DR. Locality embedding approaches proved vulnerable to \emph{out-of-sample} problems. Gradient-based SIFT lead to better AU detection than the filter-based Gabor features. For area under the curve, few differences were found between linear and other DR approaches. For F1, results were mixed. For both metrics, the pattern of results varied among action units. These findings suggest that action unit detection may be optimized by using specific DR for specific action units. PCA and LDA were the most efficient approaches; KDA was the least efficient.
Performance Analysis of ARQ-based RF-FSO Links
Venue: arXiv cs.IT 2016
Year: 2016

In this letter, we study the performance of hybrid radio-frequency (RF) and free-space optical (FSO) links using automatic repeat request (ARQ). We derive closed-form expressions for the message decoding probabilities, throughput, and outage probability with different relative coherence times of the RF and FSO links. We also evaluate the effect of adaptive power allocation between the ARQ retransmissions on the system performance. The results show that joint implementation of the RF and FSO links leads to substantial performance improvement, compared to the cases with only the RF or the FSO link.
Towards the Design of Effective Freehand Gestural Interaction for Interactive TV
Venue: arXiv cs.HC 2016
Year: 2016

As interactive devices become pervasive, people are beginning to looking for more advanced interaction with televisions in the living room. Interactive television has the potential to offer a very engaging experience. But most common user tasks are still challenging with such systems, such as menu selection or text input. And little work has been done on understanding and sup-porting the effective design of freehand interaction with an TV in the living room. In this paper, we perform two studies investi-gating freehand gestural interaction with a consumer level sensor, which is suitable for TV scenarios. In the first study, we inves-tigate a range of design factors for tiled layout menu selection, including wearable feedback, push gesture depth, target size and position in motor space. The results show that tactile and audio feedback have no significant effect on performance and prefer-ence, and these results inform potential designs for high selection performance. In the second study, we investigate a common TV user task of text input using freehand gesture. We design and evaluate two virtual keyboard layouts and three freehand selec-tion methods. Results show that ease of use and error tolerance can be both achieved using a text entry method utilizing a dual circle layout and an expanding target selection technique. Finally, we propose design guidelines for effective, usable and com-fortable freehand gestural interaction for interactive TV based on the findings.
The Random Frequency Diverse Array: A New Antenna Structure for Uncoupled Direction-Range Indication in Active Sensing
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose a new type of array antenna, termed the Random Frequency Diverse Array (RFDA), for an uncoupled indication of target direction and range with low system complexity. In RFDA, each array element has a narrow bandwidth and a randomly assigned carrier frequency. The beampattern of the array is shown to be stochastic but thumbtack-like, and its stochastic characteristics, such as the mean, variance, and asymptotic distribution are derived analytically. Based on these two features, we propose two kinds of algorithms for signal processing. One is matched filtering, due to the beampattern's good characteristics. The other is compressive sensing, because the new approach can be regarded as a sparse and random sampling of target information in the spatial-frequency domain. Fundamental limits, such as the Cramér-Rao bound and the observing matrix's mutual coherence, are provided as performance guarantees of the new array structure. The features and performances of RFDA are verified with numerical results.
Distributed Fusion of Labeled Multi-Object Densities Via Label Spaces Matching
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we address the problem of the distributed multi-target tracking with labeled set filters in the framework of Generalized Covariance Intersection (GCI). Our analyses show that the label space mismatching (LS-DM) phenomenon, which means the same realization drawn from label spaces of different sensors does not have the same implication, is quite common in practical scenarios and may bring serious problems. Our contributions are two-fold. Firstly, we provide a principled mathematical definition of "label spaces matching (LS-DM)" based on information divergence, which is also referred to as LS-M criterion. Then, to handle the LS-DM, we propose a novel two-step distributed fusion algorithm, named as GCI fusion via label spaces matching (GCI-LSM). The first step is to match the label spaces from different sensors. To this end, we build a ranked assignment problem and design a cost function consistent with LS-M criterion to seek the optimal solution of matching correspondence between label spaces of different sensors. The second step is to perform the GCI fusion on the matched label space. We also derive the GCI fusion with generic labeled multi-object (LMO) densities based on LS-M, which is the foundation of labeled distributed fusion algorithms. Simulation results for Gaussian mixture implementation highlight the performance of the proposed GCI-LSM algorithm in two different tracking scenarios.
Hierarchical Gaussian Mixture Model with Objects Attached to Terminal and Non-terminal Dendrogram Nodes
Venue: arXiv cs.LG 2016
Year: 2016

A hierarchical clustering algorithm based on Gaussian mixture model is presented. The key difference to regular hierarchical mixture models is the ability to store objects in both terminal and nonterminal nodes. Upper levels of the hierarchy contain sparsely distributed objects, while lower levels contain densely represented ones. As it was shown by experiments, this ability helps in noise detection (modelling). Furthermore, compared to regular hierarchical mixture model, the presented method generates more compact dendrograms with higher quality measured by adopted F-measure.
Potholes Ahead: Impact of Transient Link Blockage on Beam Steering in Practical mm-Wave Systems
Venue: arXiv cs.NI 2016
Year: 2016

The practical realization of beam steering mechanisms in millimeter wave communications has a large impact on performance. The key challenge is to find a pragmatic trade-off between throughput performance and the overhead of periodic beam sweeping required to improve link quality in case of transient link blockage. This is particularly critical in commercial off-the-shelf devices, which require simple yet efficient solutions. First, we analyze the operation of such a commercial device to understand the impact of link blockage in practice. To this end, we measure TCP throughput for different traffic loads while blocking the link at regular intervals. Second, we derive a Markov model based on our practical insights to compute throughput for the case of transient blockage. We use this model to evaluate the trade-off between throughput and periodic beam sweeping. Finally, we validate our results using throughput traces collected using the aforementioned commercial device. Both our model and our practical measurements show that transient blockage causes significant signal fluctuation due to suboptimal beam realignment. In particular, fluctuations increase with traffic load, limiting the achievable throughput. We show that choosing lower traffic loads allows us to reduce fluctuations by 41% while achieving the same net throughput than with higher traffic loads.
Sparse Activity and Sparse Connectivity in Supervised Learning
Venue: arXiv cs.LG 2016
Year: 2016

Sparseness is a useful regularizer for learning in a wide range of applications, in particular in neural networks. This paper proposes a model targeted at classification tasks, where sparse activity and sparse connectivity are used to enhance classification capabilities. The tool for achieving this is a sparseness-enforcing projection operator which finds the closest vector with a pre-defined sparseness for any given vector. In the theoretical part of this paper, a comprehensive theory for such a projection is developed. In conclusion, it is shown that the projection is differentiable almost everywhere and can thus be implemented as a smooth neuronal transfer function. The entire model can hence be tuned end-to-end using gradient-based methods. Experiments on the MNIST database of handwritten digits show that classification performance can be boosted by sparse activity or sparse connectivity. With a combination of both, performance can be significantly better compared to classical non-sparse approaches.
Probabilistic Programming for Malware Analysis
Venue: arXiv cs.CR 2016
Year: 2016

Constructing lineages of malware is an important cyber-defense task. Performing this task is difficult, however, due to the amount of malware data and obfuscation techniques by the authors. In this work, we formulate the lineage task as a probabilistic model, and use a novel probabilistic programming solution to jointly infer the lineage and creation times of families of malware.
Mutual Information in Rank-One Matrix Estimation
Venue: arXiv cs.IT 2016
Year: 2016

We consider the estimation of a n-dimensional vector x from the knowledge of noisy and possibility non-linear element-wise measurements of xxT , a very generic problem that contains, e.g. stochastic 2-block model, submatrix localization or the spike perturbation of random matrices. We use an interpolation method proposed by Guerra and later refined by Korada and Macris. We prove that the Bethe mutual information (related to the Bethe free energy and conjectured to be exact by Lesieur et al. on the basis of the non-rigorous cavity method) always yields an upper bound to the exact mutual information. We also provide a lower bound using a similar technique. For concreteness, we illustrate our findings on the sparse PCA problem, and observe that (a) our bounds match for a large region of parameters and (b) that it exists a phase transition in a region where the spectum remains uninformative. While we present only the case of rank-one symmetric matrix estimation, our proof technique is readily extendable to low-rank symmetric matrix or low-rank symmetric tensor estimation
Longitudinal Analysis of Discussion Topics in an Online Breast Cancer Community using Convolutional Neural Networks
Venue: arXiv cs.CL 2016
Year: 2016

Identifying topics of discussions in online health communities (OHC) is critical to various applications, but can be difficult because topics of OHC content are usually heterogeneous and domain-dependent. In this paper, we provide a multi-class schema, an annotated dataset, and supervised classifiers based on convolutional neural network (CNN) and other models for the task of classifying discussion topics. We apply the CNN classifier to the most popular breast cancer online community, and carry out a longitudinal analysis to show topic distributions and topic changes throughout members' participation. Our experimental results suggest that CNN outperforms other classifiers in the task of topic classification, and that certain trajectories can be detected with respect to topic changes.
Generating Visual Explanations
Venue: arXiv cs.CV 2016
Year: 2016

Clearly explaining a rationale for a classification decision to an end-user can be as important as the decision itself. Existing approaches for deep visual recognition are generally opaque and do not output any justification text; contemporary vision-language models can describe image content but fail to take into account class-discriminative image aspects which justify visual predictions. We propose a new model that focuses on the discriminating properties of the visible object, jointly predicts a class label, and explains why the predicted label is appropriate for the image. We propose a novel loss function based on sampling and reinforcement learning that learns to generate sentences that realize a global sentence property, such as class specificity. Our results on a fine-grained bird species classification dataset show that our model is able to generate explanations which are not only consistent with an image but also more discriminative than descriptions produced by existing captioning methods.
Prepositional Attachment Disambiguation Using Bilingual Parsing and Alignments
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we attempt to solve the problem of Prepositional Phrase (PP) attachments in English. The motivation for the work comes from NLP applications like Machine Translation, for which, getting the correct attachment of prepositions is very crucial. The idea is to correct the PP-attachments for a sentence with the help of alignments from parallel data in another language. The novelty of our work lies in the formulation of the problem into a dual decomposition based algorithm that enforces agreement between the parse trees from two languages as a constraint. Experiments were performed on the English-Hindi language pair and the performance improved by 10% over the baseline, where the baseline is the attachment predicted by the MSTParser model trained for English.
Classification of Alzheimer's Disease using fMRI Data and Deep Learning Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Over the past decade, machine learning techniques especially predictive modeling and pattern recognition in biomedical sciences from drug delivery system to medical imaging has become one of the important methods which are assisting researchers to have deeper understanding of entire issue and to solve complex medical problems. Deep learning is power learning machine learning algorithm in classification while extracting high-level features. In this paper, we used convolutional neural network to classify Alzheimer's brain from normal healthy brain. The importance of classifying this kind of medical data is to potentially develop a predict model or system in order to recognize the type disease from normal subjects or to estimate the stage of the disease. Classification of clinical data such as Alzheimer's disease has been always challenging and most problematic part has been always selecting the most discriminative features. Using Convolutional Neural Network (CNN) and the famous architecture LeNet-5, we successfully classified functional MRI data of Alzheimer's subjects from normal controls where the accuracy of test data on trained data reached 96.85%. This experiment suggests us the shift and scale invariant features extracted by CNN followed by deep learning classification is most powerful method to distinguish clinical data from healthy data in fMRI. This approach also enables us to expand our methodology to predict more complicated systems.
What a Nerd! Beating Students and Vector Cosine in the ESL and TOEFL Datasets
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we claim that Vector Cosine, which is generally considered one of the most efficient unsupervised measures for identifying word similarity in Vector Space Models, can be outperformed by a completely unsupervised measure that evaluates the extent of the intersection among the most associated contexts of two target words, weighting such intersection according to the rank of the shared contexts in the dependency ranked lists. This claim comes from the hypothesis that similar words do not simply occur in similar contexts, but they share a larger portion of their most relevant contexts compared to other related words. To prove it, we describe and evaluate APSyn, a variant of Average Precision that, independently of the adopted parameters, outperforms the Vector Cosine and the co-occurrence on the ESL and TOEFL test sets. In the best setting, APSyn reaches 0.73 accuracy on the ESL dataset and 0.70 accuracy in the TOEFL dataset, beating therefore the non-English US college applicants (whose average, as reported in the literature, is 64.50%) and several state-of-the-art approaches.
Solution of Interpolation Problems via the Hankel Polynomial Construction
Venue: arXiv cs.SC 2016
Year: 2016

We treat the interpolation problem $ \{f(x_j)=y_j\}_{j=1}^N $ for polynomial and rational functions. Developing the approach by C.Jacobi, we represent the interpolants by virtue of the Hankel polynomials generated by the sequences $ \{\sum_{j=1}^N x_j^ky_j/W^{\prime}(x_j) \}_{k\in \mathbb N} $ and $ \{\sum_{j=1}^N x_j^k/(y_jW^{\prime}(x_j)) \}_{k\in \mathbb N} $; here $ W(x)=\prod_{j=1}^N(x-x_j) $. The obtained results are applied for the error correction problem, i.e. the problem of reconstructing the polynomial from a redundant set of its values some of which are probably erroneous. The problem of evaluation of the resultant of polynomials $ p(x) $ and $ q(x) $ from the set of values $ \{p(x_j)/q(x_j) \}_{j=1}^N $ is also tackled within the framework of this approach.
Using Enthymemes to Fill the Gap between Logical Argumentation and Revision of Abstract Argumentation Frameworks
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we present a preliminary work on an approach to fill the gap between logic-based argumentation and the numerous approaches to tackle the dynamics of abstract argumentation frameworks. Our idea is that, even when arguments and attacks are defined by means of a logical belief base, there may be some uncertainty about how accurate is the content of an argument, and so the presence (or absence) of attacks concerning it. We use enthymemes to illustrate this notion of uncertainty of arguments and attacks. Indeed, as argued in the literature, real arguments are often enthymemes instead of completely specified deductive arguments. This means that some parts of the pair (support, claim) may be missing because they are supposed to belong to some "common knowledge", and then should be deduced by the agent which receives the enthymeme. But the perception that agents have of the common knowledge may be wrong, and then a first agent may state an enthymeme that her opponent is not able to decode in an accurate way. It is likely that the decoding of the enthymeme by the agent leads to mistaken attacks between this new argument and the existing ones. In this case, the agent can receive some information about attacks or arguments acceptance statuses which disagree with her argumentation framework. We exemplify a way to incorporate this new piece of information by means of existing works on the dynamics of abstract argumentation frameworks.
The SCJ small parsimony problem for weighted gene adjacencies (Extended version)
Venue: arXiv cs.DS 2016
Year: 2016

Reconstructing ancestral gene orders in a given phylogeny is a classical problem in comparative genomics. Most existing methods compare conserved features in extant genomes in the phylogeny to define potential ancestral gene adjacencies, and either try to reconstruct all ancestral genomes under a global evolutionary parsimony criterion, or, focusing on a single ancestral genome, use a scaffolding approach to select a subset of ancestral gene adjacencies, generally aiming at reducing the fragmentation of the reconstructed ancestral genome. In this paper, we describe an exact algorithm for the Small Parsimony Problem that combines both approaches. We consider that gene adjacencies at internal nodes of the species phylogeny are weighted, and we introduce an objective function defined as a convex combination of these weights and the evolutionary cost under the Single-Cut-or-Join (SCJ) model. The weights of ancestral gene adjacencies can e.g. be obtained through the recent availability of ancient DNA sequencing data, which provide a direct hint at the genome structure of the considered ancestor, or through probabilistic analysis of gene adjacencies evolution. We show the NP-hardness of our problem variant and propose a Fixed-Parameter Tractable algorithm based on the Sankoff-Rousseau dynamic programming algorithm that also allows to sample co-optimal solutions. We apply our approach to mammalian and bacterial data providing different degrees of complexity. We show that including adjacency weights in the objective has a significant impact in reducing the fragmentation of the reconstructed ancestral gene orders.