OpenRaiser/Intern-Atlas huggingface dataset:
Coloring Down: $3/2$-approximation for special cases of the weighted tree augmentation problem
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we investigate the weighted tree augmentation problem (TAP), where the goal is to augment a tree with a minimum cost set of edges such that the graph becomes two edge connected. First we show that in weighted TAP, we can restrict our attention to trees which are binary and where all the non-tree edges go between two leaves of the tree. We then give two different top-down coloring algorithms. Both algorithms differ from known techniques for a 3/2-approximation in unweighted TAP and current attempts to reach a 3/2-approximation for weighted TAP. The first algorithm we describe always gives a 2-approximation for any feasible fractional solution to the natural edge cover LP. When the fractional solution is such that all the edges with non-zero weight are at least $α$, then this algorithm achieves a $2/(1+α)$-approximation. We propose a new conjecture on extreme points of LP relaxations for the problem, which if true, will lead to a constructive proof of an integrality gap of at most 3/2 for weighted TAP. In the second algorithm, we introduce simple valid constraints to the edge cover LP. In this algorithm, we focus on deficient edges, edges covered to an extent less than 4/3 in the fractional solution. We show that for fractional feasible solutions, deficient edges occur in node-disjoint paths in the tree. When the number of such paths is at most two, we give a top-down coloring algorithm which decomposes 3/2 times the fractional solution into a convex combination of integer solutions. We believe our algorithms will be useful in eventually resolving the integrality gap of linear programming formulations for TAP. We also investigate a variant of TAP where each edge in the solution must be covered by a cycle of length three. We give a $Θ(\log n)$-approximation algorithm for this problem in the weighted case and a 4-approximation in the unweighted case.
Some Improvements in Fuzzy Turing Machines
Venue: arXiv cs.LO 2017
Year: 2017

In this paper, we modify some previous definitions of fuzzy Turing machines to define the notions of accepting and rejecting degrees of inputs, computationally. We use a BFS-based search method and obtain an upper level bound to guarantee the existence of accepting and rejecting degrees. We show that fuzzy, generalized fuzzy and classical Turing machines have the same computational power. Next, we introduce the class of Extended Fuzzy Turing Machines equipped with indeterminacy states. These machines are used to catch some types of loops of the classical Turing machines. Moreover, to each r.e. or co-r.e language, we correspond a fuzzy language which is indeterminable by an extended fuzzy Turing machine.
Unsupervised Iterative Deep Learning of Speech Features and Acoustic Tokens with Applications to Spoken Term Detection
Venue: arXiv cs.CL 2017
Year: 2017

In this paper we aim to automatically discover high quality frame-level speech features and acoustic tokens directly from unlabeled speech data. A Multi-granular Acoustic Tokenizer (MAT) was proposed for automatic discovery of multiple sets of acoustic tokens from the given corpus. Each acoustic token set is specified by a set of hyperparameters describing the model configuration. These different sets of acoustic tokens carry different characteristics for the given corpus and the language behind, thus can be mutually reinforced. The multiple sets of token labels are then used as the targets of a Multi-target Deep Neural Network (MDNN) trained on frame-level acoustic features. Bottleneck features extracted from the MDNN are then used as the feedback input to the MAT and the MDNN itself in the next iteration. The multi-granular acoustic token sets and the frame-level speech features can be iteratively optimized in the iterative deep learning framework. We call this framework the Multi-granular Acoustic Tokenizing Deep Neural Network (MATDNN). The results were evaluated using the metrics and corpora defined in the Zero Resource Speech Challenge organized at Interspeech 2015, and improved performance was obtained with a set of experiments of query-by-example spoken term detection on the same corpora. Visualization for the discovered tokens against the English phonemes was also shown.
PDD Graph: Bridging Electronic Medical Records and Biomedical Knowledge Graphs via Entity Linking
Venue: arXiv cs.DB 2017
Year: 2017

Electronic medical records contain multi-format electronic medical data that consist of an abundance of medical knowledge. Facing with patient's symptoms, experienced caregivers make right medical decisions based on their professional knowledge that accurately grasps relationships between symptoms, diagnosis and corresponding treatments. In this paper, we aim to capture these relationships by constructing a large and high-quality heterogenous graph linking patients, diseases, and drugs (PDD) in EMRs. Specifically, we propose a novel framework to extract important medical entities from MIMIC-III (Medical Information Mart for Intensive Care III) and automatically link them with the existing biomedical knowledge graphs, including ICD-9 ontology and DrugBank. The PDD graph presented in this paper is accessible on the Web via the SPARQL endpoint, and provides a pathway for medical discovery and applications, such as effective treatment recommendations.
Incremental Boosting Convolutional Neural Network for Facial Action Unit Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Recognizing facial action units (AUs) from spontaneous facial expressions is still a challenging problem. Most recently, CNNs have shown promise on facial AU recognition. However, the learned CNNs are often overfitted and do not generalize well to unseen subjects due to limited AU-coded training images. We proposed a novel Incremental Boosting CNN (IB-CNN) to integrate boosting into the CNN via an incremental boosting layer that selects discriminative neurons from the lower layer and is incrementally updated on successive mini-batches. In addition, a novel loss function that accounts for errors from both the incremental boosted classifier and individual weak classifiers was proposed to fine-tune the IB-CNN. Experimental results on four benchmark AU databases have demonstrated that the IB-CNN yields significant improvement over the traditional CNN and the boosting CNN without incremental learning, as well as outperforming the state-of-the-art CNN-based methods in AU recognition. The improvement is more impressive for the AUs that have the lowest frequencies in the databases.
Study and Analysis of MAC/IPAD Lab Configuration
Venue: arXiv cs.OS 2017
Year: 2017

This paper is about three virtualization modes: VMware, Parallels, and Boot Camping. The trade off of their testing is the hardware requirements. The main question is, among the three, which is the most suitable? The answer actually varies from user to user. It depends on the user needs. Moreover, it is necessary to consider its performance, graphics, efficiency and reliability, and interoperability, and that is our major scope. In order to take the final decision in choosing one of the modes it is important to run some tests, which costs a lot in terms of money, complexity, and time consumption. Therefore, in order to overcome this trade off, most of the research has been done through online benchmarking and my own anticipation. The final solution was extracted after comparing all previously mentioned above and after rigorous testing made which will be introduced later in this document.
Hybrid PS-V Technique: A Novel Sensor Fusion Approach for Fast Mobile Eye-Tracking with Sensor-Shift Aware Correction
Venue: arXiv cs.CV 2017
Year: 2017

This paper introduces and evaluates a hybrid technique that fuses efficiently the eye-tracking principles of photosensor oculography (PSOG) and video oculography (VOG). The main concept of this novel approach is to use a few fast and power-economic photosensors as the core mechanism for performing high speed eye-tracking, whereas in parallel, use a video sensor operating at low sampling-rate (snapshot mode) to perform dead-reckoning error correction when sensor movements occur. In order to evaluate the proposed method, we simulate the functional components of the technique and present our results in experimental scenarios involving various combinations of horizontal and vertical eye and sensor movements. Our evaluation shows that the developed technique can be used to provide robustness to sensor shifts that otherwise could induce error larger than 5 deg. Our analysis suggests that the technique can potentially enable high speed eye-tracking at low power profiles, making it suitable to be used in emerging head-mounted devices, e.g. AR/VR headsets.
Photosensor Oculography: Survey and Parametric Analysis of Designs using Model-Based Simulation
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a renewed overview of photosensor oculography (PSOG), an eye-tracking technique based on the principle of using simple photosensors to measure the amount of reflected (usually infrared) light when the eye rotates. Photosensor oculography can provide measurements with high precision, low latency and reduced power consumption, and thus it appears as an attractive option for performing eye-tracking in the emerging head-mounted interaction devices, e.g. augmented and virtual reality (AR/VR) headsets. In our current work we employ an adjustable simulation framework as a common basis for performing an exploratory study of the eye-tracking behavior of different photosensor oculography designs. With the performed experiments we explore the effects from the variation of some basic parameters of the designs on the resulting accuracy and cross-talk, which are crucial characteristics for the seamless operation of human-computer interaction applications based on eye-tracking. Our experimental results reveal the design trade-offs that need to be adopted to tackle the competing conditions that lead to optimum performance of different eye-tracking characteristics. We also present the transformations that arise in the eye-tracking output when sensor shifts occur, and assess the resulting degradation in accuracy for different combinations of eye movements and sensor shifts.
Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
Venue: arXiv cs.CG 2017
Year: 2017

We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph $GK_n$ on any set $S$ of $n$ points in general position in the plane? We show that this number is in $Ω(\sqrt{n})$. Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths).
Stabilization Control of the Differential Mobile Robot Using Lyapunov Function and Extended Kalman Filter
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents the design of a control model to navigate the differential mobile robot to reach the desired destination from an arbitrary initial pose. The designed model is divided into two stages: the state estimation and the stabilization control. In the state estimation, an extended Kalman filter is employed to optimally combine the information from the system dynamics and measurements. Two Lyapunov functions are constructed that allow a hybrid feedback control law to execute the robot movements. The asymptotical stability and robustness of the closed loop system are assured. Simulations and experiments are carried out to validate the effectiveness and applicability of the proposed approach.
Detecting Intentional Lexical Ambiguity in English Puns
Venue: arXiv cs.CL 2017
Year: 2017

The article describes a model of automatic analysis of puns, where a word is intentionally used in two meanings at the same time (the target word). We employ Roget's Thesaurus to discover two groups of words which, in a pun, form around two abstract bits of meaning (semes). They become a semantic vector, based on which an SVM classifier learns to recognize puns, reaching a score 0.73 for F-measure. We apply several rule-based methods to locate intentionally ambiguous (target) words, based on structural and semantic criteria. It appears that the structural criterion is more effective, although it possibly characterizes only the tested dataset. The results we get correlate with the results of other teams at SemEval-2017 competition (Task 7 Detection and Interpretation of English Puns) considering effects of using supervised learning models and word statistics.
APE-GAN: Adversarial Perturbation Elimination with GAN
Venue: arXiv cs.CV 2017
Year: 2017

Although neural networks could achieve state-of-the-art performance while recongnizing images, they often suffer a tremendous defeat from adversarial examples--inputs generated by utilizing imperceptible but intentional perturbation to clean samples from the datasets. How to defense against adversarial examples is an important problem which is well worth researching. So far, very few methods have provided a significant defense to adversarial examples. In this paper, a novel idea is proposed and an effective framework based Generative Adversarial Nets named APE-GAN is implemented to defense against the adversarial examples. The experimental results on three benchmark datasets including MNIST, CIFAR10 and ImageNet indicate that APE-GAN is effective to resist adversarial examples generated from five attacks.
Order-Free RNN with Visual Attention for Multi-Label Classification
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we propose the joint learning attention and recurrent neural network (RNN) models for multi-label classification. While approaches based on the use of either model exist (e.g., for the task of image captioning), training such existing network architectures typically require pre-defined label sequences. For multi-label classification, it would be desirable to have a robust inference process, so that the prediction error would not propagate and thus affect the performance. Our proposed model uniquely integrates attention and Long Short Term Memory (LSTM) models, which not only addresses the above problem but also allows one to identify visual objects of interests with varying sizes without the prior knowledge of particular label ordering. More importantly, label co-occurrence information can be jointly exploited by our LSTM model. Finally, by advancing the technique of beam search, prediction of multiple labels can be efficiently achieved by our proposed network model.
SECMACE: Scalable and Robust Identity and Credential Management Infrastructure in Vehicular Communication Systems
Venue: arXiv cs.CR 2017
Year: 2017

Several years of academic and industrial research efforts have converged to a common understanding on fundamental security building blocks for the upcoming Vehicular Communication (VC) systems. There is a growing consensus towards deploying a special-purpose identity and credential management infrastructure, i.e., a Vehicular Public-Key Infrastructure (VPKI), enabling pseudonymous authentication, with standardization efforts towards that direction. In spite of the progress made by standardization bodies (IEEE 1609.2 and ETSI) and harmonization efforts (Car2Car Communication Consortium (C2C-CC)), significant questions remain unanswered towards deploying a VPKI. Deep understanding of the VPKI, a central building block of secure and privacy-preserving VC systems, is still lacking. This paper contributes to the closing of this gap. We present SECMACE, a VPKI system, which is compatible with the IEEE 1609.2 and ETSI standards specifications. We provide a detailed description of our state-of-the-art VPKI that improves upon existing proposals in terms of security and privacy protection, and efficiency. SECMACE facilitates multi-domain operations in the VC systems and enhances user privacy, notably preventing linking pseudonyms based on timing information and offering increased protection even against honest-but-curious VPKI entities. We propose multiple policies for the vehicle-VPKI interactions, based on which and two large-scale mobility trace datasets, we evaluate the full-blown implementation of SECMACE. With very little attention on the VPKI performance thus far, our results reveal that modest computing resources can support a large area of vehicles with very low delays and the most promising policy in terms of privacy protection can be supported with moderate overhead.
Beyond Forward Shortcuts: Fully Convolutional Master-Slave Networks (MSNets) with Backward Skip Connections for Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Recent deep CNNs contain forward shortcut connections; i.e. skip connections from low to high layers. Reusing features from lower layers that have higher resolution (location information) benefit higher layers to recover lost details and mitigate information degradation. However, during inference the lower layers do not know about high layer features, although they contain contextual high semantics that benefit low layers to adaptively extract informative features for later layers. In this paper, we study the influence of backward skip connections which are in the opposite direction to forward shortcuts, i.e. paths from high layers to low layers. To achieve this -- which indeed runs counter to the nature of feed-forward networks -- we propose a new fully convolutional model that consists of a pair of networks. A `Slave' network is dedicated to provide the backward connections from its top layers to the `Master' network's bottom layers. The Master network is used to produce the final label predictions. In our experiments we validate the proposed FCN model on ADE20K (ImageNet scene parsing), PASCAL-Context, and PASCAL VOC 2011 datasets.
The Finite Satisfiability Problem for Two-Variable, First-Order Logic with one Transitive Relation is Decidable
Venue: arXiv cs.LO 2017
Year: 2017

We consider the two-variable fragment of first-order logic with one distinguished binary predicate constrained to be interpreted as a transitive relation. The finite satisfiability problem for this logic is shown to be decidable, in triply exponential non-deterministic time. The complexity falls to doubly exponential non-deterministic time if the distinguished binary predicate is constrained to be interpreted as a partial order.
Inspecting Maude Variants with GLINTS
Venue: arXiv cs.LO 2017
Year: 2017

This paper introduces GLINTS, a graphical tool for exploring variant narrowing computations in Maude. The most recent version of Maude, version 2.7.1, provides quite sophisticated unification features, including order-sorted equational unification for convergent theories modulo axioms such as associativity, commutativity, and identity (ACU). This novel equational unification relies on built-in generation of the set of 'variants' of a term $t$, i.e., the canonical form of $t σ$ for a computed substitution $σ$. Variant generation relies on a novel narrowing strategy called 'folding variant narrowing' that opens up new applications in formal reasoning, theorem proving, testing, protocol analysis, and model checking, especially when the theory satisfies the 'finite variant property', i.e., there is a finite number of most general variants for every term in the theory. However, variant narrowing computations can be extremely involved and are simply presented in text format by Maude, often being too heavy to be debugged or even understood. The GLINTS system provides support for (i) determining whether a given theory satisfies the finite variant property, (ii) thoroughly exploring variant narrowing computations, (iii) automatic checking of node 'embedding' and 'closedness' modulo axioms, and (iv) querying and inspecting selected parts of the variant trees. This paper is under consideration for acceptance in TPLP.
Gibbard-Satterthwaite Games for k-Approval Voting Rules
Venue: arXiv cs.GT 2017
Year: 2017

The Gibbard-Satterthwaite theorem implies the existence of voters, called manipulators, who can change the election outcome in their favour by voting strategically. When a given preference profile admits several such manipulators, voting becomes a game played by these voters, who have to reason strategically about each others' actions. To complicate the game even further, counter-manipulators may then try to counteract the actions of manipulators. Our voters are boundedly rational and do not think beyond manipulating or countermanipulating. We call these games Gibbard--Satterthwaite Games. In this paper we look for conditions that guarantee the existence of a Nash equilibria in pure strategies.
Spherical Paragraph Model
Venue: arXiv cs.CL 2017
Year: 2017

Representing texts as fixed-length vectors is central to many language processing tasks. Most traditional methods build text representations based on the simple Bag-of-Words (BoW) representation, which loses the rich semantic relations between words. Recent advances in natural language processing have shown that semantically meaningful representations of words can be efficiently acquired by distributed models, making it possible to build text representations based on a better foundation called the Bag-of-Word-Embedding (BoWE) representation. However, existing text representation methods using BoWE often lack sound probabilistic foundations or cannot well capture the semantic relatedness encoded in word vectors. To address these problems, we introduce the Spherical Paragraph Model (SPM), a probabilistic generative model based on BoWE, for text representation. SPM has good probabilistic interpretability and can fully leverage the rich semantics of words, the word co-occurrence information as well as the corpus-wide information to help the representation learning of texts. Experimental results on topical classification and sentiment analysis demonstrate that SPM can achieve new state-of-the-art performances on several benchmark datasets.
Quantum Computation via Sparse Distributed Representation
Venue: arXiv cs.NE 2017
Year: 2017

Quantum superposition says that any physical system simultaneously exists in all of its possible states, the number of which is exponential in the number of entities composing the system. The strength of presence of each possible state in the superposition, i.e., its probability of being observed, is represented by its probability amplitude coefficient. The assumption that these coefficients must be represented physically disjointly from each other, i.e., localistically, is nearly universal in the quantum theory/computing literature. Alternatively, these coefficients can be represented using sparse distributed representations (SDR), wherein each coefficient is represented by small subset of an overall population of units, and the subsets can overlap. Specifically, I consider an SDR model in which the overall population consists of Q WTA clusters, each with K binary units. Each coefficient is represented by a set of Q units, one per cluster. Thus, K^Q coefficients can be represented with KQ units. Thus, the particular world state, X, whose coefficient's representation, R(X), is the set of Q units active at time t has the max probability and the probability of every other state, Y_i, at time t, is measured by R(Y_i)'s intersection with R(X). Thus, R(X) simultaneously represents both the particular state, X, and the probability distribution over all states. Thus, set intersection may be used to classically implement quantum superposition. If algorithms exist for which the time it takes to store (learn) new representations and to find the closest-matching stored representation (probabilistic inference) remains constant as additional representations are stored, this meets the criterion of quantum computing. Such an algorithm has already been described: it achieves this "quantum speed-up" without esoteric hardware, and in fact, on a single-processor, classical (Von Neumann) computer.