OpenRaiser/Intern-Atlas huggingface dataset:
Hashing in the Zero Shot Framework with Domain Adaptation
Venue: arXiv cs.CV 2017
Year: 2017

Techniques to learn hash codes which can store and retrieve large dimensional multimedia data efficiently have attracted broad research interests in the recent years. With rapid explosion of newly emerged concepts and online data, existing supervised hashing algorithms suffer from the problem of scarcity of ground truth annotations due to the high cost of obtaining manual annotations. Therefore, we propose an algorithm to learn a hash function from training images belonging to `seen' classes which can efficiently encode images of `unseen' classes to binary codes. Specifically, we project the image features from visual space and semantic features from semantic space into a common Hamming subspace. Earlier works to generate hash codes have tried to relax the discrete constraints on hash codes and solve the continuous optimization problem. However, it often leads to quantization errors. In this work, we use the max-margin classifier to learn an efficient hash function. To address the concern of domain-shift which may arise due to the introduction of new classes, we also introduce an unsupervised domain adaptation model in the proposed hashing framework. Results on the three datasets show the advantage of using domain adaptation in learning a high-quality hash function and superiority of our method for the task of image retrieval performance as compared to several state-of-the-art hashing methods.
A short proof of correctness of the quasi-polynomial time algorithm for parity games
Venue: arXiv cs.FL 2017
Year: 2017

Recently Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan proposed a quasi-polynomial time algorithm for parity games. This paper proposes a short proof of correctness of their algorithm.
A Region Based Easy Path Wavelet Transform For Sparse Image Representation
Venue: arXiv cs.IT 2017
Year: 2017

The Easy Path Wavelet Transform is an adaptive transform for bivariate functions (in particular natural images) which has been proposed in [1]. It provides a sparse representation by finding a path in the domain of the function leveraging the local correlations of the function values. It then applies a one dimensional wavelet transform to the obtained vector, decimates the points and iterates the procedure. The main drawback of such method is the need to store, for each level of the transform, the path which vectorizes the two dimensional data. Here we propose a variation on the method which consists of firstly applying a segmentation procedure to the function domain, partitioning it into regions where the variation in the function values is low; in a second step, inside each such region, a path is found in some deterministic way, i.e. not data-dependent. This circumvents the need to store the paths at each level, while still obtaining good quality lossy compression. This method is particularly well suited to encode a Region of Interest in the image with different quality than the rest of the image. [1] Gerlind Plonka. The easy path wavelet transform: A new adaptive wavelet transform for sparse representation of two-dimensional data. Multiscale Modeling & Simulation, 7(3):1474$-$1496, 2008.
Identification of Voice Utterance with Aging Factor Using the Method of MFCC Multichannel
Venue: arXiv cs.SD 2017
Year: 2017

This research was conducted to develop a method to identify voice utterance. For voice utterance that encounters change caused by aging factor, with the interval of 10 to 25 years. The change of voice utterance influenced by aging factor might be extracted by MFCC (Mel Frequency Cepstrum Coefficient). However, the level of the compatibility of the feature may be dropped down to 55%. While the ones which do not encounter it may reach 95%. To improve the compatibility of the changing voice feature influenced by aging factor, then the method of the more specific feature extraction is developed: which is by separating the voice into several channels, suggested as MFCC multichannel, consisting of multichannel 5 filterbank (M5FB), multichannel 2 filterbank (M2FB) and multichannel 1 filterbank (M1FB). The result of the test shows that for model M5FB and M2FB have the highest score in the level of compatibility with 85% and 82% with 25 years interval. While model M5FB gets the highest score of 86% for 10 years time interval.
Empirical Risk Minimization for Stochastic Convex Optimization: $O(1/n)$- and $O(1/n^2)$-type of Risk Bounds
Venue: arXiv cs.LG 2017
Year: 2017

Although there exist plentiful theories of empirical risk minimization (ERM) for supervised learning, current theoretical understandings of ERM for a related problem---stochastic convex optimization (SCO), are limited. In this work, we strengthen the realm of ERM for SCO by exploiting smoothness and strong convexity conditions to improve the risk bounds. First, we establish an $\widetilde{O}(d/n + \sqrt{F_*/n})$ risk bound when the random function is nonnegative, convex and smooth, and the expected function is Lipschitz continuous, where $d$ is the dimensionality of the problem, $n$ is the number of samples, and $F_*$ is the minimal risk. Thus, when $F_*$ is small we obtain an $\widetilde{O}(d/n)$ risk bound, which is analogous to the $\widetilde{O}(1/n)$ optimistic rate of ERM for supervised learning. Second, if the objective function is also $λ$-strongly convex, we prove an $\widetilde{O}(d/n + κF_*/n )$ risk bound where $κ$ is the condition number, and improve it to $O(1/[λn^2] + κF_*/n)$ when $n=\widetildeΩ(κd)$. As a result, we obtain an $O(κ/n^2)$ risk bound under the condition that $n$ is large and $F_*$ is small, which to the best of our knowledge, is the first $O(1/n^2)$-type of risk bound of ERM. Third, we stress that the above results are established in a unified framework, which allows us to derive new risk bounds under weaker conditions, e.g., without convexity of the random function and Lipschitz continuity of the expected function. Finally, we demonstrate that to achieve an $O(1/[λn^2] + κF_*/n)$ risk bound for supervised learning, the $\widetildeΩ(κd)$ requirement on $n$ can be replaced with $Ω(κ^2)$, which is dimensionality-independent.
Rapid parametric density estimation
Venue: arXiv cs.LG 2017
Year: 2017

Parametric density estimation, for example as Gaussian distribution, is the base of the field of statistics. Machine learning requires inexpensive estimation of much more complex densities, and the basic approach is relatively costly maximum likelihood estimation (MLE). There will be discussed inexpensive density estimation, for example literally fitting a polynomial (or Fourier series) to the sample, which coefficients are calculated by just averaging monomials (or sine/cosine) over the sample. Another discussed basic application is fitting distortion to some standard distribution like Gaussian - analogously to ICA, but additionally allowing to reconstruct the disturbed density. Finally, by using weighted average, it can be also applied for estimation of non-probabilistic densities, like modelling mass distribution, or for various clustering problems by using negative (or complex) weights: fitting a function which sign (or argument) determines clusters. The estimated parameters are approaching the optimal values with error dropping like $1/\sqrt{n}$, where $n$ is the sample size.
Fixing the Infix: Unsupervised Discovery of Root-and-Pattern Morphology
Venue: arXiv cs.CL 2017
Year: 2017

We present an unsupervised and language-agnostic method for learning root-and-pattern morphology in Semitic languages. This form of morphology, abundant in Semitic languages, has not been handled in prior unsupervised approaches. We harness the syntactico-semantic information in distributed word representations to solve the long standing problem of root-and-pattern discovery in Semitic languages. Moreover, we construct an unsupervised root extractor based on the learned rules. We prove the validity of learned rules across Arabic, Hebrew, and Amharic, alongside showing that our root extractor compares favorably with a widely used, carefully engineered root extractor: ISRI.
Automated Low-cost Terrestrial Laser Scanner for Measuring Diameters at Breast Height and Heights of Forest Trees
Venue: arXiv cs.CV 2017
Year: 2017

Terrestrial laser scanner is a kind of fast, high-precision data acquisition device, which had been more and more applied to the research areas of forest inventory. In this study, a kind of automated low-cost terrestrial laser scanner was designed and implemented based on a two-dimensional laser radar sensor SICK LMS-511 and a stepper motor. The new scanner was named as BEE, which can scan the forest trees in three dimension. The BEE scanner and its supporting software are specifically designed for forest inventory. The experiments have been performed by using the BEE scanner in an artificial ginkgo forest which was located in Haidian district of Beijing. Four square plots were selected to do the experiments. The BEE scanner scanned in the four plots and acquired the single scan data respectively. The DBH, tree height and tree position of trees in the four plots were estimated and analyzed. For comparison, the manual measured data was also collected in the four plots. The tree stem detection rate for all four plots was 92.75%; the root mean square error of the DBH estimation was 1.27cm; the root mean square error of the tree height estimation was 0.24m; the tree position estimation was in line with the actual position. Experimental results show that the BEE scanner can efficiently estimate the structure parameters of forest trees and has a good potential in practical application of forest inventory.
A novel type of Automata for dynamic, heterogeneous and random architectures
Venue: arXiv cs.FL 2017
Year: 2017

In this paper, the author aims to establish a mathematical model for a mimic computer. To this end, a novel automaton is proposed. First, a one-dimensional cellular automaton is used for expressing some dynamic changes in the structure of a computing unit, a sequential automaton is employed to describe some state transitions, a hierarchical automaton is employed to express the different granularities of some computing units, and a probabilistic automaton is used to depict some random changes of a computing unit. Second, the new automaton is obtained by combining the various types of automata mentioned above in the certain logical relationship. To the best of our knowledge, the new automaton model is the first automaton which can portray the operation semantics for a mimic computing system, and it can directly describe some behaviors of a mimic computer.
Characterisation of Approximation and (Head) Normalisation for $λμ$ using Strict Intersection Types
Venue: arXiv cs.LO 2017
Year: 2017

We study the strict type assignment for lambda-mu that is presented in [van Bakel'16]. We define a notion of approximants of lambda-mu-terms, show that it generates a semantics, and that for each typeable term there is an approximant that has the same type. We show that this leads to a characterisation via assignable types for all terms that have a head normal form, and to one for all terms that have a normal form, as well as to one for all terms that are strongly normalisable.
Autonomous Braking System via Deep Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, we propose a new autonomous braking system based on deep reinforcement learning. The proposed autonomous braking system automatically decides whether to apply the brake at each time step when confronting the risk of collision using the information on the obstacle obtained by the sensors. The problem of designing brake control is formulated as searching for the optimal policy in Markov decision process (MDP) model where the state is given by the relative position of the obstacle and the vehicle's speed, and the action space is defined as whether brake is stepped or not. The policy used for brake control is learned through computer simulations using the deep reinforcement learning method called deep Q-network (DQN). In order to derive desirable braking policy, we propose the reward function which balances the damage imposed to the obstacle in case of accident and the reward achieved when the vehicle runs out of risk as soon as possible. DQN is trained for the scenario where a vehicle is encountered with a pedestrian crossing the urban road. Experiments show that the control agent exhibits desirable control behavior and avoids collision without any mistake in various uncertain environments.
FASHION: Fault-Aware Self-Healing Intelligent On-chip Network
Venue: arXiv cs.AR 2017
Year: 2017

To avoid packet loss and deadlock scenarios that arise due to faults or power gating in multicore and many-core systems, the network-on-chip needs to possess resilient communication and load-balancing properties. In this work, we introduce the Fashion router, a self-monitoring and self-reconfiguring design that allows for the on-chip network to dynamically adapt to component failures. First, we introduce a distributed intelligence unit, called Self-Awareness Module (SAM), which allows the router to detect permanent component failures and build a network connectivity map. Using local information, SAM adapts to faults, guarantees connectivity and deadlock-free routing inside the maximal connected subgraph and keeps routing tables up-to-date. Next, to reconfigure network links or virtual channels around faulty/power-gated components, we add bidirectional link and unified virtual channel structure features to the Fashion router. This version of the router, named Ex-Fashion, further mitigates the negative system performance impacts, leads to larger maximal connected subgraph and sustains a relatively high degree of fault-tolerance. To support the router, we develop a fault diagnosis and recovery algorithm executed by the Built-In Self-Test, self-monitoring, and self-reconfiguration units at runtime to provide fault-tolerant system functionalities. The Fashion router places no restriction on topology, position or number of faults. It drops 54.3-55.4% fewer nodes for same number of faults (between 30 and 60 faults) in an 8x8 2D-mesh over other state-of-the-art solutions. It is scalable and efficient. The area overheads are 2.311% and 2.659% when implemented in 8x8 and 16x16 2D-meshes using the TSMC 65nm library at 1.38GHz clock frequency.
Position Heaps for Parameterized Strings
Venue: arXiv cs.DS 2017
Year: 2017

We propose a new indexing structure for parameterized strings, called parameterized position heap. Parameterized position heap is applicable for parameterized pattern matching problem, where the pattern matches a substring of the text if there exists a bijective mapping from the symbols of the pattern to the symbols of the substring. We propose an online construction algorithm of parameterized position heap of a text and show that our algorithm runs in linear time with respect to the text size. We also show that by using parameterized position heap, we can find all occurrences of a pattern in the text in linear time with respect to the product of the pattern size and the alphabet size.
Relaxing constraints in stateful network data plane design
Venue: arXiv cs.NI 2017
Year: 2017

Supporting programmable states in the data plane of a forwarding element, e.g., a switch or a NIC, has recently attracted the interest of the research community, which is now looking for the right abstraction to enable the programming of stateful network functions in hardware at line rate. We challenge the conservative assumptions of state-of-the-art abstractions in this field, e.g. always assuming minimum size packets arriving back-to-back. Using trace-based simulations we show that by making more realistic assumptions on the traffic characteristics, e.g. larger average packet size, we can relax the design constraints that currently limit the set of functions that can be implemented at line rate, allowing for more complex functions, with no harm for performance.
Multi-scale Convolutional Neural Networks for Crowd Counting
Venue: arXiv cs.CV 2017
Year: 2017

Crowd counting on static images is a challenging problem due to scale variations. Recently deep neural networks have been shown to be effective in this task. However, existing neural-networks-based methods often use the multi-column or multi-network model to extract the scale-relevant features, which is more complicated for optimization and computation wasting. To this end, we propose a novel multi-scale convolutional neural network (MSCNN) for single image crowd counting. Based on the multi-scale blobs, the network is able to generate scale-relevant features for higher crowd counting performances in a single-column architecture, which is both accuracy and cost effective for practical applications. Complemental results show that our method outperforms the state-of-the-art methods on both accuracy and robustness with far less number of parameters.
On the Spectral Efficiency of Blind Channel Estimation and Synchronization Techniques
Venue: arXiv cs.IT 2017
Year: 2017

In the literature, channel estimation and synchronization (CE/SY) algorithms are classified as blind, and hence spectrally efficient, if they do not require pilot symbols. However, we show in this letter that such classification is not accurate and can be misleading. Consequently, this letter presents a more reliable and accurate approach to evaluate the spectral efficiency of communications systems with various CE/SY algorithms. The proposed approach allows fair spectral efficiency comparison between various systems with blind or non-blind CE/SY algorithms. In particular, we evaluate the spectral efficiency of communications systems that incorporates blind CE/SY algorithms and compare it to other blind and pilot-based algorithms. The obtained results reveal that, on the contrary to what is widely accepted, blind CE/SY algorithms with modulation-type constrain do not necessarily improve the spectral efficiency as compared to pilot-based techniques. Consequently, such techniques are classified as conditionally blind, to distinguish them from fully blind techniques.
SEA: String Executability Analysis by Abstract Interpretation
Venue: arXiv cs.PL 2017
Year: 2017

Dynamic languages often employ reflection primitives to turn dynamically generated text into executable code at run-time. These features make standard static analysis extremely hard if not impossible because its essential data structures, i.e., the control-flow graph and the system of recursive equations associated with the program to analyse, are themselves dynamically mutating objects. We introduce SEA, an abstract interpreter for automatic sound string executability analysis of dynamic languages employing bounded (i.e, finitely nested) reflection and dynamic code generation. Strings are statically approximated in an abstract domain of finite state automata with basic operations implemented as symbolic transducers. SEA combines standard program analysis together with string executability analysis. The analysis of a call to reflection determines a call to the same abstract interpreter over a code which is synthesised directly from the result of the static string executability analysis at that program point. The use of regular languages for approximating dynamically generated code structures allows SEA to soundly approximate safety properties of self modifying programs yet maintaining efficiency. Soundness here means that the semantics of the code synthesised by the analyser to resolve reflection over-approximates the semantics of the code dynamically built at run-rime by the program at that point.
Data Selection Strategies for Multi-Domain Sentiment Analysis
Venue: arXiv cs.CL 2017
Year: 2017

Domain adaptation is important in sentiment analysis as sentiment-indicating words vary between domains. Recently, multi-domain adaptation has become more pervasive, but existing approaches train on all available source domains including dissimilar ones. However, the selection of appropriate training data is as important as the choice of algorithm. We undertake -- to our knowledge for the first time -- an extensive study of domain similarity metrics in the context of sentiment analysis and propose novel representations, metrics, and a new scope for data selection. We evaluate the proposed methods on two large-scale multi-domain adaptation settings on tweets and reviews and demonstrate that they consistently outperform strong random and balanced baselines, while our proposed selection strategy outperforms instance-level selection and yields the best score on a large reviews corpus.
Integrated Information as a Metric for Group Interaction: Analyzing Human and Computer Groups Using a Technique Developed to Measure Consciousness
Venue: arXiv cs.SI 2017
Year: 2017

Researchers in many disciplines have previously used a variety of mathematical techniques for analyzing group interactions. Here we use a new metric for this purpose, called 'integrated information' or 'phi.' Phi was originally developed by neuroscientists as a measure of consciousness in brains, but it captures, in a single mathematical quantity, two properties that are important in many other kinds of groups as well: differentiated information and integration. Here we apply this metric to the activity of three types of groups that involve people and computers. First, we find that 4-person work groups with higher measured phi perform a wide range of tasks more effectively, as measured by their collective intelligence. Next, we find that groups of Wikipedia editors with higher measured phi create higher quality articles. Last, we find that the measured phi of the collection of people and computers communicating on the Internet increased over a recent six-year period. Together, these results suggest that integrated information can be a useful way of characterizing a certain kind of interactional complexity that, at least sometimes, predicts group performance. In this sense, phi can be viewed as a potential metric of effective group collaboration. Since the metric was originally developed as a measure of consciousness, the results also raise intriguing questions about the conditions under which it might be useful to regard groups as having a kind of consciousness.
A study on implementing a multithreaded version of the SIRENE detector simulation software for high energy neutrinos
Venue: arXiv cs.DC 2017
Year: 2017

The primary objective of SIRENE is to simulate the response to neutrino events of any type of high energy neutrino telescope. Additionally, it implements different geometries for a neutrino detector and different configurations and characteristics of photo-multiplier tubes (PMTs) inside the optical modules of the detector through a library of C+ + classes. This could be considered a massive statistical analysis of photo-electrons. Aim of this work is the development of a multithreaded version of the SIRENE detector simulation software for high energy neutrinos. This approach allows utilization of multiple CPU cores leading to a potentially significant decrease in the required execution time compared to the sequential code. We are making use of the OpenMP framework for the production of multithreaded code running on the CPU. Finally, we analyze the feasibility of a GPU-accelerated implementation.