OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Modality Fusion based on Consensus-Voting and 3D Convolution for Isolated Gesture Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Recently, the popularity of depth-sensors such as Kinect has made depth videos easily available while its advantages have not been fully exploited. This paper investigates, for gesture recognition, to explore the spatial and temporal information complementarily embedded in RGB and depth sequences. We propose a convolutional twostream consensus voting network (2SCVN) which explicitly models both the short-term and long-term structure of the RGB sequences. To alleviate distractions from background, a 3d depth-saliency ConvNet stream (3DDSN) is aggregated in parallel to identify subtle motion characteristics. These two components in an unified framework significantly improve the recognition accuracy. On the challenging Chalearn IsoGD benchmark, our proposed method outperforms the first place on the leader-board by a large margin (10.29%) while also achieving the best result on RGBD-HuDaAct dataset (96.74%). Both quantitative experiments and qualitative analysis shows the effectiveness of our proposed framework and codes will be released to facilitate future research.
Minimal and Reduced Reversible Automata
Venue: arXiv cs.FL 2016
Year: 2016

A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, a sufficient condition for the existence of infinitely many reduced reversible automata accepting a same language is given. It is also proved that, when the language is accepted by a unique minimal reversible automaton (that does not necessarily coincide with the minimum deterministic automaton), then no other reduced reversible automata accepting it can exist.
Population Protocols with Faulty Interactions: the Impact of a Leader
Venue: arXiv cs.DC 2016
Year: 2016

We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-way interactions (as opposed to two-way interactions) and omission faults (i.e., failure by an agent to read its partner's state during an interaction), which in turn may be detectable or undetectable. We focus on the impact of a leader, and we give a complete characterization of the models in which the presence of a unique leader in the system allows the construction of simulators: when simulations are possible, we give explicit protocols; when they are not, we give proofs of impossibility. Specifically, if each agent has only a finite amount of memory, the simulation is possible only if there are no omission faults. If agents have an unbounded amount of memory, the simulation is possible as long as omissions are detectable. If an upper bound on the number of omissions involving the leader is known, the simulation is always possible, except in the one-way model in which one side is unable to detect the interaction.
Unsupervised Learning for Lexicon-Based Classification
Venue: arXiv cs.LG 2016
Year: 2016

In lexicon-based classification, documents are assigned labels by comparing the number of words that appear from two opposed lexicons, such as positive and negative sentiment. Creating such words lists is often easier than labeling instances, and they can be debugged by non-experts if classification performance is unsatisfactory. However, there is little analysis or justification of this classification heuristic. This paper describes a set of assumptions that can be used to derive a probabilistic justification for lexicon-based classification, as well as an analysis of its expected accuracy. One key assumption behind lexicon-based classification is that all words in each lexicon are equally predictive. This is rarely true in practice, which is why lexicon-based approaches are usually outperformed by supervised classifiers that learn distinct weights on each word from labeled instances. This paper shows that it is possible to learn such weights without labeled data, by leveraging co-occurrence statistics across the lexicons. This offers the best of both worlds: light supervision in the form of lexicons, and data-driven classification with higher accuracy than traditional word-counting heuristics.
Multi-sensor perceptual system for mobile robot and sensor fusion-based localization
Venue: arXiv cs.RO 2016
Year: 2016

This paper presents an Extended Kalman Filter (EKF) approach to localize a mobile robot with two quadrature encoders, a compass sensor, a laser range finder (LRF) and an omni-directional camera. The prediction step is performed by employing the kinematic model of the robot as well as estimating the input noise covariance matrix as being proportional to the wheel's angular speed. At the correction step, the measurements from all sensors including incremental pulses of the encoders, line segments of the LRF, robot orientation of the compass and deflection angular of the omni-directional camera are fused. Experiments in an indoor structured environment were implemented and the good localization results prove the effectiveness and applicability of the algorithm.
Will My Tests Tell Me If I Break This Code?
Venue: arXiv cs.SE 2016
Year: 2016

Automated tests play an important role in software evolution because they can rapidly detect faults introduced during changes. In practice, code-coverage metrics are often used as criteria to evaluate the effectiveness of test suites with focus on regression faults. However, code coverage only expresses which portion of a system has been executed by tests, but not how effective the tests actually are in detecting regression faults. Our goal was to evaluate the validity of code coverage as a measure for test effectiveness. To do so, we conducted an empirical study in which we applied an extreme mutation testing approach to analyze the tests of open-source projects written in Java. We assessed the ratio of pseudo-tested methods (those tested in a way such that faults would not be detected) to all covered methods and judged their impact on the software project. The results show that the ratio of pseudo-tested methods is acceptable for unit tests but not for system tests (that execute large portions of the whole system). Therefore, we conclude that the coverage metric is only a valid effectiveness indicator for unit tests.
CAS-CNN: A Deep Convolutional Neural Network for Image Compression Artifact Suppression
Venue: arXiv cs.CV 2016
Year: 2016

Lossy image compression algorithms are pervasively used to reduce the size of images transmitted over the web and recorded on data storage media. However, we pay for their high compression rate with visual artifacts degrading the user experience. Deep convolutional neural networks have become a widespread tool to address high-level computer vision tasks very successfully. Recently, they have found their way into the areas of low-level computer vision and image processing to solve regression problems mostly with relatively shallow networks. We present a novel 12-layer deep convolutional network for image compression artifact suppression with hierarchical skip connections and a multi-scale loss function. We achieve a boost of up to 1.79 dB in PSNR over ordinary JPEG and an improvement of up to 0.36 dB over the best previous ConvNet result. We show that a network trained for a specific quality factor (QF) is resilient to the QF used to compress the input image - a single network trained for QF 60 provides a PSNR gain of more than 1.5 dB over the wide QF range from 40 to 76.
Time and Space Optimal Counting in Population Protocols
Venue: arXiv cs.DC 2016
Year: 2016

This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of (exact) counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized. This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of counting given the optimal space per agent. In the case of randomly interacting agents (probabilistic fairness), as usual, the convergence time is measured in terms of parallel time (or parallel interactions), which is defined as the number of pairwise interactions until convergence, divided by n (the number of agents). In case of weak fairness, where it is only required that every pair of agents interacts infinitely often, the convergence time is defined in terms of non-null transitions, i.e, the transitions that affect the states of the interacting agents.First, assuming probabilistic fairness, we present a "non-guessing" time optimal protocol of O(n log n) expected time given an optimal space of only one bit, and we prove the time optimality of this protocol. Then, for weak fairness, we show that a space optimal (semi-uniform) solution cannot converge faster than in $Ω$(2^n) time (non-null transitions). This result, together with the time complexity analysis of an already known space optimal protocol, shows that it is also optimal in time (given the optimal space constrains).
MOMOS-MT: Mobile Monophonic System for Music Transcription
Venue: arXiv cs.SD 2016
Year: 2016

Music holds a significant cultural role in social identity and in the encouragement of socialization. Technology, by the destruction of physical and cultural distance, has lead to many changes in musical themes and the complete loss of forms. Yet, it also allows for the preservation and distribution of music from societies without a history of written sheet music. This paper presents early work on a tool for musicians and ethnomusicologists to transcribe sheet music from monophonic voiced pieces for preservation and distribution. Using FFT, the system detects the pitch frequencies, also other methods detect note durations, tempo, time signatures and generates sheet music. The final system is able to be used in mobile platforms allowing the user to take recordings and produce sheet music in situ to a performance.
Discretization of Maxwell's Equations for Non-inertial Observers Using Space-Time Algebra
Venue: arXiv cs.CE 2016
Year: 2016

We employ Maxwell's equations formulated in Space-Time Algebra to perform discretization of moving geometries directly in space-time. All the derivations are carried out without any non-relativistic assumptions, thus the application area of the scheme is not restricted to low velocities. The 4D mesh construction is based on a 3D mesh stemming from a conventional 3D mesh generator. The movement of the system is encoded in the 4D mesh geometry, enabling an easy extension of well-known 3D approaches to the space-time setting. As a research example, we study a manifestation of Sagnac's effect in a rotating ring resonator. In case of constant rotation, the space-time approach enhances the efficiency of the scheme, as the material matrices are constant for every time step, without abandoning the relativistic framework.
A Non-Intrusive and Context-Based Vulnerability Scoring Framework for Cloud Services
Venue: arXiv cs.CR 2016
Year: 2016

Understanding the severity of vulnerabilities within cloud services is particularly important for today service administrators.Although many systems, e.g., CVSS, have been built to evaluate and score the severity of vulnerabilities for administrators, the scoring schemes employed by these systems fail to take into account the contextual information of specific services having these vulnerabilities, such as what roles they play in a particular service. Such a deficiency makes resulting scores unhelpful. This paper presents a practical framework, NCVS, that offers automatic and contextual scoring mechanism to evaluate the severity of vulnerabilities for a particular service. Specifically, for a given service S, NCVS first automatically collects S contextual information including topology, configurations, vulnerabilities and their dependencies. Then, NCVS uses the collected information to build a contextual dependency graph, named CDG, to model S context. Finally, NCVS scores and ranks all the vulnerabilities in S by analyzing S context, such as what roles the vulnerabilities play in S, and how critical they affect the functionality of S. NCVS is novel and useful, because 1) context-based vulnerability scoring results are highly relevant and meaningful for administrators to understand each vulnerability importance specific to the target service; and 2) the workflow of NCVS does not need instrumentation or modifications to any source code. Our experimental results demonstrate that NCVS can obtain more relevant vulnerability scoring results than comparable system, such as CVSS.
Non-linear Barrier Coverage using Mobile Wireless Sensors
Venue: arXiv cs.NI 2016
Year: 2016

A belt region is said to be k-barrier covered by a set of sensors if all paths crossing the width of the belt region intersect the sensing regions of at least k sensors. Barrier coverage can be achieved from a random initial deployment of mobile sensors by suitably relocating the sensors to form a barrier. Reducing the movement of the sensors is important in such scenarios due to the energy constraints of sensor devices. In this paper, we propose a centralized algorithm which achieves 1-barrier coverage by forming a non-linear barrier from a random initial deployment of sensors in a belt. The algorithm uses a novel idea of physical behavior of chains along with the concept of virtual force. Formation of non-linear barrier reduces the movement of the sensors needed as compared to linear barriers. Detailed simulation results are presented to show that the proposed algorithm achieves barrier coverage with less movement of sensors compared to other existing algorithms in the literature.
Component-based Synthesis of Table Consolidation and Transformation Tasks from Examples
Venue: arXiv cs.PL 2016
Year: 2016

This paper presents an example-driven synthesis technique for automating a large class of data preparation tasks that arise in data science. Given a set of input tables and an out- put table, our approach synthesizes a table transformation program that performs the desired task. Our approach is not restricted to a fixed set of DSL constructs and can synthesize programs from an arbitrary set of components, including higher-order combinators. At a high-level, our approach performs type-directed enumerative search over partial pro- grams but incorporates two key innovations that allow it to scale: First, our technique can utilize any first-order specification of the components and uses SMT-based deduction to reject partial programs. Second, our algorithm uses partial evaluation to increase the power of deduction and drive enumerative search. We have evaluated our synthesis algorithm on dozens of data preparation tasks obtained from on-line forums, and we show that our approach can automatically solve a large class of problems encountered by R users.
Data Structures for Weighted Matching and Extensions to $b$-matching and $f$-factors
Venue: arXiv cs.DS 2016
Year: 2016

This paper shows the weighted matching problem on general graphs can be solved in time $O(n(m + n\log n))$ for $n$ and $m$ the number of vertices and edges, respectively. This was previously known only for bipartite graphs. The crux is a data structure for blossom creation. It uses a dynamic nearest-common-ancestor algorithm to simplify blossom steps, so they involve only back edges rather than arbitrary nontree edges. The rest of the paper presents direct extensions of Edmonds' blossom algorithm to weighted $b$-matching and $f$-factors. Again the time bound is the one previously known for bipartite graphs: for $b$-matching the time is $O(\min\{b(V),n\log n\}(m + n\log n))$ and for $f$-factors the time is $O(\min\{f(V),m\log n\}( m + n\log n) )$, where $b(V)$ and $f(V)$ denote the sum of all degree constraints. Several immediate applications of the $f$-factor algorithm are given: The generalized shortest path structure of \cite{GS13}, i.e., the analog of the shortest path tree for conservative undirected graphs, is shown to be a version of the blossom structure for $f$-factors. This structure is found in time $O(|N|(m+n\log n))$ for $N$ the set of negative edges ($0<|N|<n$). A shortest $T$-join is found in time $O(n(m+n\log n))$, or $O(|T|(m+n\log n))$ when all costs are nonnegative. These bounds are all slight improvements of previously known ones, and are simply achieved by proper initialization of the $f$-factor algorithm.
On the Benefit of Automated Static Analysis for Small and Medium-Sized Software Enterprises
Venue: arXiv cs.SE 2016
Year: 2016

Today's small and medium-sized enterprises (SMEs) in the software industry are faced with major challenges. While having to work efficiently using limited resources they have to perform quality assurance on their code to avoid the risk of further effort for bug fixes or compensations. Automated static analysis can reduce this risk because it promises little effort for running an analysis. We report on our experience in analysing five projects from and with SMEs by three different static analysis techniques: code clone detection, bug pattern detection and architecture conformance analysis. We found that the effort that was needed to introduce those techniques was small (mostly below one person-hour), that we can detect diverse defects in production code and that the participating companies perceived the usefulness of the presented techniques as well as our analysis results high enough to include the techniques in their quality assurance.
Feature Importance Measure for Non-linear Learning Algorithms
Venue: arXiv cs.AI 2016
Year: 2016

Complex problems may require sophisticated, non-linear learning methods such as kernel machines or deep neural networks to achieve state of the art prediction accuracies. However, high prediction accuracies are not the only objective to consider when solving problems using machine learning. Instead, particular scientific applications require some explanation of the learned prediction function. Unfortunately, most methods do not come with out of the box straight forward interpretation. Even linear prediction functions are not straight forward to explain if features exhibit complex correlation structure. In this paper, we propose the Measure of Feature Importance (MFI). MFI is general and can be applied to any arbitrary learning machine (including kernel machines and deep learning). MFI is intrinsically non-linear and can detect features that by itself are inconspicuous and only impact the prediction function through their interaction with other features. Lastly, MFI can be used for both --- model-based feature importance and instance-based feature importance (i.e, measuring the importance of a feature for a particular data point).
What You Really Need To Know About Your Neighbor
Venue: arXiv cs.LO 2016
Year: 2016

A fundamental question in system design is to decide how much of the design of one component must be known in order to successfully design another component of the system. We study this question in the setting of reactive synthesis, where one constructs a system implementation from a specification given in temporal logic. In previous work, we have shown that the system can be constructed compositionally, one component at a time, if the specification admits a "dominant" (as explained in Introduction) strategy for each component. In this paper, we generalize the approach to settings where dominant strategies only exist under certain assumptions about the future behavior of the other components. We present an incremental synthesis method based on the automatic construction of such assumptions.
Video Captioning with Transferred Semantic Attributes
Venue: arXiv cs.CV 2016
Year: 2016

Automatically generating natural language descriptions of videos plays a fundamental challenge for computer vision community. Most recent progress in this problem has been achieved through employing 2-D and/or 3-D Convolutional Neural Networks (CNN) to encode video content and Recurrent Neural Networks (RNN) to decode a sentence. In this paper, we present Long Short-Term Memory with Transferred Semantic Attributes (LSTM-TSA)---a novel deep architecture that incorporates the transferred semantic attributes learnt from images and videos into the CNN plus RNN framework, by training them in an end-to-end manner. The design of LSTM-TSA is highly inspired by the facts that 1) semantic attributes play a significant contribution to captioning, and 2) images and videos carry complementary semantics and thus can reinforce each other for captioning. To boost video captioning, we propose a novel transfer unit to model the mutually correlated attributes learnt from images and videos. Extensive experiments are conducted on three public datasets, i.e., MSVD, M-VAD and MPII-MD. Our proposed LSTM-TSA achieves to-date the best published performance in sentence generation on MSVD: 52.8% and 74.0% in terms of BLEU@4 and CIDEr-D. Superior results when compared to state-of-the-art methods are also reported on M-VAD and MPII-MD.
Simultaneous Feedback Edge Set: A Parameterized Perspective
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we consider Simultaneous Feedback Edge Set (Sim-FES) problem. In this problem, the input is an $n$-vertex graph $G$, an integer $k$ and a coloring function ${\sf col}: E(G) \rightarrow 2^{[α]}$ and the objective is to check whether there is an edge subset $S$ of cardinality at most $k$ in $G$ such that for all $i \in [α]$, $G_i - S$ is acyclic. Here, $G_i=(V(G), \{e\in E(G) \mid i \in {\sf col}(e)\})$ and $[α]=\{1,\ldots,α\}$. When $α=1$, the problem is polynomial time solvable. We show that for $α=3$ Sim-FES is NP-hard by giving a reduction from Vertex Cover on cubic graphs. The same reduction shows that the problem does not admit an algorithm of running time $O(2^{o(k)}n^{O(1)})$ unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time $O(2^{ωkα+α\log k} n^{O(1)})$, where $ω$ is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when $α=2$. We also give a kernel for Sim-FES with $(kα)^{O(α)}$ vertices. Finally, we consider the problem Maximum Simultaneous Acyclic Subgraph. Here, the input is a graph $G$, an integer $q$ and, a coloring function ${\sf col}: E(G) \rightarrow 2^{[α]}$. The question is whether there is a edge subset $F$ of cardinality at least $q$ in $G$ such that for all $i\in [α]$, $G[F_i]$ is acyclic. Here, $F_i=\{e \in F \mid i \in \textsf{col}(e)\}$. We give an FPT algorithm for running in time $O(2^{ωq α}n^{O(1)})$.
Timing Attack Resilient Decoding Algorithms for Physical Unclonable Functions
Venue: arXiv cs.IT 2016
Year: 2016

This paper deals with the application of list decoding of Reed--Solomon codes to a concatenated code for key reproduction using Physical Unclonable Functions. The resulting codes achieve a higher error-correction performance at the same code rate than known schemes in this scenario. We also show that their decoding algorithms can be protected from side-channel attacks on the runtime both by masking techniques and by directly modifying the algorithms to have constant runtime.