OpenRaiser/Intern-Atlas huggingface dataset:
A Bimodal Co-Sparse Analysis Model for Image Processing
Venue: arXiv cs.CV 2014
Year: 2014

The success of many computer vision tasks lies in the ability to exploit the interdependency between different image modalities such as intensity and depth. Fusing corresponding information can be achieved on several levels, and one promising approach is the integration at a low level. Moreover, sparse signal models have successfully been used in many vision applications. Within this area of research, the so called co-sparse analysis model has attracted considerably less attention than its well-known counterpart, the sparse synthesis model, although it has been proven to be very useful in various image processing applications. In this paper, we propose a co-sparse analysis model that is able to capture the interdependency of two image modalities. It is based on the assumption that a pair of analysis operators exists, so that the co-supports of the corresponding bimodal image structures are correlated. We propose an algorithm that is able to learn such a coupled pair of operators from registered and noise-free training data. Furthermore, we explain how this model can be applied to solve linear inverse problems in image processing and how it can be used for image registration tasks. This paper extends the work of some of the authors by two major contributions. Firstly, a modification of the learning process is proposed that a priori guarantees unit norm and zero-mean of the rows of the operator. This accounts for the intuition that contrast in image modalities carries the most information. Secondly, the model is used in a novel bimodal image registration algorithm which estimates the transformation parameters of unregistered images of different modalities.
The Role of the Internet of Things in Network Resilience
Venue: arXiv cs.NI 2014
Year: 2014

Disasters lead to devastating structural damage not only to buildings and transport infrastructure, but also to other critical infrastructure, such as the power grid and communication backbones. Following such an event, the availability of minimal communication services is however crucial to allow efficient and coordinated disaster response, to enable timely public information, or to provide individuals in need with a default mechanism to post emergency messages. The Internet of Things consists in the massive deployment of heterogeneous devices, most of which battery-powered, and interconnected via wireless network interfaces. Typical IoT communication architectures enables such IoT devices to not only connect to the communication backbone (i.e. the Internet) using an infrastructure-based wireless network paradigm, but also to communicate with one another autonomously, without the help of any infrastructure, using a spontaneous wireless network paradigm. In this paper, we argue that the vast deployment of IoT-enabled devices could bring benefits in terms of data network resilience in face of disaster. Leveraging their spontaneous wireless networking capabilities, IoT devices could enable minimal communication services (e.g. emergency micro-message delivery) while the conventional communication infrastructure is out of service. We identify the main challenges that must be addressed in order to realize this potential in practice. These challenges concern various technical aspects, including physical connectivity requirements, network protocol stack enhancements, data traffic prioritization schemes, as well as social and political aspects.
Rental harmony with roommates
Venue: arXiv cs.GT 2014
Year: 2014

We prove existence of envy-free allocations in markets with heterogenous indivisible goods and money, when a given quantity is supplied from each of the goods and agents have unit demands. We depart from most of the previous literature by allowing agents' preferences over the goods to depend on the entire vector of prices. Our proof uses Shapley's K-K-M-S theorem and Hall's marriage lemma. We then show how our theorem may be applied in two related problems: Existence of envy-free allocations in a version of the cake-cutting problem, and existence of equilibrium in an exchange economy with indivisible goods and money.
Link Analysis for Communities Detection on Facebook
Venue: arXiv cs.SI 2014
Year: 2014

Social networks have become a part in the daily life of millions of users, which offer wide range of interests and practices. The main characteristic of social networks is its ability to gather different individuals around a common point of view or collective beliefs. Among the current social networking sites, Facebook is the most popular, which has the highest number of users. However, in Facebook, the existence of communities (groups)is a critical question; thus, many researchers focus on potential communities by using techniques like data mining and web mining. In this work, we present four approaches based on link analysis techniques to detect prospective groups and their members
Approximately Optimal Mechanism Design: Motivation, Examples, and Lessons Learned
Venue: arXiv cs.GT 2014
Year: 2014

Optimal mechanism design enjoys a beautiful and well-developed theory, and also a number of killer applications. Rules of thumb produced by the field influence everything from how governments sell wireless spectrum licenses to how the major search engines auction off online advertising. There are, however, some basic problems for which the traditional optimal mechanism design approach is ill-suited --- either because it makes overly strong assumptions, or because it advocates overly complex designs. The thesis of this paper is that approximately optimal mechanisms allow us to reason about fundamental questions that seem out of reach of the traditional theory. This survey has three main parts. The first part describes the approximately optimal mechanism design paradigm --- how it works, and what we aim to learn by applying it. The second and third parts of the survey cover two case studies, where we instantiate the general design paradigm to investigate two basic questions. In the first example, we consider revenue maximization in a single-item auction with heterogeneous bidders. Our goal is to understand if complexity --- in the sense of detailed distributional knowledge --- is an essential feature of good auctions for this problem, or alternatively if there are simpler auctions that are near-optimal. The second example considers welfare maximization with multiple items. Our goal here is similar in spirit: when is complexity --- in the form of high-dimensional bid spaces --- an essential feature of every auction that guarantees reasonable welfare? Are there interesting cases where low-dimensional bid spaces suffice?
Overlapping Community Detection Optimization and Nash Equilibrium
Venue: arXiv cs.SI 2014
Year: 2014

Community detection using both graphs and social networks is the focus of many algorithms. Recent methods aimed at optimizing the so-called modularity function proceed by maximizing relations within communities while minimizing inter-community relations. However, given the NP-completeness of the problem, these algorithms are heuristics that do not guarantee an optimum. In this paper, we introduce a new algorithm along with a function that takes an approximate solution and modifies it in order to reach an optimum. This reassignment function is considered a 'potential function' and becomes a necessary condition to asserting that the computed optimum is indeed a Nash Equilibrium. We also use this function to simultaneously show partitioning and overlapping communities, two detection and visualization modes of great value in revealing interesting features of a social network. Our approach is successfully illustrated through several experiments on either real unipartite, multipartite or directed graphs of medium and large-sized datasets.
A Concise Information-Theoretic Derivation of the Baum-Welch algorithm
Venue: arXiv cs.IT 2014
Year: 2014

We derive the Baum-Welch algorithm for hidden Markov models (HMMs) through an information-theoretical approach using cross-entropy instead of the Lagrange multiplier approach which is universal in machine learning literature. The proposed approach provides a more concise derivation of the Baum-Welch method and naturally generalizes to multiple observations.
Caching Piggyback Information for Efficient Index Code Transmission
Venue: arXiv cs.NI 2014
Year: 2014

The index coding problem is a fundamental transmission problem arising in content distribution and wireless networks. Traditional approach to solve this problem is to find heuristic/ approximation minimum clique partition solution on an appropriately mapped graph of the index coding problem. In this paper we study index code for unicast data flow for which we propose updated clique index coding (UCIC) scheme, UCIC piggybacks additional information in the coded symbol such that an unsatisfied client can update its cache. We show that UCIC has higher coding gain than previously proposed index coding schemes, and it is optimal for those instances where index code of minimum length is known.
UWB Signal Detection by Cyclic Features
Venue: arXiv cs.IT 2014
Year: 2014

Ultra-wideband (UWB) impulse radio (IR) systems are well known for low transmission power, low probability of detection, and overlaying with narrowband (NB) systems. These merits in fact make UWB signal detection challenging, since several high-power wireless communication systems coexist with UWB signals. In the literature, cyclic features are exploited for signal detection. However, the high computational complexity of conventional cyclic feature based detectors burdens the receivers. In this paper, we propose computationally efficient detectors using the specific cyclic features of UWB signals. The closed-form relationships between the cyclic features and the system parameters are revealed. Then, some constant false alarm rate detectors are proposed based on the estimated cyclic autocorrelation functions (CAFs). The proposed detectors have low complexities compared to the existing ones. Extensive simulation results indicate that the proposed detectors achieve a good balance between the detection performance and the computational complexity in various scenarios, such as multipath environments, colored noise, and NB interferences.
On The Reachability Problem for Recursive Hybrid Automata with One and Two Players
Venue: arXiv cs.LO 2014
Year: 2014

Motivated by the success of bounded model checking framework for finite state machines, Ouaknine and Worrell proposed a time-bounded theory of real-time verification by claiming that restriction to bounded-time recovers decidability for several key decision problem related to real-time verification. In support of this theory, the list of undecidable problems recently shown decidable under time-bounded restriction is rather impressive: language inclusion for timed automata, emptiness problem for alternating timed automata, and emptiness problem for rectangular hybrid automata. The objective of our study was to recover decidability for general recursive timed automata---and perhaps for recursive hybrid automata---under time-bounded restriction in order to provide an appealing verification framework for powerful modeling environments such as Stateflow/Simulink. Unfortunately, however, we answer this question in negative by showing that time-bounded reachability problem stays undecidable for recursive timed automata with five or more clocks. While the bad news continues even when one considers well-behaved subclasses of recursive hybrid automata, we recover decidability by considering recursive hybrid automata with bounded context using a pass-by-reference mechanism, or by restricting the number of variables to two, with rates in $\{0,1\}$.
On the Use of Different Feature Extraction Methods for Linear and Non Linear kernels
Venue: arXiv cs.CL 2014
Year: 2014

The speech feature extraction has been a key focus in robust speech recognition research; it significantly affects the recognition performance. In this paper, we first study a set of different features extraction methods such as linear predictive coding (LPC), mel frequency cepstral coefficient (MFCC) and perceptual linear prediction (PLP) with several features normalization techniques like rasta filtering and cepstral mean subtraction (CMS). Based on this, a comparative evaluation of these features is performed on the task of text independent speaker identification using a combination between gaussian mixture models (GMM) and linear and non-linear kernels based on support vector machine (SVM).
Hitting-sets for ROABP and Sum of Set-Multilinear circuits
Venue: arXiv cs.CC 2014
Year: 2014

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best result known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their exponential dependence on the individual degree. With this, we match the time-complexity for the unknown order ROABP with the known order ROABP (due to Forbes-Shpilka (FOCS 2013)) and also with the depth-$3$ set-multilinear circuits (due to Agrawal-Saha-Saxena (STOC 2013)). Our proof is simpler and involves a new technique called basis isolation. The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper, we take a step towards designing such hitting-sets. We give the first subexponential whitebox PIT for the sum of constantly many set-multilinear depth-$3$ circuits. To achieve this, we define notions of distance and base sets. Distance, for a multilinear depth-$3$ circuit, measures how far are the partitions from a mere refinement. We design a hitting-set in time $n^{O(d \log n)}$ for $d$-distance. Further, we give an extension of our result to models where the distance is large but it is small when restricted to certain base sets (of variables). We also explore a new model of ROABP where the factor-matrices are invertible (called invertible-factor ROABP). We design a hitting-set in time poly($n^{w^2}$) for width-$w$ invertible-factor ROABP. Further, we could do without the invertibility restriction when $w=2$. Previously, the best result for width-$2$ ROABP was quasi-polynomial time (Forbes-Saptharishi-Shpilka, STOC 2014).
Exploring Task Mappings on Heterogeneous MPSoCs using a Bias-Elitist Genetic Algorithm
Venue: arXiv cs.PF 2014
Year: 2014

Exploration of task mappings plays a crucial role in achieving high performance in heterogeneous multi-processor system-on-chip (MPSoC) platforms. The problem of optimally mapping a set of tasks onto a set of given heterogeneous processors for maximal throughput has been known, in general, to be NP-complete. The problem is further exacerbated when multiple applications (i.e., bigger task sets) and the communication between tasks are also considered. Previous research has shown that Genetic Algorithms (GA) typically are a good choice to solve this problem when the solution space is relatively small. However, when the size of the problem space increases, classic genetic algorithms still suffer from the problem of long evolution times. To address this problem, this paper proposes a novel bias-elitist genetic algorithm that is guided by domain-specific heuristics to speed up the evolution process. Experimental results reveal that our proposed algorithm is able to handle large scale task mapping problems and produces high-quality mapping solutions in only a short time period.
Building global and scalable systems with Atomic Multicast
Venue: arXiv cs.DC 2014
Year: 2014

The rise of worldwide Internet-scale services demands large distributed systems. Indeed, when handling several millions of users, it is common to operate thousands of servers spread across the globe. Here, replication plays a central role, as it contributes to improve the user experience by hiding failures and by providing acceptable latency. In this paper, we claim that atomic multicast, with strong and well-defined properties, is the appropriate abstraction to efficiently design and implement globally scalable distributed systems. We substantiate our claim with the design of two modern online services atop atomic multicast, a strongly consistent key-value store and a distributed log. In addition to presenting the design of these services, we experimentally assess their performance in a geographically distributed deployment.
Open Collaboration for Innovation: Principles and Performance
Venue: arXiv cs.CY 2014
Year: 2014

The principles of open collaboration for innovation (and production), once distinctive to open source software, are now found in many other ventures. Some of these ventures are internet-based: Wikipedia, online forums and communities. Others are off-line: in medicine, science, and everyday life. Such ventures have been affecting traditional firms, and may represent a new organizational form. Despite the impact of such ventures, questions remain about their operating principles and performance. Here we define open collaboration (OC), the underlying set of principles, and propose that it is a robust engine for innovation and production. First, we review multiple OC ventures and identify four defining principles. In all instances, participants create goods and services of economic value, they exchange and reuse each other's work, they labor purposefully with just loose coordination, and they permit anyone to contribute and consume. These principles distinguish OC from other organizational forms, such as firms or cooperatives. Next, we turn to performance. To understand the performance of OC, we develop a computational model, combining innovation theory with recent evidence on human cooperation. We identify and investigate three elements that affect performance: the cooperativeness of participants, the diversity of their needs, and the degree to which the goods are rival (subtractable). Through computational experiments, we find that OC performs well even in seemingly harsh environments: when cooperators are a minority, free riders are present, diversity is lacking, or goods are rival. We conclude that OC is viable and likely to expand into new domains. The findings also inform the discussion on new organizational forms, collaborative and communal.
Collective Intelligence in Citizen Science -- A Study of Performers and Talkers
Venue: arXiv cs.SI 2014
Year: 2014

The recent emergence of online citizen science is illustrative of an efficient and effective means to harness the crowd in order to achieve a range of scientific discoveries. Fundamentally, citizen science projects draw upon crowds of non-expert volunteers to complete short Tasks, which can vary in domain and complexity. However, unlike most human-computational systems, participants in these systems, the `citizen scientists' are volunteers, whereby no incentives, financial or otherwise, are offered. Furthermore, encouraged by citizen science platforms such as Zooniverse, online communities have emerged, providing them with an environment to discuss, share ideas, and solve problems. In fact, it is the result of these forums that has enabled a number of scientific discoveries to be made. In this paper we explore the phenomenon of collective intelligence via the relationship between the activities of online citizen science communities and the discovery of scientific knowledge. We perform a cross-project analysis of ten Zooniverse citizen science projects and analyse the behaviour of users with regards to their Task completion activity and participation in discussion and discover collective behaviour amongst highly active users. Whilst our findings have implications for future citizen science design, we also consider the wider implications for understanding collective intelligence research in general.
When is a crowd wise?
Venue: arXiv cs.SI 2014
Year: 2014

Numerous studies and anecdotes demonstrate the "wisdom of the crowd," the surprising accuracy of a group's aggregated judgments. Less is known, however, about the generality of crowd wisdom. For example, are crowds wise even if their members have systematic judgmental biases, or can influence each other before members render their judgments? If so, are there situations in which we can expect a crowd to be less accurate than skilled individuals? We provide a precise but general definition of crowd wisdom: A crowd is wise if a linear aggregate, for example a mean, of its members' judgments is closer to the target value than a randomly, but not necessarily uniformly, sampled member of the crowd. Building on this definition, we develop a theoretical framework for examining, a priori, when and to what degree a crowd will be wise. We systematically investigate the boundary conditions for crowd wisdom within this framework and determine conditions under which the accuracy advantage for crowds is maximized. Our results demonstrate that crowd wisdom is highly robust: Even if judgments are biased and correlated, one would need to nearly deterministically select only a highly skilled judge before an individual's judgment could be expected to be more accurate than a simple averaging of the crowd. Our results also provide an accuracy rationale behind the need for diversity of judgments among group members. Contrary to folk explanations of crowd wisdom which hold that judgments should ideally be independent so that errors cancel out, we find that crowd wisdom is maximized when judgments systematically differ as much as possible. We re-analyze data from two published studies that confirm our theoretical results.
Meme creation and sharing processes: individuals shaping the masses
Venue: arXiv cs.SI 2014
Year: 2014

The propagation of online memes is initially influenced by meme creators and secondarily by meme consumers, whose individual sharing decisions accumulate to determine total meme propagation. We characterize this as a sender/receiver sequence in which the first sender is also the creator. This sequence consists of two distinct processes, the creation process and the sharing process. We investigated these processes separately to determine their individual influence on sharing outcomes. Our study observed participants creating memes in the lab. We then tracked the sharing of those memes, derived a model of sharing behavior, and implemented our sharing model in a contagion simulation. Although we assume meme consumers typically have little or no information about a meme's creator when making a decision about whether to share a meme (and vice versa), we nevertheless ask whether consumer re-sharing behavior can be predicted based on features of the creator. Using human participants, web log monitoring, and statistical model fitting, the resulting Creator Model of Re-sharing Behavior predicts 11.5% of the variance in the behavior of consumers. Even when we know nothing about re-sharers of a meme, we can predict something about their behavior by observing the creation process. To investigate the individual re-sharing decisions that, together, constitute a meme's total consumer response, we built a statistical model from human observation. Receivers make their decision to share as a function of the meme's content and their reaction to it, which we model as a consumer's decision to share. The resulting Consumer Model of Sharing Decisions describes 37.5% of the variance in this decision making process.