OpenRaiser/Intern-Atlas huggingface dataset:
Accountability in Dynamic Networks
Venue: arXiv cs.GT 2016
Year: 2016

We take a game theoretical approach to determine necessary and sufficient conditions under which we can persuade rational agents to exchange messages in pairwise exchanges over links of a dynamic network, by holding them accountable for deviations with punishments. We make three contributions: (1) we provide a new game theoretical model of repeated interactions in dynamic networks, where agents have incomplete information of the topology, (2) we define a new solution concept for this model, and (3) we identify necessary and sufficient conditions for enforcing accountability, i.e., for persuading agents to exchange messages in the aforementioned model. Our results are of technical interest but also of practical relevance. We show that we cannot enforce accountability if the dynamic network does not allow for \emph{timely punishments}. In practice, this means for instance that we cannot enforce accountability in some networks formed in file-sharing applications such as Bittorrent\,\cite{Cohen:03}. We also show that for applications such as secret exchange, where the benefits of the exchanges significantly surpass the communication costs, timely punishments are enough to enforce accountability. However, we cannot in general enforce accountability if agents do not possess enough information about the network topology. Nevertheless, we can enforce accountability in a wide variety of networks that satisfy 1-connectivity\,\cite{Kuhn:10} with minimal knowledge about the network topology, including overlays for gossip dissemination such as \cite{Li:06,Li:08}.
Study of Interference Cancellation and Relay Selection Algorithms Using Greedy Techniques for Cooperative DS-CDMA Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we study interference cancellation techniques and a multi-relay selection algorithm based on greedy methods for the uplink of cooperative direct-sequence code-division multiple access (DS-CDMA) systems. We first devise low-cost list-based successive interference cancellation (GL-SIC) and parallel interference cancellation (GL-PIC) algorithms with RAKE receivers as the front-end that can approach the maximum likelihood detector performance and be used at both the relays and the destination of cooperative systems. Unlike prior art, the proposed GL-SIC and GL-PIC algorithms exploit the Euclidean distance between users of interest and the potential nearest constellation point with a chosen threshold in order to build an effective list of detection candidates. A low-complexity multi-relay selection algorithm based on greedy techniques that can approach the performance of an exhaustive search is also proposed. A cross-layer design strategy that brings together the proposed multiuser detection algorithms and the greedy relay selection is then developed along with an analysis of the proposed techniques. Simulations show an excellent bit error rate performance of the proposed detection and relay selection algorithms as compared to existing techniques.
TabMCQ: A Dataset of General Knowledge Tables and Multiple-choice Questions
Venue: arXiv cs.CL 2016
Year: 2016

We describe two new related resources that facilitate modelling of general knowledge reasoning in 4th grade science exams. The first is a collection of curated facts in the form of tables, and the second is a large set of crowd-sourced multiple-choice questions covering the facts in the tables. Through the setup of the crowd-sourced annotation task we obtain implicit alignment information between questions and tables. We envisage that the resources will be useful not only to researchers working on question answering, but also to people investigating a diverse range of other applications such as information extraction, question parsing, answer type identification, and lexical semantic modelling.
A Truthful Mechanism with Biparameter Learning for Online Crowdsourcing
Venue: arXiv cs.AI 2016
Year: 2016

We study a problem of allocating divisible jobs, arriving online, to workers in a crowdsourcing setting which involves learning two parameters of strategically behaving workers. Each job is split into a certain number of tasks that are then allocated to workers. Each arriving job has to be completed within a deadline and each task has to be completed satisfying an upper bound on probability of failure. The job population is homogeneous while the workers are heterogeneous in terms of costs, completion times, and times to failure. The job completion time and time to failure of each worker are stochastic with fixed but unknown means. The requester is faced with the challenge of learning two separate parameters of each (strategically behaving) worker simultaneously, namely, the mean job completion time and the mean time to failure. The time to failure of a worker depends on the duration of the task handled by the worker. Assuming non-strategic workers to start with, we solve this biparameter learning problem by applying the Robust UCB algorithm. Then, we non-trivially extend this algorithm to the setting where the workers are strategic about their costs. Our proposed mechanism is dominant strategy incentive compatible and ex-post individually rational with asymptotically optimal regret performance.
Fast and Robust Hand Tracking Using Detection-Guided Optimization
Venue: arXiv cs.CV 2016
Year: 2016

Markerless tracking of hands and fingers is a promising enabler for human-computer interaction. However, adoption has been limited because of tracking inaccuracies, incomplete coverage of motions, low framerate, complex camera setups, and high computational requirements. In this paper, we present a fast method for accurately tracking rapid and complex articulations of the hand using a single depth camera. Our algorithm uses a novel detection-guided optimization strategy that increases the robustness and speed of pose estimation. In the detection step, a randomized decision forest classifies pixels into parts of the hand. In the optimization step, a novel objective function combines the detected part labels and a Gaussian mixture representation of the depth to estimate a pose that best fits the depth. Our approach needs comparably less computational resources which makes it extremely fast (50 fps without GPU support). The approach also supports varying static, or moving, camera-to-scene arrangements. We show the benefits of our method by evaluating on public datasets and comparing against previous work.
Parametric Bounded Löb's Theorem and Robust Cooperation of Bounded Agents
Venue: arXiv cs.GT 2016
Year: 2016

Löb's theorem and Gödel's theorems make predictions about the behavior of systems capable of self-reference with unbounded computational resources with which to write and evaluate proofs. However, in the real world, systems capable of self-reference will have limited memory and processing speed, so in this paper we introduce an effective version of Löb's theorem which is applicable given such bounded resources. These results have powerful implications for the game theory of bounded agents who are able to write proofs about themselves and one another, including the capacity to out-perform classical Nash equilibria and correlated equilibria, attaining mutually cooperative program equilibrium in the Prisoner's Dilemma. Previous cooperative program equilibria studied by Tennenholtz (2004) and Fortnow (2009) have depended on tests for program equality, a fragile condition, whereas "Löbian" cooperation is much more robust and agnostic of the opponent's implementation.
Adaptive Multi-polling Scheduler for QoS Support of Video Transmission in IEEE 802.11e WLANs
Venue: arXiv cs.NI 2016
Year: 2016

The 802.11E Task Group has been established to enhance Quality of Service (QoS) provision for time-bounded services in the current IEEE 802.11 Medium Access Control (MAC) protocol. The QoS is introduced throughout Hybrid Coordination Function Controlled Channel Access (HCCA) for the rigorous QoS provision. In HCCA, the station is allocated a fixed Transmission Opportunity (TXOP) based on its TSPEC parameters so that it is efficient for Constant Bit Rate streams. However, as the profile of Variable Bit Rate (VBR) traffics is inconstant, they are liable to experience a higher delay especially in bursty traffic case. In this paper, we present a dynamic TXOP assignment algorithm called Adaptive Multi-polling TXOP scheduling algorithm (AMTXOP) for supporting the video traffics transmission over IEEE 802.11e wireless networks. This scheme invests a piggybacked information about the size of the subsequent video frames of the uplink streams to assist the Hybrid Coordinator accurately assign the TXOP according to actual change in the traffic profile. The proposed scheduler is powered by integrating multi-polling scheme to further reduce the delay and polling overhead. Extensive simulation experiments have been carried out to show the efficiency of the AMTXOP over the existing schemes in terms of the packet delay and the channel utilization.
Consensus-Based Torque Control of Deloaded Wind DFIGs for Distributed and Fair Dynamic Dispatching
Venue: arXiv cs.SY 2016
Year: 2016

In this paper we aim to address the problem of dynamically dispatching a group of state-of-the-art deloaded wind generators (WGs) in a fair-sharing manner. We use the term dynamically since the WGs aim to dispatch themselves according to a varying committed WF power output. We first propose a leader-follower protocol whose execution guarantees asymptotically, two control objectives. These are 1) reaching asymptotic consensus on the utilization level of all WGs and 2) the total power output of the WGs asymptotically converges to the reference value. Thereafter, we combine singular perturbation and Lyapunov theory to prove that, under certain conditions, the proposed protocol will asymptotically converge to its equilibrium. Finally, we derive a cooperative Control Lyapunov Function-based (CLF) controller for the rotor side converter (RSC) of each WG that realizes the protocol in practice. We demonstrate the effectiveness of our proposed protocol and the corresponding RSC controller design via simulations on the modified IEEE 24-bus RT system.
A Minimalistic Approach to Sum-Product Network Learning for Real Applications
Venue: arXiv cs.AI 2016
Year: 2016

Sum-Product Networks (SPNs) are a class of expressive yet tractable hierarchical graphical models. LearnSPN is a structure learning algorithm for SPNs that uses hierarchical co-clustering to simultaneously identifying similar entities and similar features. The original LearnSPN algorithm assumes that all the variables are discrete and there is no missing data. We introduce a practical, simplified version of LearnSPN, MiniSPN, that runs faster and can handle missing data and heterogeneous features common in real applications. We demonstrate the performance of MiniSPN on standard benchmark datasets and on two datasets from Google's Knowledge Graph exhibiting high missingness rates and a mix of discrete and continuous features.
Adaptivity provably helps: information-theoretic limits on $l_0$ cost of non-adaptive sensing
Venue: arXiv cs.IT 2016
Year: 2016

The advantages of adaptivity and feedback are of immense interest in signal processing and communication with many positive and negative results. Although it is established that adaptivity does not offer substantial reductions in minimax mean square error for a fixed number of measurements, existing results have shown several advantages of adaptivity in complexity of reconstruction, accuracy of support detection, and gain in signal-to-noise ratio, under constraints on sensing energy. Sensing energy has often been measured in terms of the Frobenius Norm of the sensing matrix. This paper uses a different metric that we call the $l_0$ cost of a sensing matrix-- to quantify the complexity of sensing. Thus sparse sensing matrices have a lower cost. We derive information-theoretic lower bounds on the $l_0$ cost that hold for any non-adaptive sensing strategy. We establish that any non-adaptive sensing strategy must incur an $l_0$ cost of $Θ\left( N \log_2(N)\right) $ to reconstruct an $N$-dimensional, one--sparse signal when the number of measurements are limited to $Θ\left(\log_2 (N)\right)$. In comparison, bisection-type adaptive strategies only require an $l_0$ cost of at most $\mathcal{O}(N)$ for an equal number of measurements. The problem has an interesting interpretation as a sphere packing problem in a multidimensional space, such that all the sphere centres have minimum non-zero co-ordinates. We also discuss the variation in $l_0$ cost as the number of measurements increase from $Θ\left(\log_2 (N)\right)$ to $Θ\left(N\right)$.
The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
Venue: arXiv cs.LO 2016
Year: 2016

We prove that an $ω$-categorical core structure primitively positively interprets all finite structures with parameters if and only if some stabilizer of its polymorphism clone has a homomorphism to the clone of projections, and that this happens if and only if its polymorphism clone does not contain operations $α$, $β$, $s$ satisfying the identity $αs(x,y,x,z,y,z) \approx βs(y,x,z,x,z,y)$. This establishes an algebraic criterion equivalent to the conjectured borderline between P and NP-complete CSPs over reducts of finitely bounded homogenous structures, and accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our theorem is also of independent mathematical interest, characterizing a topological property of any $ω$-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).
Machine olfaction using time scattering of sensor multiresolution graphs
Venue: arXiv cs.AI 2016
Year: 2016

In this paper we construct a learning architecture for high dimensional time series sampled by sensor arrangements. Using a redundant wavelet decomposition on a graph constructed over the sensor locations, our algorithm is able to construct discriminative features that exploit the mutual information between the sensors. The algorithm then applies scattering networks to the time series graphs to create the feature space. We demonstrate our method on a machine olfaction problem, where one needs to classify the gas type and the location where it originates from data sampled by an array of sensors. Our experimental results clearly demonstrate that our method outperforms classical machine learning techniques used in previous studies.
The triangle scheduling problem
Venue: arXiv cs.DS 2016
Year: 2016

This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the greedy algorithm solves the problem to optimality when the binary tree ratio of the input instance is at most 2. We also show that the problem is unary NP-hard for instances with binary tree ratio strictly larger than 2, and provide a quasi polynomial time approximation scheme (QPTAS). The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.
Temperature-aware Dynamic Optimization of Embedded Systems
Venue: arXiv cs.AR 2016
Year: 2016

Due to embedded systems` stringent design constraints, much prior work focused on optimizing energy consumption and/or performance. Since embedded systems typically have fewer cooling options, rising temperature, and thus temperature optimization, is an emergent concern. Most embedded systems only dissipate heat by passive convection, due to the absence of dedicated thermal management hardware mechanisms. The embedded system`s temperature not only affects the system`s reliability, but could also affect the performance, power, and cost. Thus, embedded systems require efficient thermal management techniques. However, thermal management can conflict with other optimization objectives, such as execution time and energy consumption. In this paper, we focus on managing the temperature using a synergy of cache optimization and dynamic frequency scaling, while also optimizing the execution time and energy consumption. This paper provides new insights on the impact of cache parameters on efficient temperature-aware cache tuning heuristics. In addition, we present temperature-aware phase-based tuning, TaPT, which determines Pareto optimal clock frequency and cache configurations for fine-grained execution time, energy, and temperature tradeoffs. TaPT enables autonomous system optimization and also allows designers to specify temperature constraints and optimization priorities. Experiments show that TaPT can effectively reduce execution time, energy, and temperature, while imposing minimal hardware overhead.
Phase distance mapping: a phase-based cache tuning methodology for embedded systems
Venue: arXiv cs.AR 2016
Year: 2016

Networked embedded systems typically leverage a collection of low-power embedded systems (nodes) to collaboratively execute applications spanning diverse application domains (e.g., video, image processing, communication, etc.) with diverse application requirements. The individual networked nodes must operate under stringent constraints (e.g., energy, memory, etc.) and should be specialized to meet varying application requirements in order to adhere to these constraints. Phase-based tuning specializes system tunable parameters to the varying runtime requirements of different execution phases to meet optimization goals. Since the design space for tunable systems can be very large, one of the major challenges in phase-based tuning is determining the best configuration for each phase without incurring significant tuning overhead (e.g., energy and/or performance) during design space exploration. In this paper, we propose phase distance mapping, which directly determines the best configuration for a phase, thereby eliminating design space exploration. Phase distance mapping applies the correlation between the characteristics and best configuration of a known phase to determine the best configuration of a new phase. Experimental results verify that our phase distance mapping approach, when applied to cache tuning, determines cache configurations within 1 % of the optimal configurations on average and yields an energy delay product savings of 27 % on average.
Hi Detector, What's Wrong with that Object? Identifying Irregular Object From Images by Modelling the Detection Score Distribution
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we study the challenging problem of identifying the irregular status of objects from images in an "open world" setting, that is, distinguishing the irregular status of an object category from its regular status as well as objects from other categories in the absence of "irregular object" training data. To address this problem, we propose a novel approach by inspecting the distribution of the detection scores at multiple image regions based on the detector trained from the "regular object" and "other objects". The key observation motivating our approach is that for "regular object" images as well as "other objects" images, the region-level scores follow their own essential patterns in terms of both the score values and the spatial distributions while the detection scores obtained from an "irregular object" image tend to break these patterns. To model this distribution, we propose to use Gaussian Processes (GP) to construct two separate generative models for the case of the "regular object" and the "other objects". More specifically, we design a new covariance function to simultaneously model the detection score at a single region and the score dependencies at multiple regions. We finally demonstrate the superior performance of our method on a large dataset newly proposed in this paper.
Frequency Analysis of Temporal Graph Signals
Venue: arXiv cs.LG 2016
Year: 2016

This letter extends the concept of graph-frequency to graph signals that evolve with time. Our goal is to generalize and, in fact, unify the familiar concepts from time- and graph-frequency analysis. To this end, we study a joint temporal and graph Fourier transform (JFT) and demonstrate its attractive properties. We build on our results to create filters which act on the joint (temporal and graph) frequency domain, and show how these can be used to perform interference cancellation. The proposed algorithms are distributed, have linear complexity, and can approximate any desired joint filtering objective.
Subgraph Counting: Color Coding Beyond Trees
Venue: arXiv cs.DC 2016
Year: 2016

The problem of counting occurrences of query graphs in a large data graph, known as subgraph counting, is fundamental to several domains such as genomics and social network analysis. Many important special cases (e.g. triangle counting) have received significant attention. Color coding is a very general and powerful algorithmic technique for subgraph counting. Color coding has been shown to be effective in several applications, but scalable implementations are only known for the special case of {\em tree queries} (i.e. queries of treewidth one). In this paper we present the first efficient distributed implementation for color coding that goes beyond tree queries: our algorithm applies to any query graph of treewidth $2$. Since tree queries can be solved in time linear in the size of the data graph, our contribution is the first step into the realm of colour coding for queries that require superlinear running time in the worst case. This superlinear complexity leads to significant load balancing problems on graphs with heavy tailed degree distributions. Our algorithm structures the computation to work around high degree nodes in the data graph, and achieves very good runtime and scalability on a diverse collection of data and query graph pairs as a result. We also provide theoretical analysis of our algorithmic techniques, showing asymptotic improvements in runtime on random graphs with power law degree distributions, a popular model for real world graphs.
Extending Consequence-Based Reasoning to SRIQ
Venue: arXiv cs.AI 2016
Year: 2016

Consequence-based calculi are a family of reasoning algorithms for description logics (DLs), and they combine hypertableau and resolution in a way that often achieves excellent performance in practice. Up to now, however, they were proposed for either Horn DLs (which do not support disjunction), or for DLs without counting quantifiers. In this paper we present a novel consequence-based calculus for SRIQ---a rich DL that supports both features. This extension is non-trivial since the intermediate consequences that need to be derived during reasoning cannot be captured using DLs themselves. The results of our preliminary performance evaluation suggest the feasibility of our approach in practice.
Socially Impaired Robots: Human Social Disorders and Robots' Socio-Emotional Intelligence
Venue: arXiv cs.RO 2016
Year: 2016

Social robots need intelligence in order to safely coexist and interact with humans. Robots without functional abilities in understanding others and unable to empathise might be a societal risk and they may lead to a society of socially impaired robots. In this work we provide a survey of three relevant human social disorders, namely autism, psychopathy and schizophrenia, as a means to gain a better understanding of social robots' future capability requirements. We provide evidence supporting the idea that social robots will require a combination of emotional intelligence and social intelligence, namely socio-emotional intelligence. We argue that a robot with a simple socio-emotional process requires a simulation-driven model of intelligence. Finally, we provide some critical guidelines for designing future socio-emotional robots.