OpenRaiser/Intern-Atlas huggingface dataset:
Shape and Centroid Independent Clustring Algorithm for Crowd Management Applications
Venue: arXiv cs.CV 2016
Year: 2016

Clustering techniques play an important role in data mining and its related applications. Among the challenging applications that require robust and real-time processing are crowd management and group trajectory applications. In this paper, a robust and low-complexity clustering algorithm is proposed. It is capable of processing data in a manner that is shape and centroid independent. The algorithm is of low complexity due to the novel technique to compute the matrix power. The algorithm was tested on real and synthetic data and test results are reported.
New word analogy corpus for exploring embeddings of Czech words
Venue: arXiv cs.CL 2016
Year: 2016

The word embedding methods have been proven to be very useful in many tasks of NLP (Natural Language Processing). Much has been investigated about word embeddings of English words and phrases, but only little attention has been dedicated to other languages. Our goal in this paper is to explore the behavior of state-of-the-art word embedding methods on Czech, the language that is characterized by very rich morphology. We introduce new corpus for word analogy task that inspects syntactic, morphosyntactic and semantic properties of Czech words and phrases. We experiment with Word2Vec and GloVe algorithms and discuss the results on this corpus. The corpus is available for the research community.
A New Android Malware Detection Approach Using Bayesian Classification
Venue: arXiv cs.CR 2016
Year: 2016

Mobile malware has been growing in scale and complexity as smartphone usage continues to rise. Android has surpassed other mobile platforms as the most popular whilst also witnessing a dramatic increase in malware targeting the platform. A worrying trend that is emerging is the increasing sophistication of Android malware to evade detection by traditional signature-based scanners. As such, Android app marketplaces remain at risk of hosting malicious apps that could evade detection before being downloaded by unsuspecting users. Hence, in this paper we present an effective approach to alleviate this problem based on Bayesian classification models obtained from static code analysis. The models are built from a collection of code and app characteristics that provide indicators of potential malicious activities. The models are evaluated with real malware samples in the wild and results of experiments are presented to demonstrate the effectiveness of the proposed approach.
Sparse Suffix Tree Construction in Optimal Time and Space
Venue: arXiv cs.DS 2016
Year: 2016

Suffix tree (and the closely related suffix array) are fundamental structures capturing all substrings of a given text essentially by storing all its suffixes in the lexicographical order. In some applications, we work with a subset of $b$ interesting suffixes, which are stored in the so-called sparse suffix tree. Because the size of this structure is $Θ(b)$, it is natural to seek a construction algorithm using only $O(b)$ words of space assuming read-only random access to the text. We design a linear-time Monte Carlo algorithm for this problem, hence resolving an open question explicitly stated by Bille et al. [TALG 2016]. The best previously known algorithm by I et al. [STACS 2014] works in $O(n\log b)$ time. Our solution proceeds in $n/b$ rounds; in the $r$-th round, we consider all suffixes starting at positions congruent to $r$ modulo $n/b$. By maintaining rolling hashes, we lexicographically sort all interesting suffixes starting at such positions, and then we merge them with the already considered suffixes. For efficient merging, we also need to answer LCE queries in small space. By plugging in the structure of Bille et al. [CPM 2015] we obtain $O(n+b\log b)$ time complexity. We improve this structure, which implies a linear-time sparse suffix tree construction algorithm. We complement our Monte Carlo algorithm with a deterministic verification procedure. The verification takes $O(n\sqrt{\log b})$ time, which improves upon the bound of $O(n\log b)$ obtained by I et al. [STACS 2014]. This is obtained by first observing that the pruning done inside the previous solution has a rather clean description using the notion of graph spanners with small multiplicative stretch. Then, we are able to decrease the verification time by applying difference covers twice. Combined with the Monte Carlo algorithm, this gives us an $O(n\sqrt{\log b})$-time and $O(b)$-space Las Vegas algorithm.
PageRank in Malware Categorization
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we propose a malware categorization method that models malware behavior in terms of instructions using PageRank. PageRank computes ranks of web pages based on structural information and can also compute ranks of instructions that represent the structural information of the instructions in malware analysis methods. Our malware categorization method uses the computed ranks as features in machine learning algorithms. In the evaluation, we compare the effectiveness of different PageRank algorithms and also investigate bagging and boosting algorithms to improve the categorization accuracy.
Approximating the Maximum Number of Synchronizing States in Automata
Venue: arXiv cs.FL 2016
Year: 2016

We consider the problem {\sc Max Sync Set} of finding a maximum synchronizing set of states in a given automaton. We show that the decision version of this problem is PSPACE-complete and investigate the approximability of {\sc Max Sync Set} for binary and weakly acyclic automata (an automaton is called weakly acyclic if it contains no cycles other than self-loops). We prove that, assuming $P \ne NP$, for any $\varepsilon > 0$, the {\sc Max Sync Set} problem cannot be approximated in polynomial time within a factor of $O(n^{1 - \varepsilon})$ for weakly acyclic $n$-state automata with alphabet of linear size, within a factor of $O(n^{\frac{1}{2} - \varepsilon})$ for binary $n$-state automata, and within a factor of $O(n^{\frac{1}{3} - \varepsilon})$ for binary weakly acyclic $n$-state automata. Finally, we prove that for unary automata the problem becomes solvable in polynomial time.
Knowledge Distillation for Small-footprint Highway Networks
Venue: arXiv cs.CL 2016
Year: 2016

Deep learning has significantly advanced state-of-the-art of speech recognition in the past few years. However, compared to conventional Gaussian mixture acoustic models, neural network models are usually much larger, and are therefore not very deployable in embedded devices. Previously, we investigated a compact highway deep neural network (HDNN) for acoustic modelling, which is a type of depth-gated feedforward neural network. We have shown that HDNN-based acoustic models can achieve comparable recognition accuracy with much smaller number of model parameters compared to plain deep neural network (DNN) acoustic models. In this paper, we push the boundary further by leveraging on the knowledge distillation technique that is also known as {\it teacher-student} training, i.e., we train the compact HDNN model with the supervision of a high accuracy cumbersome model. Furthermore, we also investigate sequence training and adaptation in the context of teacher-student training. Our experiments were performed on the AMI meeting speech recognition corpus. With this technique, we significantly improved the recognition accuracy of the HDNN acoustic model with less than 0.8 million parameters, and narrowed the gap between this model and the plain DNN with 30 million parameters.
Media Query Processing For The Internet-of-Things: Coupling Of Device Energy Consumption And Cloud Infrastructure Billing
Venue: arXiv cs.MM 2016
Year: 2016

Audio/visual recognition and retrieval applications have recently garnered significant attention within Internet-of-Things (IoT) oriented services, given that video cameras and audio processing chipsets are now ubiquitous even in low-end embedded systems. In the most typical scenario for such services, each device extracts audio/visual features and compacts them into feature descriptors, which comprise media queries. These queries are uploaded to a remote cloud computing service that performs content matching for classification or retrieval applications. Two of the most crucial aspects for such services are: (i) controlling the device energy consumption when using the service; (ii) reducing the billing cost incurred from the cloud infrastructure provider. In this paper we derive analytic conditions for the optimal coupling between the device energy consumption and the incurred cloud infrastructure billing. Our framework encapsulates: the energy consumption to produce and transmit audio/visual queries, the billing rates of the cloud infrastructure, the number of devices concurrently connected to the same cloud server, {the query volume constraint of each cluster of devices,} and the statistics of the query data production volume per device. Our analytic results are validated via a deployment with: (i) the device side comprising compact image descriptors (queries) computed on Beaglebone Linux embedded platforms and transmitted to Amazon Web Services (AWS) Simple Storage Service; (ii) the cloud side carrying out image similarity detection via AWS Elastic Compute Cloud (EC2) instances, with the AWS Auto Scaling being used to control the number of instances according to the demand.
A Unified Paradigm of Organized Complexity and Semantic Information Theory
Venue: arXiv cs.IT 2016
Year: 2016

One of the most fundamental problems in science is to define {\it quantitatively} the complexity of organized matters, i.e., {\it organized complexity}. Although many measures have been proposed toward this aim in previous decades, there is no agreed upon definition. This paper presents a new quantitative definition of organized complexity. This definition {\it simultaneously} captures the three major features of complexity: computational (similar to logical depth), descriptional (similar to the Kolmogorov complexity and effective complexity) and distributional (similar to statistical complexity). In addition, the proposed definition is computable and can measure both probabilistic and deterministic forms of objects in a unified manner. The proposed definition is based on circuits rather than Turing machines and $ε$-machines. We give several criteria required for organized complexity measures and show that the proposed definition satisfies all of them for the first time. We then apply this quantitative definition to formulate a {\it semantic information theory}. We present the first formal definition of a {\it semantic information amount}, which is the core concept of the semantic information theory, that is based only on concretely defined notions. Previous semantic information theories defined this amount under some a priori information which is not concretely specified. We then unveil several fundamental properties in the semantic information theory, e.g., a semantic source coding theorem, semantic channel coding theorem, and effectiveness coding theorem. Although the semantic information theory has a long history of research going back more than six decades, there has been no study on its relation to organized complexity. This paper offers the first unified paradigm of organized complexity and semantic information theory.
Automated X-ray Image Analysis for Cargo Security: Critical Review and Future Promise
Venue: arXiv cs.CV 2016
Year: 2016

We review the relatively immature field of automated image analysis for X-ray cargo imagery. There is increasing demand for automated analysis methods that can assist in the inspection and selection of containers, due to the ever-growing volumes of traded cargo and the increasing concerns that customs- and security-related threats are being smuggled across borders by organised crime and terrorist networks. We split the field into the classical pipeline of image preprocessing and image understanding. Preprocessing includes: image manipulation; quality improvement; Threat Image Projection (TIP); and material discrimination and segmentation. Image understanding includes: Automated Threat Detection (ATD); and Automated Contents Verification (ACV). We identify several gaps in the literature that need to be addressed and propose ideas for future research. Where the current literature is sparse we borrow from the single-view, multi-view, and CT X-ray baggage domains, which have some characteristics in common with X-ray cargo.
The Entity Registry System. From concept to deployment
Venue: arXiv cs.DC 2016
Year: 2016

The entity registry system (ERS) is a decentralized entity registry that can be used to replace the Web as a platform for publishing linked data when the latter is not available. In developing countries, where off-line is the default mode of operation, centralized linked data solutions fail to address the needs of the communities. Although the features are mostly completed, the system is not yet ready for deployment. This project aims to provide extensive tests and scalability investigations that would make it ready for a real scenario.
Fast and Lean Immutable Multi-Maps on the JVM based on Heterogeneous Hash-Array Mapped Tries
Venue: arXiv cs.DS 2016
Year: 2016

An immutable multi-map is a many-to-many thread-friendly map data structure with expected fast insert and lookup operations. This data structure is used for applications processing graphs or many-to-many relations as applied in static analysis of object-oriented systems. When processing such big data sets the memory overhead of the data structure encoding itself is a memory usage bottleneck. Motivated by reuse and type-safety, libraries for Java, Scala and Clojure typically implement immutable multi-maps by nesting sets as the values with the keys of a trie map. Like this, based on our measurements the expected byte overhead for a sparse multi-map per stored entry adds up to around 65B, which renders it unfeasible to compute with effectively on the JVM. In this paper we propose a general framework for Hash-Array Mapped Tries on the JVM which can store type-heterogeneous keys and values: a Heterogeneous Hash-Array Mapped Trie (HHAMT). Among other applications, this allows for a highly efficient multi-map encoding by (a) not reserving space for empty value sets and (b) inlining the values of singleton sets while maintaining a (c) type-safe API. We detail the necessary encoding and optimizations to mitigate the overhead of storing and retrieving heterogeneous data in a hash-trie. Furthermore, we evaluate HHAMT specifically for the application to multi-maps, comparing them to state-of-the-art encodings of multi-maps in Java, Scala and Clojure. We isolate key differences using microbenchmarks and validate the resulting conclusions on a real world case in static analysis. The new encoding brings the per key-value storage overhead down to 30B: a 2x improvement. With additional inlining of primitive values it reaches a 4x improvement.
Competing spreading processes and immunization in multiplex networks
Venue: arXiv cs.SI 2016
Year: 2016

Epidemic spreading on physical contact network will naturally introduce the human awareness information diffusion on virtual contact network, and the awareness diffusion will in turn depress the epidemic spreading, thus forming the competing spreading processes of epidemic and awareness in a multiplex networks. In this paper, we study the competing dynamics of epidemic and awareness, both of which follow the SIR process, in a two-layer networks based on microscopic Markov chain approach and numerical simulations. We find that strong capacities of awareness diffusion and self-protection of individuals could lead to a much higher epidemic threshold and a smaller outbreak size. However, the self-awareness of individuals has no obvious effect on the epidemic threshold and outbreak size. In addition, the immunization of the physical contact network under the interplay between of epidemic and awareness spreading is also investigated. The targeted immunization is found performs much better than random immunization, and the awareness diffusion could reduce the immunization threshold for both type of random and targeted immunization significantly.
Training Deep Networks for Facial Expression Recognition with Crowd-Sourced Label Distribution
Venue: arXiv cs.CV 2016
Year: 2016

Crowd sourcing has become a widely adopted scheme to collect ground truth labels. However, it is a well-known problem that these labels can be very noisy. In this paper, we demonstrate how to learn a deep convolutional neural network (DCNN) from noisy labels, using facial expression recognition as an example. More specifically, we have 10 taggers to label each input image, and compare four different approaches to utilizing the multiple labels: majority voting, multi-label learning, probabilistic label drawing, and cross-entropy loss. We show that the traditional majority voting scheme does not perform as well as the last two approaches that fully leverage the label distribution. An enhanced FER+ data set with multiple labels for each face image will also be shared with the research community.
Challenges in video based object detection in maritime scenario using computer vision
Venue: arXiv cs.CV 2016
Year: 2016

This paper discusses the technical challenges in maritime image processing and machine vision problems for video streams generated by cameras. Even well documented problems of horizon detection and registration of frames in a video are very challenging in maritime scenarios. More advanced problems of background subtraction and object detection in video streams are very challenging. Challenges arising from the dynamic nature of the background, unavailability of static cues, presence of small objects at distant backgrounds, illumination effects, all contribute to the challenges as discussed here.
Efficient Optimal Control of Smoke using Spacetime Multigrid
Venue: arXiv cs.GR 2016
Year: 2016

We present a novel algorithm to control the physically-based animation of smoke. Given a set of keyframe smoke shapes, we compute a dense sequence of control force fields that can drive the smoke shape to match several keyframes at certain time instances. Our approach formulates this control problem as a PDE constrained spacetime optimization and computes locally optimal control forces as the stationary point of the Karush-Kuhn-Tucker conditions. In order to reduce the high complexity of multiple passes of fluid resimulation, we utilize the coherence between consecutive fluid simulation passes and update our solution using a novel spacetime full approximation scheme (STFAS). We demonstrate the benefits of our approach by computing accurate solutions on 2D and 3D benchmarks. In practice, we observe more than an order of magnitude improvement over prior methods.
Performance Analysis of Small Cells' Deployment under Imperfect Traffic Hotspot Localization
Venue: arXiv cs.NI 2016
Year: 2016

Heterogeneous Networks (HetNets), long been considered in operators' roadmaps for macrocells' network improvements, still continue to attract interest for 5G network deployments. Understanding the efficiency of small cell deployment in the presence of traffic hotspots can further draw operators' attention to this feature. In this context, we evaluate the impact of imperfect small cell positioning on the network performances. We show that the latter is mainly impacted by the position of the hotspot within the cell: in case the hotspot is near the macrocell, even a perfect positioning of the small cell will not yield improved performance due to the interference coming from the macrocell. In the case where the hotspot is located far enough from the macrocell, even a large error in small cell positioning would still be beneficial in offloading traffic from the congested macrocell.
Autonomous Grounding of Visual Field Experience through Sensorimotor Prediction
Venue: arXiv cs.RO 2016
Year: 2016

In a developmental framework, autonomous robots need to explore the world and learn how to interact with it. Without an a priori model of the system, this opens the challenging problem of having robots master their interface with the world: how to perceive their environment using their sensors, and how to act in it using their motors. The sensorimotor approach of perception claims that a naive agent can learn to master this interface by capturing regularities in the way its actions transform its sensory inputs. In this paper, we apply such an approach to the discovery and mastery of the visual field associated with a visual sensor. A computational model is formalized and applied to a simulated system to illustrate the approach.
Improving Quality of Hierarchical Clustering for Large Data Series
Venue: arXiv cs.CL 2016
Year: 2016

Brown clustering is a hard, hierarchical, bottom-up clustering of words in a vocabulary. Words are assigned to clusters based on their usage pattern in a given corpus. The resulting clusters and hierarchical structure can be used in constructing class-based language models and for generating features to be used in NLP tasks. Because of its high computational cost, the most-used version of Brown clustering is a greedy algorithm that uses a window to restrict its search space. Like other clustering algorithms, Brown clustering finds a sub-optimal, but nonetheless effective, mapping of words to clusters. Because of its ability to produce high-quality, human-understandable cluster, Brown clustering has seen high uptake the NLP research community where it is used in the preprocessing and feature generation steps. Little research has been done towards improving the quality of Brown clusters, despite the greedy and heuristic nature of the algorithm. The approaches tried so far have focused on: studying the effect of the initialisation in a similar algorithm; tuning the parameters used to define the desired number of clusters and the behaviour of the algorithm; and including a separate parameter to differentiate the window from the desired number of clusters. However, some of these approaches have not yielded significant improvements in cluster quality. In this thesis, a close analysis of the Brown algorithm is provided, revealing important under-specifications and weaknesses in the original algorithm. These have serious effects on cluster quality and reproducibility of research using Brown clustering. In the second part of the thesis, two modifications are proposed. Finally, a thorough evaluation is performed, considering both the optimization criterion of Brown clustering and the performance of the resulting class-based language models.
Detailed Garment Recovery from a Single-View Image
Venue: arXiv cs.CV 2016
Year: 2016

Most recent garment capturing techniques rely on acquiring multiple views of clothing, which may not always be readily available, especially in the case of pre-existing photographs from the web. As an alternative, we pro- pose a method that is able to compute a rich and realistic 3D model of a human body and its outfits from a single photograph with little human in- teraction. Our algorithm is not only able to capture the global shape and geometry of the clothing, it can also extract small but important details of cloth, such as occluded wrinkles and folds. Unlike previous methods using full 3D information (i.e. depth, multi-view images, or sampled 3D geom- etry), our approach achieves detailed garment recovery from a single-view image by using statistical, geometric, and physical priors and a combina- tion of parameter estimation, semantic parsing, shape recovery, and physics- based cloth simulation. We demonstrate the effectiveness of our algorithm by re-purposing the reconstructed garments for virtual try-on and garment transfer applications, as well as cloth animation for digital characters.