OpenRaiser/Intern-Atlas huggingface dataset:
Be Precise or Fuzzy: Learning the Meaning of Cardinals and Quantifiers from Vision
Venue: arXiv cs.CL 2017
Year: 2017

People can refer to quantities in a visual scene by using either exact cardinals (e.g. one, two, three) or natural language quantifiers (e.g. few, most, all). In humans, these two processes underlie fairly different cognitive and neural mechanisms. Inspired by this evidence, the present study proposes two models for learning the objective meaning of cardinals and quantifiers from visual scenes containing multiple objects. We show that a model capitalizing on a 'fuzzy' measure of similarity is effective for learning quantifiers, whereas the learning of exact cardinals is better accomplished when information about number is provided.
Towards a Unified Taxonomy of Biclustering Methods
Venue: arXiv cs.AI 2017
Year: 2017

Being an unsupervised machine learning and data mining technique, biclustering and its multimodal extensions are becoming popular tools for analysing object-attribute data in different domains. Apart from conventional clustering techniques, biclustering is searching for homogeneous groups of objects while keeping their common description, e.g., in binary setting, their shared attributes. In bioinformatics, biclustering is used to find genes, which are active in a subset of situations, thus being candidates for biomarkers. However, the authors of those biclustering techniques that are popular in gene expression analysis, may overlook the existing methods. For instance, BiMax algorithm is aimed at finding biclusters, which are well-known for decades as formal concepts. Moreover, even if bioinformatics classify the biclustering methods according to reasonable domain-driven criteria, their classification taxonomies may be different from survey to survey and not full as well. So, in this paper we propose to use concept lattices as a tool for taxonomy building (in the biclustering domain) and attribute exploration as means for cross-domain taxonomy completion.
Exact clustering in linear time
Venue: arXiv cs.DS 2017
Year: 2017

The time complexity of data clustering has been viewed as fundamentally quadratic, slowing with the number of data items, as each item is compared for similarity to preceding items. Clustering of large data sets has been infeasible without resorting to probabilistic methods or to capping the number of clusters. Here we introduce MIMOSA, a novel class of algorithms which achieve linear time computational complexity on clustering tasks. MIMOSA algorithms mark and match partial-signature keys in a hash table to obtain exact, error-free cluster retrieval. Benchmark measurements, on clustering a data set of 10,000,000 news articles by news topic, found that a MIMOSA implementation finished more than four orders of magnitude faster than a standard centroid implementation.
Sampling from Social Networks with Attributes
Venue: arXiv cs.SI 2017
Year: 2017

Sampling from large networks represents a fundamental challenge for social network research. In this paper, we explore the sensitivity of different sampling techniques (node sampling, edge sampling, random walk sampling, and snowball sampling) on social networks with attributes. We consider the special case of networks (i) where we have one attribute with two values (e.g., male and female in the case of gender), (ii) where the size of the two groups is unequal (e.g., a male majority and a female minority), and (iii) where nodes with the same or different attribute value attract or repel each other (i.e., homophilic or heterophilic behavior). We evaluate the different sampling techniques with respect to conserving the position of nodes and the visibility of groups in such networks. Experiments are conducted both on synthetic and empirical social networks. Our results provide evidence that different network sampling techniques are highly sensitive with regard to capturing the expected centrality of nodes, and that their accuracy depends on relative group size differences and on the level of homophily that can be observed in the network. We conclude that uninformed sampling from social networks with attributes thus can significantly impair the ability of researchers to draw valid conclusions about the centrality of nodes and the visibility or invisibility of groups in social networks.
Quantifying Program Bias
Venue: arXiv cs.PL 2017
Year: 2017

With the range and sensitivity of algorithmic decisions expanding at a break-neck speed, it is imperative that we aggressively investigate whether programs are biased. We propose a novel probabilistic program analysis technique and apply it to quantifying bias in decision-making programs. Specifically, we (i) present a sound and complete automated verification technique for proving quantitative properties of probabilistic programs; (ii) show that certain notions of bias, recently proposed in the fairness literature, can be phrased as quantitative correctness properties; and (iii) present FairSquare, the first verification tool for quantifying program bias, and evaluate it on a range of decision-making programs.
Communication Reducing Algorithms for Distributed Hierarchical N-Body Problems with Boundary Distributions
Venue: arXiv cs.DC 2017
Year: 2017

Reduction of communication and efficient partitioning are key issues for achieving scalability in hierarchical $N$-Body algorithms like FMM. In the present work, we propose four independent strategies to improve partitioning and reduce communication. First of all, we show that the conventional wisdom of using space-filling curve partitioning may not work well for boundary integral problems, which constitute about 50% of FMM's application user base. We propose an alternative method which modifies orthogonal recursive bisection to solve the cell-partition misalignment that has kept it from scaling previously. Secondly, we optimize the granularity of communication to find the optimal balance between a bulk-synchronous collective communication of the local essential tree and an RDMA per task per cell. Finally, we take the dynamic sparse data exchange proposed by Hoefler et al. and extend it to a hierarchical sparse data exchange, which is demonstrated at scale to be faster than the MPI library's MPI_Alltoallv that is commonly used.
A Performance Analysis of Simple Runtime System for Actor Programming in C++
Venue: arXiv cs.PL 2017
Year: 2017

In this paper, we propose the Templet -- a runtime system for actor programming of high performance computing in C++. We provide a compact source code of the runtime system, which uses standard library of C++11 only. We demonstrate how it differs from the classic implementations of the actor model. The practical significance of the Templet was examined by comparative study on the performance of three applications: the reference code in C++, managed by the OpenMP; the actor code in C++, managed by the Templet; the actor code in Java, managed by the Akka. As a test problem we used a numerical algorithm for solving the heat equation.
Analysis and Optimization of fastText Linear Text Classifier
Venue: arXiv cs.CL 2017
Year: 2017

The paper [1] shows that simple linear classifier can compete with complex deep learning algorithms in text classification applications. Combining bag of words (BoW) and linear classification techniques, fastText [1] attains same or only slightly lower accuracy than deep learning algorithms [2-9] that are orders of magnitude slower. We proved formally that fastText can be transformed into a simpler equivalent classifier, which unlike fastText does not have any hidden layer. We also proved that the necessary and sufficient dimensionality of the word vector embedding space is exactly the number of document classes. These results help constructing more optimal linear text classifiers with guaranteed maximum classification capabilities. The results are proven exactly by pure formal algebraic methods without attracting any empirical data.
On the Necessity of Structured Codes for Communications over MAC with Feedback
Venue: arXiv cs.IT 2017
Year: 2017

The problem of three-user multiple-access channel (MAC) with noiseless feedback is investigated. A new coding strategy is presented. The coding scheme builds upon the natural extension of the Cover-Leung (CL) scheme; and uses quasi-linear codes. A new single-letter achievable rate region is derived. The new achievable region strictly contains the CL region. This is shown through an example. In this example, the coding scheme achieves optimality in terms of transmission rates. It is shown that any optimality achieving scheme for this example must have a specific algebraic structure. Particularly, the codebooks must be closed under binary addition.
Nontrivial Turmites are Turing-universal
Venue: arXiv cs.CC 2017
Year: 2017

A Turmit is a Turing machine that works over a two-dimensional grid, that is, an agent that moves, reads and writes symbols over the cells of the grid. Its state is an arrow and, depending on the symbol that it reads, it turns to the left or to the right, switching the symbol at the same time. Several symbols are admitted, and the rule is specified by the turning sense that the machine has over each symbol. Turmites are a generalization of Langtons ant, and they present very complex and diverse behaviors. We prove that any Turmite, except for those whose rule does not depend on the symbol, can simulate any Turing Machine. We also prove the P-completeness of prediction their future behavior by explicitly giving a log-space reduction from the Topological Circuit Value Problem. A similar result was already established for Langtons ant; here we use a similar technique but prove a stronger notion of simulation, and for a more general family.
Defect detection for patterned fabric images based on GHOG and low-rank decomposition
Venue: arXiv cs.CV 2017
Year: 2017

In order to accurately detect defects in patterned fabric images, a novel detection algorithm based on Gabor-HOG (GHOG) and low-rank decomposition is proposed in this paper. Defect-free pattern fabric images have the specified direction, while defects damage their regularity of direction. Therefore, a direction-aware descriptor is designed, denoted as GHOG, a combination of Gabor and HOG, which is extremely valuable for localizing the defect region. Upon devising a powerful directional descriptor, an efficient low-rank decomposition model is constructed to divide the matrix generated by the directional feature extracted from image blocks into a low-rank matrix (background information) and a sparse matrix (defect information). A nonconvex log det(.) as a smooth surrogate function for the rank instead of the nuclear norm is also exploited to improve the efficiency of the low-rank model. Moreover, the computational efficiency is further improved by utilizing the alternative direction method of multipliers (ADMM). Thereafter, the saliency map generated by the sparse matrix is segmented via the optimal threshold algorithm to locate the defect regions. Experimental results show that the proposed method can effectively detect patterned fabric defects and outperform the state-of-the-art methods.
On the Unambiguous Distance of Multi-Carrier Phase Ranging with Random Hopped Frequencie
Venue: arXiv cs.NI 2017
Year: 2017

In a multi-carrier phase ranging (MPR) system, the distance that radio signal travels is estimated through phase shift of multiple carrier frequencies. Due to phase ambiguity, a unique estimation can only be obtained within the unambiguous distance (UD), which depends on the carrier frequencies used for ranging. Without external information, the maximum measurable distance of an MPR system is defined by its UD. The MPR system employing random frequency hopping (FH) waveform has a strong anti-jamming capability and sees promising potentials in many fields. However, it is challenging to depict its measurable distance. Different from current MPR system employing deterministic frequencies, the carrier frequency under the FH waveform hops randomly within the occupied bandwidth. Consequently, the UD is a random variable. In this paper, we try to find a deterministic value to depict the UD of an MPR system under the random spaced frequencies (RSF) configuration, serving as a metric of its measurable distance in engineering applications. It is safe to adopt the lower bound of the random UD as the metric, but the measurable distance may be drastically underestimated. Alternatively, we propose to adopt the upper bound of the random UD as the metric, because when the RSF set contains more than a dozen of carriers, i) we prove the probability that the random UD obtains its upper bound is very close to 1 if phase noise is not introduced; ii) simulations show that the upper bound can also be obtained reliably in the presence of phase noise. As a comparison, the practical measurable range of the MPR system under the traditional linearly spaced frequencies (LSF) configuration is only a fraction of its theoretical UD because the UD is more sensitive to phase error.
On Loss Functions for Deep Neural Networks in Classification
Venue: arXiv cs.LG 2017
Year: 2017

Deep neural networks are currently among the most commonly used classifiers. Despite easily achieving very good performance, one of the best selling points of these models is their modular design - one can conveniently adapt their architecture to specific needs, change connectivity patterns, attach specialised layers, experiment with a large amount of activation functions, normalisation schemes and many others. While one can find impressively wide spread of various configurations of almost every aspect of the deep nets, one element is, in authors' opinion, underrepresented - while solving classification problems, vast majority of papers and applications simply use log loss. In this paper we try to investigate how particular choices of loss functions affect deep models and their learning dynamics, as well as resulting classifiers robustness to various effects. We perform experiments on classical datasets, as well as provide some additional, theoretical insights into the problem. In particular we show that L1 and L2 losses are, quite surprisingly, justified classification objectives for deep nets, by providing probabilistic interpretation in terms of expected misclassification. We also introduce two losses which are not typically used as deep nets objectives and show that they are viable alternatives to the existing ones.
Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes
Venue: arXiv cs.LG 2017
Year: 2017

In this work we study the quantitative relation between the recursive teaching dimension (RTD) and the VC dimension (VCD) of concept classes of finite sizes. The RTD of a concept class $\mathcal C \subseteq \{0, 1\}^n$, introduced by Zilles et al. (2011), is a combinatorial complexity measure characterized by the worst-case number of examples necessary to identify a concept in $\mathcal C$ according to the recursive teaching model. For any finite concept class $\mathcal C \subseteq \{0,1\}^n$ with $\mathrm{VCD}(\mathcal C)=d$, Simon & Zilles (2015) posed an open problem $\mathrm{RTD}(\mathcal C) = O(d)$, i.e., is RTD linearly upper bounded by VCD? Previously, the best known result is an exponential upper bound $\mathrm{RTD}(\mathcal C) = O(d \cdot 2^d)$, due to Chen et al. (2016). In this paper, we show a quadratic upper bound: $\mathrm{RTD}(\mathcal C) = O(d^2)$, much closer to an answer to the open problem. We also discuss the challenges in fully solving the problem.
DySign: Dynamic Fingerprinting for the Automatic Detection of Android Malware
Venue: arXiv cs.CR 2017
Year: 2017

The astonishing spread of Android OS, not only in smartphones and tablets but also in IoT devices, makes this operating system a very tempting target for malware threats. Indeed, the latter are expanding at a similar rate. In this respect, malware fingerprints, whether based on cryptographic or fuzzy-hashing, are the first defense line against such attacks. Fuzzy-hashing fingerprints are suitable for capturing malware static features. Moreover, they are more resilient to small changes in the actual static content of malware files. On the other hand, dynamic analysis is another technique for malware detection that uses emulation environments to extract behavioral features of Android malware. However, to the best of our knowledge, there is no such fingerprinting technique that leverages dynamic analysis and would act as the first defense against Android malware attacks. In this paper, we address the following question: could we generate effective fingerprints for Android malware through dynamic analysis? To this end, we propose DySign, a novel technique for fingerprinting Android malware's dynamic behaviors. This is achieved through the generation of a digest from the dynamic analysis of a malware sample on existing known malware. It is important to mention that: (i) DySign fingerprints are approximated of the observed behaviors during dynamic analysis so as to achieve resiliency to small changes in the behaviors of future malware variants; (ii) Fingerprint computation is agnostic to the analyzed malware sample or family. DySign leverages state-of-the-art Natural Language Processing (NLP) techniques to generate the aforementioned fingerprints, which are then leveraged to build an enhanced Android malware detection system with family attribution.
Adoption of free and open source software using alternative educational framework in college of applied sciences
Venue: arXiv cs.CY 2017
Year: 2017

The adoption of Free and Open Source Software (FOSS) in educational institutions is increasing day by day. Many countries are insisting the use of FOSS in their government sectors and few are in the process of adopting FOSS strategies. The reasons for adopting FOSS are: total cost ownership, free to make copies and distribution, software legality, reliability, availability, performance, security and other pedagogical and administrative benefits. In this research paper, the alternative educational framework has been used to identify the FOSS tools and software by considering the various strategic areas, polices and phased approach to identify the suitable FOSS tools for the courses of various specializations of Information Technology programme in College of Applied Sciences, Sultanate of Oman. As a result of this research, a list of alternative FOSS tools and software for the courses of IT programme has been identified and recommended.
DR2-Net: Deep Residual Reconstruction Network for Image Compressive Sensing
Venue: arXiv cs.CV 2017
Year: 2017

Most traditional algorithms for compressive sensing image reconstruction suffer from the intensive computation. Recently, deep learning-based reconstruction algorithms have been reported, which dramatically reduce the time complexity than iterative reconstruction algorithms. In this paper, we propose a novel \textbf{D}eep \textbf{R}esidual \textbf{R}econstruction Network (DR$^{2}$-Net) to reconstruct the image from its Compressively Sensed (CS) measurement. The DR$^{2}$-Net is proposed based on two observations: 1) linear mapping could reconstruct a high-quality preliminary image, and 2) residual learning could further improve the reconstruction quality. Accordingly, DR$^{2}$-Net consists of two components, \emph{i.e.,} linear mapping network and residual network, respectively. Specifically, the fully-connected layer in neural network implements the linear mapping network. We then expand the linear mapping network to DR$^{2}$-Net by adding several residual learning blocks to enhance the preliminary image. Extensive experiments demonstrate that the DR$^{2}$-Net outperforms traditional iterative methods and recent deep learning-based methods by large margins at measurement rates 0.01, 0.04, 0.1, and 0.25, respectively. The code of DR$^{2}$-Net has been released on: https://github.com/coldrainyht/caffe\_dr2
Network Systems and String Stability
Venue: arXiv cs.SY 2017
Year: 2017

Network systems and their control are highly important and appear in a variety of applications, including vehicle platooning and formation con- trol. Especially vehicle platoons are highly investigated and an interesting problem that arises in this area is string stability, which broadly spoken means that a input signal amplifies unbounded as it travels through the vehicle string. However, various definitions are commonly used. In this paper, we aim to formalise the notion of string stability and illustrate the importance of those distinctions on simulation examples. A second goal is to generalise the found definitions for general network systems.
Progressively Diffused Networks for Semantic Image Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

This paper introduces Progressively Diffused Networks (PDNs) for unifying multi-scale context modeling with deep feature learning, by taking semantic image segmentation as an exemplar application. Prior neural networks, such as ResNet, tend to enhance representational power by increasing the depth of architectures and driving the training objective across layers. However, we argue that spatial dependencies in different layers, which generally represent the rich contexts among data elements, are also critical to building deep and discriminative representations. To this end, our PDNs enables to progressively broadcast information over the learned feature maps by inserting a stack of information diffusion layers, each of which exploits multi-dimensional convolutional LSTMs (Long-Short-Term Memory Structures). In each LSTM unit, a special type of atrous filters are designed to capture the short range and long range dependencies from various neighbors to a certain site of the feature map and pass the accumulated information to the next layer. From the extensive experiments on semantic image segmentation benchmarks (e.g., ImageNet Parsing, PASCAL VOC2012 and PASCAL-Part), our framework demonstrates the effectiveness to substantially improve the performances over the popular existing neural network models, and achieves state-of-the-art on ImageNet Parsing for large scale semantic segmentation.
An Examination of the Benefits of Scalable TTI for Heterogeneous Traffic Management in 5G Networks
Venue: arXiv cs.IT 2017
Year: 2017

The rapid growth in the number and variety of connected devices requires 5G wireless systems to cope with a very heterogeneous traffic mix. As a consequence, the use of a fixed TTI during transmission is not necessarily the most efficacious method when heterogeneous traffic types need to be simultaneously serviced.This work analyzes the benefits of scheduling based on exploiting scalable TTI, where the channel assignment and the TTI duration are adapted to the deadlines and requirements of different services. We formulate an optimization problem by taking individual service requirements into consideration. We then prove that the optimization problem is NP-hard and provide a heuristic algorithm, which provides an effective solution to the problem. Numerical results show that our proposed algorithm is capable of finding near-optimal solutions to meet the latency requirements of mission critical communication services, while providing a good throughput performance for mobile broadband services.
Robust and adaptive search
Venue: arXiv cs.DS 2017
Year: 2017

Binary search finds a given element in a sorted array with an optimal number of $\log n$ queries. However, binary search fails even when the array is only slightly disordered or access to its elements is subject to errors. We study the worst-case query complexity of search algorithms that are robust to imprecise queries and that adapt to perturbations of the order of the elements. We give (almost) tight results for various parameters that quantify query errors and that measure array disorder. In particular, we exhibit settings where query complexities of $\log n + ck$, $(1+\varepsilon)\log n + ck$, and $\sqrt{cnk}+o(nk)$ are best-possible for parameter value $k$, any $\varepsilon>0$, and constant $c$.