OpenRaiser/Intern-Atlas huggingface dataset:
Bandit-Based Task Assignment for Heterogeneous Crowdsourcing
Venue: arXiv cs.LG 2015
Year: 2015

We consider a task assignment problem in crowdsourcing, which is aimed at collecting as many reliable labels as possible within a limited budget. A challenge in this scenario is how to cope with the diversity of tasks and the task-dependent reliability of workers, e.g., a worker may be good at recognizing the name of sports teams, but not be familiar with cosmetics brands. We refer to this practical setting as heterogeneous crowdsourcing. In this paper, we propose a contextual bandit formulation for task assignment in heterogeneous crowdsourcing, which is able to deal with the exploration-exploitation trade-off in worker selection. We also theoretically investigate the regret bounds for the proposed method, and demonstrate its practical usefulness experimentally.
Multiple Redundancy Constants with Trickle
Venue: arXiv cs.NI 2015
Year: 2015

Wireless sensor network protocols very often use the Trickle algorithm to govern information dissemination. For example, the widely used IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) uses Trickle to emit control packets. We derive an analytical model of Trickle to take into account multiple redundancy constants and the common lack of synchronization among nodes. Moreover, we demonstrate message count unfairness when Trickle uses a unique global redundancy constant because nodes with less neighbors transmit more often. Consequently, we propose a heuristic algorithm that calculates a redundancy constant for each node as a function of its number of neighbors. Our calculated redundancy constants reduce unfairness among nodes by distributing more equally the number of transmitted messages in the network. Our analytical model is validated by emulations of constrained devices running the Contiki Operating System and its IPv6 networking stack. Furthermore, results very well corroborate the heuristic algorithm improvements.
Clustering is Efficient for Approximate Maximum Inner Product Search
Venue: arXiv cs.LG 2015
Year: 2015

Efficient Maximum Inner Product Search (MIPS) is an important task that has a wide applicability in recommendation systems and classification with a large number of classes. Solutions based on locality-sensitive hashing (LSH) as well as tree-based solutions have been investigated in the recent literature, to perform approximate MIPS in sublinear time. In this paper, we compare these to another extremely simple approach for solving approximate MIPS, based on variants of the k-means clustering algorithm. Specifically, we propose to train a spherical k-means, after having reduced the MIPS problem to a Maximum Cosine Similarity Search (MCSS). Experiments on two standard recommendation system benchmarks as well as on large vocabulary word embeddings, show that this simple approach yields much higher speedups, for the same retrieval precision, than current state-of-the-art hashing-based and tree-based methods. This simple method also yields more robust retrievals when the query is corrupted by noise.
Generalized Totalizer Encoding for Pseudo-Boolean Constraints
Venue: arXiv cs.LO 2015
Year: 2015

Pseudo-Boolean constraints, also known as 0-1 Integer Linear Constraints, are used to model many real-world problems. A common approach to solve these constraints is to encode them into a SAT formula. The runtime of the SAT solver on such formula is sensitive to the manner in which the given pseudo-Boolean constraints are encoded. In this paper, we propose generalized Totalizer encoding (GTE), which is an arc-consistency preserving extension of the Totalizer encoding to pseudo-Boolean constraints. Unlike some other encodings, the number of auxiliary variables required for GTE does not depend on the magnitudes of the coefficients. Instead, it depends on the number of distinct combinations of these coefficients. We show the superiority of GTE with respect to other encodings when large pseudo-Boolean constraints have low number of distinct coefficients. Our experimental results also show that GTE remains competitive even when the pseudo-Boolean constraints do not have this characteristic.
Tweeting Over The Border: An Empirical Study of Transnational Migration in San Diego and Tijuana
Venue: arXiv cs.SI 2015
Year: 2015

Sociological studies on transnational migration are often based on surveys or interviews, an expensive and time consuming approach. On the other hand, the pervasiveness of mobile phones and location aware social networks has introduced new ways to understand human mobility patterns at a national or global scale. In this work, we leverage geo located information obtained from Twitter as to understand transnational migration patterns between two border cities (San Diego, USA and Tijuana, Mexico). We obtained 10.9 million geo located tweets from December 2013 to January 2015. Our method infers human mobility by inspecting tweet submissions and user's home locations. Our results depict a trans national community structure that exhibits the formation of a functional metropolitan area that physically transcends international borders. These results show the potential for re analysing sociology phenomena from a technology based empirical perspective.
Design Contracts For Networked Automation Systems Co-design
Venue: arXiv cs.SY 2015
Year: 2015

Networked automation systems (NAS) are characterized by confluence of control, computation, communication and Information (C3I) technologies. Design decisions of one domain are affected by the constraints posed by others. Reliable NAS design should address the requirements of the system, and simultaneously meet the constraints posed by other domains and this is called co-design in literature. Co-design requires clear definition of interfaces among these domains. Control design in NAS is affected by the timing imperfections posed by other domains. In this investigation, we first study the different sources of timing imperfections in NAS, and classify them based on their occurrence. The concept of jitter is used to define the timing imperfections induced by various system components. Using this analysis, we classify the jitter based on their behavior and domain of occurrence. Our analysis shows that the jitter induced in NAS can be classified based on domain as- hardware, software and communication. Next, we use this analysis to model the jitter from the components of NAS. Modeling timing imperfections helps in capturing the interfaces among the domains, and we use the concept of design contracts to capture the interfaces. Design contracts describe the semantic mapping among the domains and are specified using the jitter margins. Implementing design contracts requires knowledge of the jitter margin and, the results from control theory are used to this extent.
Structural Resolution for Logic Programming
Venue: arXiv cs.LO 2015
Year: 2015

We introduce a Three Tier Tree Calculus (3TC) that defines in a systematic way three tiers of tree structures underlying proof search in logic programming. We use 3TC to define a new -- structural -- version of resolution for logic programming.
Robust speech recognition using consensus function based on multi-layer networks
Venue: arXiv cs.CL 2015
Year: 2015

The clustering ensembles mingle numerous partitions of a specified data into a single clustering solution. Clustering ensemble has emerged as a potent approach for ameliorating both the forcefulness and the stability of unsupervised classification results. One of the major problems in clustering ensembles is to find the best consensus function. Finding final partition from different clustering results requires skillfulness and robustness of the classification algorithm. In addition, the major problem with the consensus function is its sensitivity to the used data sets quality. This limitation is due to the existence of noisy, silence or redundant data. This paper proposes a novel consensus function of cluster ensembles based on Multilayer networks technique and a maintenance database method. This maintenance database approach is used in order to handle any given noisy speech and, thus, to guarantee the quality of databases. This can generates good results and efficient data partitions. To show its effectiveness, we support our strategy with empirical evaluation using distorted speech from Aurora speech databases.
Data-free parameter pruning for Deep Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Deep Neural nets (NNs) with millions of parameters are at the heart of many state-of-the-art computer vision systems today. However, recent works have shown that much smaller models can achieve similar levels of performance. In this work, we address the problem of pruning parameters in a trained NN model. Instead of removing individual weights one at a time as done in previous works, we remove one neuron at a time. We show how similar neurons are redundant, and propose a systematic way to remove them. Our experiments in pruning the densely connected layers show that we can remove upto 85\% of the total parameters in an MNIST-trained network, and about 35\% for AlexNet without significantly affecting performance. Our method can be applied on top of most networks with a fully connected layer to give a smaller network.
Bayesian Time-of-Flight for Realtime Shape, Illumination and Albedo
Venue: arXiv cs.CV 2015
Year: 2015

We propose a computational model for shape, illumination and albedo inference in a pulsed time-of-flight (TOF) camera. In contrast to TOF cameras based on phase modulation, our camera enables general exposure profiles. This results in added flexibility and requires novel computational approaches. To address this challenge we propose a generative probabilistic model that accurately relates latent imaging conditions to observed camera responses. While principled, realtime inference in the model turns out to be infeasible, and we propose to employ efficient non-parametric regression trees to approximate the model outputs. As a result we are able to provide, for each pixel, at video frame rate, estimates and uncertainty for depth, effective albedo, and ambient light intensity. These results we present are state-of-the-art in depth imaging. The flexibility of our approach allows us to easily enrich our generative model. We demonstrate that by extending the original single-path model to a two-path model, capable of describing some multipath effects. The new model is seamlessly integrated in the system at no additional computational cost. Our work also addresses the important question of optimal exposure design in pulsed TOF systems. Finally, for benchmark purposes and to obtain realistic empirical priors of multipath and insights into this phenomena, we propose a physically accurate simulation of multipath phenomena.
Towards Very Large Aperture Massive MIMO: a measurement based study
Venue: arXiv cs.IT 2015
Year: 2015

Massive MIMO is a new technique for wireless communications that claims to offer very high system throughput and energy efficiency in multi-user scenarios. The cost is to add a very large number of antennas at the base station. Theoretical research has probed these benefits, but very few measurements have showed the potential of Massive MIMO in practice. We investigate the properties of measured Massive MIMO channels in a large indoor venue. We describe a measurement campaign using 3 arrays having different shape and aperture, with 64 antennas and 8 users with 2 antennas each. We focus on the impact of the array aperture which is the main limiting factor in the degrees of freedom available in the multiple antenna channel. We find that performance is improved as the aperture increases, with an impact mostly visible in crowded scenarios where the users are closely spaced. We also test MIMO capability within a same user device with user proximity effect. We see a good channel resolvability with confirmation of the strong effect of the user hand grip. At last, we highlight that propagation conditions where line-of-sight is dominant can be favorable.
Authorship Patterns in Computer Science Research in the Philippines
Venue: arXiv cs.DL 2015
Year: 2015

We studied patterns of authorship in computer science~(CS) research in the Philippines by using data mining and graph theory techniques on archives of scientific papers presented in the Philippine Computer Science Congresses from 2000 to 2010 involving 326~papers written by 605~authors. We inferred from these archives various graphs namely, a paper--author bipartite graph, a co-authorship graph, and two mixing graphs. Our results show that the scientific articles by Filipino computer scientists were generated at a rate of 33~papers per year, while the papers were written by an average of 2.64~authors (maximum=13). The frequency distribution of the number of authors per paper follows a power-law with a power of $φ=-2.04$ ($R^2=0.71$). The number of Filipino CS researchers increases at an annual rate of 60~new scientists. The researchers have written an average of 1.42~papers (maximum=20) and have collaborated with 3.70~other computer scientists (maximum=54). The frequency distribution of the number of papers per author follows a power law with $φ=-1.88$ ($R^2=0.83$). This distribution closely agrees with Lotka's {\em law of scientific productivity} having $φ\approx -2$. The number of co-authors per author also follows a power-law with $φ=-1.65$ ($R^2=0.80$). These results suggest that most CS~papers in the country were written by scientists who prefer to work alone or at most in small groups. These also suggest that few papers were written by scientists who were involved in large collaboration efforts. The productivity of the Philippines' CS researchers, as measured by their number of papers, is positively correlated with their participation in collaborative research efforts, as measured by their number of co-authors (Pearson $r=0.7425$).
Evaluation of Contactless Smartcard Antennas
Venue: arXiv cs.CR 2015
Year: 2015

This report summarizes the results of our evaluation of antennas of contactless and dual interface smartcards and our ideas for user-switchable NFC antennas. We show how to disassemble smartcards with contactless capabilities in order to obtain the bare chip module and the bare antenna wire. We examine the design of various smartcard antennas and present concepts to render the contactless interface unusable. Finally, we present ideas and practical experiments to make the contactless interface switchable by the end-user.
Manitest: Are classifiers really invariant?
Venue: arXiv cs.CV 2015
Year: 2015

Invariance to geometric transformations is a highly desirable property of automatic classifiers in many image recognition tasks. Nevertheless, it is unclear to which extent state-of-the-art classifiers are invariant to basic transformations such as rotations and translations. This is mainly due to the lack of general methods that properly measure such an invariance. In this paper, we propose a rigorous and systematic approach for quantifying the invariance to geometric transformations of any classifier. Our key idea is to cast the problem of assessing a classifier's invariance as the computation of geodesics along the manifold of transformed images. We propose the Manitest method, built on the efficient Fast Marching algorithm to compute the invariance of classifiers. Our new method quantifies in particular the importance of data augmentation for learning invariance from data, and the increased invariance of convolutional neural networks with depth. We foresee that the proposed generic tool for measuring invariance to a large class of geometric transformations and arbitrary classifiers will have many applications for evaluating and comparing classifiers based on their invariance, and help improving the invariance of existing classifiers.
Large scale lattice Boltzmann simulation for the coupling of free and porous media flow
Venue: arXiv cs.CE 2015
Year: 2015

In this work, we investigate the interaction of free and porous media flow by large scale lattice Boltzmann simulations. We study the transport phenomena at the porous interface on multiple scales, i.e., we consider both, computationally generated pore-scale geometries and homogenized models at a macroscopic scale. The pore-scale results are compared to those obtained by using different transmission models. Two-domain approaches with sharp interface conditions, e.g., of Beavers--Joseph--Saffman type, as well as a single-domain approach with a porosity depending viscosity are taken into account. For the pore-scale simulations, we use a highly scalable communication-reducing scheme with a robust second order boundary handling. We comment on computational aspects of the pore-scale simulation and on how to generate pore-scale geometries. The two-domain approaches depend sensitively on the choice of the exact position of the interface, whereas a well-designed single-domain approach can significantly better recover the averaged pore-scale results.
Weighted Efficient Domination for $P_5$-Free Graphs in Linear Time
Venue: arXiv cs.DM 2015
Year: 2015

In a finite undirected graph $G=(V,E)$, a vertex $v \in V$ {\em dominates} itself and its neighbors. A vertex set $D \subseteq V$ in $G$ is an {\em efficient dominating set} ({\em e.d.} for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The {\em Efficient Domination} (ED) problem, which asks for the existence of an e.d. in $G$, is known to be NP-complete for $P_7$-free graphs but solvable in polynomial time for $P_5$-free graphs. Very recently, it has been shown by Lokshtanov et al. and independently by Mosca that ED is solvable in polynomial time for $P_6$-free graphs. In this note, we show that, based on modular decomposition, ED is solvable in linear time for $P_5$-free graphs.
A Neighbourhood-Based Stopping Criterion for Contrastive Divergence Learning
Venue: arXiv cs.NE 2015
Year: 2015

Restricted Boltzmann Machines (RBMs) are general unsupervised learning devices to ascertain generative models of data distributions. RBMs are often trained using the Contrastive Divergence learning algorithm (CD), an approximation to the gradient of the data log-likelihood. A simple reconstruction error is often used as a stopping criterion for CD, although several authors \cite{schulz-et-al-Convergence-Contrastive-Divergence-2010-NIPSw, fischer-igel-Divergence-Contrastive-Divergence-2010-ICANN} have raised doubts concerning the feasibility of this procedure. In many cases the evolution curve of the reconstruction error is monotonic while the log-likelihood is not, thus indicating that the former is not a good estimator of the optimal stopping point for learning. However, not many alternatives to the reconstruction error have been discussed in the literature. In this manuscript we investigate simple alternatives to the reconstruction error, based on the inclusion of information contained in neighboring states to the training set, as a stopping criterion for CD learning.
Media Usage in Post-Secondary Education and Implications for Teaching and Learning
Venue: arXiv cs.CY 2015
Year: 2015

The Web 2.0 has permeated academic life. The use of online information services in post-secondary education has led to dramatic changes in faculty teaching methods as well as in the learning and study behavior of students. At the same time, traditional information media, such as textbooks and printed handouts, still form the basic pillars of teaching and learning. This paper reports the results of a survey about media usage in teaching and learning conducted with Western University students and instructors, highlighting trends in the usage of new and traditional media in higher education by instructors and students. In addition, the survey comprises part of an international research program in which 20 universities from 10 countries are currently participating. Further, the study will hopefully become a part of the ongoing discussion of practices and policies that purport to advance the effective use of media in teaching and learning.
Micro Service Cloud Computing Pattern for Next Generation Networks
Venue: arXiv cs.DC 2015
Year: 2015

The falling trend in the revenue of traditional telephony services has attracted attention to new IP based services. The IP Multimedia System (IMS) is a key architecture which provides the necessary platform for delivery of new multimedia services. However, current implementations of IMS do not offer automatic scalability or elastisity for the growing number of customers. Although the cloud computing paradigm has shown many promising characteristics for web applications, it is still failing to meet the requirements for telecommunication applications. In this paper, we present some related cloud computing patterns and discuss their adaptations for implementation of IMS or other telecommunication systems.
All Colors Shortest Path Problem
Venue: arXiv cs.CC 2015
Year: 2015

All Colors Shortest Path problem defined on an undirected graph aims at finding a shortest, possibly non-simple, path where every color occurs at least once, assuming that each vertex in the graph is associated with a color known in advance. To the best of our knowledge, this paper is the first to define and investigate this problem. Even though the problem is computationally similar to generalized minimum spanning tree, and the generalized traveling salesman problems, allowing for non-simple paths where a node may be visited multiple times makes All Colors Shortest Path problem novel and computationally unique. In this paper we prove that All Colors Shortest Path problem is NP-hard, and does not lend itself to a constant factor approximation. We also propose several heuristic solutions for this problem based on LP-relaxation, simulated annealing, ant colony optimization, and genetic algorithm, and provide extensive simulations for a comparative analysis of them. The heuristics presented are not the standard implementations of the well known heuristic algorithms, but rather sophisticated models tailored for the problem in hand. This fact is acknowledged by the very promising results reported.
Compressed Data Structures for Dynamic Sequences
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of storing a dynamic string $S$ over an alphabet $Σ=\{\,1,\ldots,σ\,\}$ in compressed form. Our representation supports insertions and deletions of symbols and answers three fundamental queries: $\mathrm{access}(i,S)$ returns the $i$-th symbol in $S$, $\mathrm{rank}_a(i,S)$ counts how many times a symbol $a$ occurs among the first $i$ positions in $S$, and $\mathrm{select}_a(i,S)$ finds the position where a symbol $a$ occurs for the $i$-th time. We present the first fully-dynamic data structure for arbitrarily large alphabets that achieves optimal query times for all three operations and supports updates with worst-case time guarantees. Ours is also the first fully-dynamic data structure that needs only $nH_k+o(n\logσ)$ bits, where $H_k$ is the $k$-th order entropy and $n$ is the string length. Moreover our representation supports extraction of a substring $S[i..i+\ell]$ in optimal $O(\log n/\log\log n + \ell/\log_σn)$ time.
Contributors Preference in Open Source Software Usability: An Empirical Study
Venue: arXiv cs.SE 2015
Year: 2015

The fact that the number of users of open source software (OSS) is practically un-limited and that ultimately the software quality is determined by end users experience, makes the usability an even more critical quality attribute than it is for proprietary software. With the sharp increase in use of open source projects by both individuals and organizations, the level of usability and related issues must be addressed more seriously. The research model of this empirical investigation studies and establishes the relationship between the key usability factors from contributors perspective and OSS usability. A data set of 78 OSS contributors that includes architects, designers, developers, testers and users from 22 open source projects of varied size has been used to study the research model. The results of this study provide empirical evidence by indicating that the highlighted key factors play a significant role in improving OSS usability.