OpenRaiser/Intern-Atlas huggingface dataset:
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
Venue: arXiv cs.GT 2016
Year: 2016

Peer-prediction is a mechanism which elicits privately-held, non-variable information from self-interested agents---formally, truth-telling is a strict Bayes Nash equilibrium of the mechanism. The original Peer-prediction mechanism suffers from two main limitations: (1) the mechanism must know the "common prior" of agents' signals; (2) additional undesirable and non-truthful equilibria exist which often have a greater expected payoff than the truth-telling equilibrium. A series of results has successfully weakened the known common prior assumption. However, the equilibrium multiplicity issue remains a challenge. In this paper, we address the above two problems. In the setting where a common prior exists but is not known to the mechanism we show (1) a general negative result applying to a large class of mechanisms showing truth-telling can never pay strictly more in expectation than a particular set of equilibria where agents collude to "relabel" the signals and tell the truth after relabeling signals; (2) provide a mechanism that has no information about the common prior but where truth-telling pays as much in expectation as any relabeling equilibrium and pays strictly more than any other symmetric equilibrium; (3) moreover in our mechanism, if the number of agents is sufficiently large, truth-telling pays similarly to any equilibrium close to a "relabeling" equilibrium and pays strictly more than any equilibrium that is not close to a relabeling equilibrium.
Nonnegative Rank vs. Binary Rank
Venue: arXiv cs.CC 2016
Year: 2016

Motivated by (and using tools from) communication complexity, we investigate the relationship between the following two ranks of a $0$-$1$ matrix: its nonnegative rank and its binary rank (the $\log$ of the latter being the unambiguous nondeterministic communication complexity). We prove that for partial $0$-$1$ matrices, there can be an exponential separation. For total $0$-$1$ matrices, we show that if the nonnegative rank is at most $3$ then the two ranks are equal, and we show a separation by exhibiting a matrix with nonnegative rank $4$ and binary rank $5$, as well as a family of matrices for which the binary rank is $4/3$ times the nonnegative rank.
An Effective Unconstrained Correlation Filter and Its Kernelization for Face Recognition
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, an effective unconstrained correlation filter called Uncon- strained Optimal Origin Tradeoff Filter (UOOTF) is presented and applied to robust face recognition. Compared with the conventional correlation filters in Class-dependence Feature Analysis (CFA), UOOTF improves the overall performance for unseen patterns by removing the hard constraints on the origin correlation outputs during the filter design. To handle non-linearly separable distributions between different classes, we further develop a non- linear extension of UOOTF based on the kernel technique. The kernel ex- tension of UOOTF allows for higher flexibility of the decision boundary due to a wider range of non-linearity properties. Experimental results demon- strate the effectiveness of the proposed unconstrained correlation filter and its kernelization in the task of face recognition.
Privacy-Preserved Big Data Analysis Based on Asymmetric Imputation Kernels and Multiside Similarities
Venue: arXiv cs.LG 2016
Year: 2016

This study presents an efficient approach for incomplete data classification, where the entries of samples are missing or masked due to privacy preservation. To deal with these incomplete data, a new kernel function with asymmetric intrinsic mappings is proposed in this study. Such a new kernel uses three-side similarities for kernel matrix formation. The similarity between a testing instance and a training sample relies not only on their distance but also on the relation between the testing sample and the centroid of the class, where the training sample belongs. This reduces biased estimation compared with typical methods when only one training sample is used for kernel matrix formation. Furthermore, centroid generation does not involve any clustering algorithms. The proposed kernel is capable of performing data imputation by using class-dependent averages. This enhances Fisher Discriminant Ratios and data discriminability. Experiments on two open databases were carried out for evaluating the proposed method. The result indicated that the accuracy of the proposed method was higher than that of the baseline. These findings thereby demonstrated the effectiveness of the proposed idea.
Deep Learning At Scale and At Ease
Venue: arXiv cs.LG 2016
Year: 2016

Recently, deep learning techniques have enjoyed success in various multimedia applications, such as image classification and multi-modal data analysis. Large deep learning models are developed for learning rich representations of complex data. There are two challenges to overcome before deep learning can be widely adopted in multimedia and other applications. One is usability, namely the implementation of different models and training algorithms must be done by non-experts without much effort especially when the model is large and complex. The other is scalability, that is the deep learning system must be able to provision for a huge demand of computing resources for training large models with massive datasets. To address these two challenges, in this paper, we design a distributed deep learning platform called SINGA which has an intuitive programming model based on the common layer abstraction of deep learning models. Good scalability is achieved through flexible distributed training architecture and specific optimization techniques. SINGA runs on GPUs as well as on CPUs, and we show that it outperforms many other state-of-the-art deep learning systems. Our experience with developing and training deep learning models for real-life multimedia applications in SINGA shows that the platform is both usable and scalable.
A Novel Biologically Mechanism-Based Visual Cognition Model--Automatic Extraction of Semantics, Formation of Integrated Concepts and Re-selection Features for Ambiguity
Venue: arXiv cs.CV 2016
Year: 2016

Integration between biology and information science benefits both fields. Many related models have been proposed, such as computational visual cognition models, computational motor control models, integrations of both and so on. In general, the robustness and precision of recognition is one of the key problems for object recognition models. In this paper, inspired by features of human recognition process and their biological mechanisms, a new integrated and dynamic framework is proposed to mimic the semantic extraction, concept formation and feature re-selection in human visual processing. The main contributions of the proposed model are as follows: (1) Semantic feature extraction: Local semantic features are learnt from episodic features that are extracted from raw images through a deep neural network; (2) Integrated concept formation: Concepts are formed with local semantic information and structural information learnt through network. (3) Feature re-selection: When ambiguity is detected during recognition process, distinctive features according to the difference between ambiguous candidates are re-selected for recognition. Experimental results on hand-written digits and facial shape dataset show that, compared with other methods, the new proposed model exhibits higher robustness and precision for visual recognition, especially in the condition when input samples are smantic ambiguous. Meanwhile, the introduced biological mechanisms further strengthen the interaction between neuroscience and information science.
A Subdivision Solver for Systems of Large Dense Polynomials
Venue: arXiv cs.MS 2016
Year: 2016

We describe here the package {\tt subdivision\\_solver} for the mathematical software {\tt SageMath}. It provides a solver on real numbers for square systems of large dense polynomials. By large polynomials we mean multivariate polynomials with large degrees, which coefficients have large bit-size. While staying robust, symbolic approaches to solve systems of polynomials see their performances dramatically affected by high degree and bit-size of input polynomials.Available numeric approaches suffer from the cost of the evaluation of large polynomials and their derivatives.Our solver is based on interval analysis and bisections of an initial compact domain of $\R^n$ where solutions are sought. Evaluations on intervals with Horner scheme is performed by the package {\tt fast\\_polynomial} for {\tt SageMath}.The non-existence of a solution within a box is certified by an evaluation scheme that uses a Taylor expansion at order 2, and existence and uniqueness of a solution within a box is certified with krawczyk operator.The precision of the working arithmetic is adapted on the fly during the subdivision process and we present a new heuristic criterion to decide if the arithmetic precision has to be increased.
Power, Delay and Area Comparisons of Majority Voters relevant to TMR Architectures
Venue: arXiv cs.AR 2016
Year: 2016

N-modular redundancy (NMR) is commonly used to enhance the fault tolerance of a circuit/system, when subject to a fault-inducing environment such as in space or military systems, where upsets due to radiation phenomena, temperature and/or other environmental conditions are anticipated. Triple Modular Redundancy (TMR), which is a 3-tuple version of NMR, is widely preferred for mission-control space, military, and aerospace, and safety-critical nuclear, power, medical, and industrial control and automation systems. The TMR scheme involves the two-times duplication of a simplex system hardware, with a majority voter ensuring correctness provided at least two out of three copies of the hardware remain operational. Thus the majority voter plays a pivotal role in ensuring the correct operation of the TMR scheme. In this paper, a number of standard-cell based majority voter designs relevant to TMR architectures are presented, and their power, delay and area parameters are estimated based on physical realization using a 32/28nm CMOS process.
Experimental Analysis of Algorithms for Coflow Scheduling
Venue: arXiv cs.NI 2016
Year: 2016

Modern data centers face new scheduling challenges in optimizing job-level performance objectives, where a significant challenge is the scheduling of highly parallel data flows with a common performance goal (e.g., the shuffle operations in MapReduce applications). Chowdhury and Stoica introduced the coflow abstraction to capture these parallel communication patterns, and Chowdhury et al. proposed effective heuristics to schedule coflows efficiently. In our previous paper, we considered the strongly NP-hard problem of minimizing the total weighted completion time of coflows with release dates, and developed the first polynomial-time scheduling algorithms with O(1)-approximation ratios. In this paper, we carry out a comprehensive experimental analysis on a Facebook trace and extensive simulated instances to evaluate the practical performance of several algorithms for coflow scheduling, including the approximation algorithms developed in our previous paper. Our experiments suggest that simple algorithms provide effective approximations of the optimal, and that the performance of our approximation algorithms is relatively robust, near optimal, and always among the best compared with the other algorithms, in both the offline and online settings.
Networked Constrained Cyber-Physical Systems subject to malicious attacks: a resilient set-theoretic control approach
Venue: arXiv cs.SY 2016
Year: 2016

In this paper a novel set-theoretic control framework for Networked Constrained Cyber-Physical Systems is presented. By resorting to set-theoretic ideas and the physical watermarking concept, an anomaly detector module and a control remediation strategy are formally derived with the aim to contrast severe cyber attacks affecting the communication channels. The resulting scheme ensures Uniformly Ultimate Boundedness and constraints fulfillment regardless of any admissible attack scenario. Simulation results show the effectiveness of the proposed strategy both against Denial of Service and False Data Injection attacks.
Modeling and Resource Allocation for HD Videos over WiMAX Broadband Wireless Networks
Venue: arXiv cs.NI 2016
Year: 2016

Mobile video is considered a major upcoming application and revenue generator for broadband wireless networks like WiMAX and LTE. Therefore, it is important to design a proper resource allocation scheme for mobile video, since video traffic is both throughput consuming and delay sensitive.
Sensor Deployment with Limited Communication Range in Homogeneous and Heterogeneous Wireless Sensor Networks
Venue: arXiv cs.NI 2016
Year: 2016

We study the heterogeneous wireless sensor networks (WSNs) and propose the necessary condition of the optimal sensor deployment. Similar to that in homogeneous WSNs, the necessary condition implies that every sensor node location should coincide with the centroid of its own optimal sensing region. Moreover, we discuss the dynamic sensor deployment in both homogeneous and heterogeneous WSNs with limited communication range for the sensor nodes. The purpose of sensor deployment is to improve sensing performance, reflected by distortion and coverage. We model the sensor deployment problem as a source coding problem with distortion reflecting sensing accuracy. Traditionally, coverage is the area covered by the sensor nodes. However, when the communication range is limited, a WSN may be divided into several disconnected sub-graphs. Under such a scenario, neither the conventional distortion nor the coverage represents the sensing performance as the collected data in disconnected sub-graphs cannot be communicated with the access point. By defining an appropriate distortion measure, we propose a Restrained Lloyd (RL) algorithm and a Deterministic Annealing (DA) algorithm to optimize sensor deployment in both homogeneous and heterogeneous WSNs. Our simulation results show that both DA and RL algorithms outperform the existing Lloyd algorithm when communication range is limited.
Survivability in IP over WDM networks
Venue: arXiv cs.NI 2016
Year: 2016

The Internet is emerging as the new universal telecommunication medium. IP over WDM has been envisioned as one of the most attractive architectures for the new Internet. Consequently survivability is a crucial concern in designing IP over WDM networks. This paper presents a survey of the survivability mechanisms for IP over WDM networks and thus is intended to provide a summary of what has been done in this area and help further research. A number of optical layer protection techniques have been discussed. They are examined from the point of view of cost, complexity, and application. Survivability techniques are being made available at multiple layers of the network. This paper also studies the recovery features of each network layer and explains the impact of interaction between layers on survivability. The advantages and issues of multi-layer survivability have been identified. The main idea is that the optical layer can provide fast protection while the higher layers can provide intelligent restoration. With this idea in mind, a new scheme of carrying IP over WDM using MPLS or Multi Protocol Lambda-Switching has been discussed. Finally, an architecture is suggested by means of which the optical layer can perform an automatic protection switch, with priority considerations with the help of signaling from the higher layers.
Achieving QoS for TCP Traffic in Satellite Networks with Differentiated Services
Venue: arXiv cs.NI 2016
Year: 2016

Satellite networks play an indispensable role in providing global Internet access and electronic connectivity. To achieve such a global communications, provisioning of quality of service (QoS) within the advanced satellite systems is the main requirement. One of the key mechanisms of implementing the quality of service is traffic management. Traffic management becomes a crucial factor in the case of satellite network because of the limited availability of their resources. Currently, Internet Protocol (IP) only has minimal traffic management capabilities and provides best effort services. In this paper, we present broadband satellite network QoS model and simulated performance results. In particular, we discuss the TCP flow aggregates performance for their good behavior in the presence of competing UDP flow aggregates in the same assured forwarding. We identify several factors that affect the performance in the mixed environments and quantify their effects using a full factorial design of experiment methodology.
"Did I Say Something Wrong?" A Word-Level Analysis of Wikipedia Articles for Deletion Discussions
Venue: arXiv cs.CL 2016
Year: 2016

This thesis focuses on gaining linguistic insights into textual discussions on a word level. It was of special interest to distinguish messages that constructively contribute to a discussion from those that are detrimental to them. Thereby, we wanted to determine whether "I"- and "You"-messages are indicators for either of the two discussion styles. These messages are nowadays often used in guidelines for successful communication. Although their effects have been successfully evaluated multiple times, a large-scale analysis has never been conducted. Thus, we used Wikipedia Articles for Deletion (short: AfD) discussions together with the records of blocked users and developed a fully automated creation of an annotated data set. In this data set, messages were labelled either constructive or disruptive. We applied binary classifiers to the data to determine characteristic words for both discussion styles. Thereby, we also investigated whether function words like pronouns and conjunctions play an important role in distinguishing the two. We found that "You"-messages were a strong indicator for disruptive messages which matches their attributed effects on communication. However, we found "I"-messages to be indicative for disruptive messages as well which is contrary to their attributed effects. The importance of function words could neither be confirmed nor refuted. Other characteristic words for either communication style were not found. Yet, the results suggest that a different model might represent disruptive and constructive messages in textual discussions better.
On Fast Bilateral Filtering using Fourier Kernels
Venue: arXiv cs.CV 2016
Year: 2016

It was demonstrated in earlier work that, by approximating its range kernel using shiftable functions, the non-linear bilateral filter can be computed using a series of fast convolutions. Previous approaches based on shiftable approximation have, however, been restricted to Gaussian range kernels. In this work, we propose a novel approximation that can be applied to any range kernel, provided it has a pointwise-convergent Fourier series. More specifically, we propose to approximate the Gaussian range kernel of the bilateral filter using a Fourier basis, where the coefficients of the basis are obtained by solving a series of least-squares problems. The coefficients can be efficiently computed using a recursive form of the QR decomposition. By controlling the cardinality of the Fourier basis, we can obtain a good tradeoff between the run-time and the filtering accuracy. In particular, we are able to guarantee sub-pixel accuracy for the overall filtering, which is not provided by most existing methods for fast bilateral filtering. We present simulation results to demonstrate the speed and accuracy of the proposed algorithm.
On Clutter Ranks of Frequency Diverse Radar Waveforms
Venue: arXiv cs.IT 2016
Year: 2016

Frequency diverse (FD) radar waveforms are attractive in radar research and practice. By combining two typical FD waveforms, the frequency diverse array (FDA) and the stepped-frequency (SF) pulse train, we propose a general FD waveform model, termed the random frequency diverse multi-input-multi-output (RFD-MIMO) in this paper. The new model can be applied to specific FD waveforms by adapting parameters. Furthermore, by exploring the characteristics of the clutter covariance matrix, we provide an approach to evaluate the clutter rank of the RFD-MIMO radar, which can be adopted as a quantitive metric for the clutter suppression potentials of FD waveforms. Numerical simulations show the effectiveness of the clutter rank estimation method, and reveal helpful results for comparing the clutter suppression performance of different FD waveforms.
Generating reversible circuits from higher-order functional programs
Venue: arXiv cs.LO 2016
Year: 2016

Boolean reversible circuits are boolean circuits made of reversible elementary gates. Despite their constrained form, they can simulate any boolean function. The synthesis and validation of a reversible circuit simulating a given function is a difficult problem. In 1973, Bennett proposed to generate reversible circuits from traces of execution of Turing machines. In this paper, we propose a novel presentation of this approach, adapted to higher-order programs. Starting with a PCF-like language, we use a monadic representation of the trace of execution to turn a regular boolean program into a circuit-generating code. We show that a circuit traced out of a program computes the same boolean function as the original program. This technique has been successfully applied to generate large oracles with the quantum programming language Quipper.
Timed Automata Approach for Motion Planning Using Metric Interval Temporal Logic
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we consider the robot motion (or task) planning problem under some given time bounded high level specifications. We use metric interval temporal logic (MITL), a member of the temporal logic family, to represent the task specification and then we provide a constructive way to generate a timed automaton and methods to look for accepting runs on the automaton to find a feasible motion (or path) sequence for the robot to complete the task.
Semirings for temporal network analysis
Venue: arXiv cs.SI 2016
Year: 2016

In the article, we describe a new algebraic approach to the temporal network analysis based on the notion of temporal quantities. We define the semiring for computing the foremost journey and the traveling semirings for the analysis of temporal networks where the latency is given, the waiting times are arbitrary, and some other information on the links are known. We use the operations in the traveling semiring to compute a generalized temporal betweenness centrality of the nodes that corresponds to the importance of the nodes with respect to the ubiquitous foremost journeys in a temporal network.