OpenRaiser/Intern-Atlas huggingface dataset:
Truthful Bilateral Trade is Impossible even with Fixed Prices
Venue: arXiv cs.GT 2017
Year: 2017

A seminal theorem of Myerson and Satterthwaite (1983) proves that, in a game of bilateral trade between a single buyer and a single seller, no mechanism can be simultaneously individually-rational, budget-balanced, incentive-compatible and socially-efficient. However, the impossibility disappears if the price is fixed exogenously and the social-efficiency goal is subject to individual-rationality at the given price. We show that the impossibility comes back if there are multiple units of the same good, or multiple types of goods, even when the prices are fixed exogenously. Particularly, if there are $M$ units of the same good or $M$ kinds of goods, for some $M\geq 2$, then no truthful mechanism can guarantee more than $1/M$ of the optimal gain-from-trade. In the single-good multi-unit case, if both agents have submodular valuations (decreasing marginal returns), then no truthful mechanism can guarantee more than $1/H_M$ of the optimal gain-from-trade, where $H_M$ is the $M$-th harmonic number ($H_M\approx \ln{M}+1/2$). All upper bounds are tight.
Robust Stackelberg Equilibria in Extensive-Form Games and Extension to Limited Lookahead
Venue: arXiv cs.GT 2017
Year: 2017

Stackelberg equilibria have become increasingly important as a solution concept in computational game theory, largely inspired by practical problems such as security settings. In practice, however, there is typically uncertainty regarding the model about the opponent. This paper is, to our knowledge, the first to investigate Stackelberg equilibria under uncertainty in extensive-form games, one of the broadest classes of game. We introduce robust Stackelberg equilibria, where the uncertainty is about the opponent's payoffs, as well as ones where the opponent has limited lookahead and the uncertainty is about the opponent's node evaluation function. We develop a new mixed-integer program for the deterministic limited-lookahead setting. We then extend the program to the robust setting for Stackelberg equilibrium under unlimited and under limited lookahead by the opponent. We show that for the specific case of interval uncertainty about the opponent's payoffs (or about the opponent's node evaluations in the case of limited lookahead), robust Stackelberg equilibria can be computed with a mixed-integer program that is of the same asymptotic size as that for the deterministic setting.
Application of Natural Language Processing to Determine User Satisfaction in Public Services
Venue: arXiv cs.CL 2017
Year: 2017

Research on customer satisfaction has increased substantially in recent years. However, the relative importance and relationships between different determinants of satisfaction remains uncertain. Moreover, quantitative studies to date tend to test for significance of pre-determined factors thought to have an influence with no scalable means to identify other causes of user satisfaction. The gaps in knowledge make it difficult to use available knowledge on user preference for public service improvement. Meanwhile, digital technology development has enabled new methods to collect user feedback, for example through online forums where users can comment freely on their experience. New tools are needed to analyze large volumes of such feedback. Use of topic models is proposed as a feasible solution to aggregate open-ended user opinions that can be easily deployed in the public sector. Generated insights can contribute to a more inclusive decision-making process in public service provision. This novel methodological approach is applied to a case of service reviews of publicly-funded primary care practices in England. Findings from the analysis of 145,000 reviews covering almost 7,700 primary care centers indicate that the quality of interactions with staff and bureaucratic exigencies are the key issues driving user satisfaction across England.
A Quantum-Inspired Ensemble Method and Quantum-Inspired Forest Regressors
Venue: arXiv cs.LG 2017
Year: 2017

We propose a Quantum-Inspired Subspace(QIS) Ensemble Method for generating feature ensembles based on feature selections. We assign each principal component a Fraction Transition Probability as its probability weight based on Principal Component Analysis and quantum interpretations. In order to generate the feature subset for each base regressor, we select a feature subset from principal components based on Fraction Transition Probabilities. The idea originating from quantum mechanics can encourage ensemble diversity and the accuracy simultaneously. We incorporate Quantum-Inspired Subspace Method into Random Forest and propose Quantum-Inspired Forest. We theoretically prove that the quantum interpretation corresponds to the first order approximation of ensemble regression. We also evaluate the empirical performance of Quantum-Inspired Forest and Random Forest in multiple hyperparameter settings. Quantum-Inspired Forest proves the significant robustness of the default hyperparameters on most data sets. The contribution of this work is two-fold, a novel ensemble regression algorithm inspired by quantum mechanics and the theoretical connection between quantum interpretations and machine learning algorithms.
Channel Transition Invariant Fast Broadcasting Scheme
Venue: arXiv cs.MM 2017
Year: 2017

Fast broadcasting (FB) is a popular near video-on-demand system where a video is divided into equal size segments those are repeatedly transmitted over a number of channels following a pattern. For user satisfaction, it is required to reduce the initial user waiting time and client side buffer requirement at streaming. Use of additional channels can achieve the objective. However, some augmentation is required to the basic FB scheme as it lacks any mechanism to realise a well defined relationship among the segment sizes at channel transition. Lack of correspondence between the segments causes intermediate waiting for the clients while watching videos. Use of additional channel requires additional bandwidth. In this paper, we propose a modified FB scheme that achieves zero initial clients waiting time and provides a mechanism to control client side buffer requirement at streaming without requiring additional channels. We present several results to demonstrate the effectiveness of the proposed FB scheme over the existing ones.
(Auto)Focus approaches and their applications: A systematic review
Venue: arXiv cs.SE 2017
Year: 2017

Focus, a framework for formal specification and development of interactive systems, was introduced approx. 25 years ago. Since then this approach was broadly used in academic and industrial studies, as well as provided a basis for a number of another frameworks focusing on particular domains, and for the AF3 modelling tool. In this paper we provide a literature review of the corresponding approaches, academic case studies and industrial applications of these methods.
Quantum-dot Cellular Automata (QCA): A Survey
Venue: arXiv cs.ET 2017
Year: 2017

In the near future the era of Beyond CMOS will start as the scaling of the current CMOS technology will reach the fundamental limit. QCA (Quantum-dot Cellular Automata) is the transistor less computation paradigm and viable candidate for Beyond CMOS device technology. The complete state of art survey on QCA is presented in this paper. This paper addresses the QCA background, its possible implementation and available simulation and synthesis tools. In depth survey is carried out for the QCA oriented defects and testing. Also, need of development and possible research areas in various sides of QCA are discussed.
Ultra-Reliable Short-Packet Communications: Half-Duplex or Full-Duplex Relaying?
Venue: arXiv cs.IT 2017
Year: 2017

This letter analyzes and compares the performance of full-duplex relaying (FDR) and half-duplex relaying (HDR) for ultra-reliable short-packet communications. Specifically, we derive both approximate and asymptotic closed-form expressions of the block error rate (BLER) for FDR and HDR using short packets with finite blocklength codes. We define and attain a closed-form expression of a critical BLER, which can be used to efficiently determine the optimal duplex mode for ultra-reliable low latency communication scenarios. Our results unveil that FDR is more appealing to the system with relatively lower transmit power constraint, less stringent BLER requirement and stronger loop interference suppression.
A correlational analysis of multiagent sensorimotor interactions: clustering autonomous and controllable entities
Venue: arXiv cs.AI 2017
Year: 2017

A first step to reach Theory of Mind (ToM) abilities (attribution of beliefs to others) in synthetic agents through sensorimotor interactions, would be to tag sensory data with agent typology and action intentions: autonomous agent X moved an object under the box. We propose a dual arm robotic setup in which ToM could be probed. We then discuss what measures can be extracted from sensorimotor interaction data (based on a correlation analysis) in the proposed setup that allow to distinguish self than other and other/inanimate from other/active with intentions. We finally discuss what elements are missing in current cognitive architectures to be able to acquire ToM abilities in synthetic agents from sensorimotor interactions, bottom-up from reactive agent interaction behaviors and top-down from the optimization of social behaviour and cooperation.
DeepSign: Deep Learning for Automatic Malware Signature Generation and Classification
Venue: arXiv cs.CR 2017
Year: 2017

This paper presents a novel deep learning based method for automatic malware signature generation and classification. The method uses a deep belief network (DBN), implemented with a deep stack of denoising autoencoders, generating an invariant compact representation of the malware behavior. While conventional signature and token based methods for malware detection do not detect a majority of new variants for existing malware, the results presented in this paper show that signatures generated by the DBN allow for an accurate classification of new malware variants. Using a dataset containing hundreds of variants for several major malware families, our method achieves 98.6% classification accuracy using the signatures generated by the DBN. The presented method is completely agnostic to the type of malware behavior that is logged (e.g., API calls and their parameters, registry entries, websites and ports accessed, etc.), and can use any raw input from a sandbox to successfully train the deep neural network which is used to generate malware signatures.
Genetic Algorithms for Evolving Computer Chess Programs
Venue: arXiv cs.NE 2017
Year: 2017

This paper demonstrates the use of genetic algorithms for evolving: 1) a grandmaster-level evaluation function, and 2) a search mechanism for a chess program, the parameter values of which are initialized randomly. The evaluation function of the program is evolved by learning from databases of (human) grandmaster games. At first, the organisms are evolved to mimic the behavior of human grandmasters, and then these organisms are further improved upon by means of coevolution. The search mechanism is evolved by learning from tactical test suites. Our results show that the evolved program outperforms a two-time world computer chess champion and is at par with the other leading computer chess programs.
From Monte Carlo to Las Vegas: Improving Restricted Boltzmann Machine Training Through Stopping Sets
Venue: arXiv cs.LG 2017
Year: 2017

We propose a Las Vegas transformation of Markov Chain Monte Carlo (MCMC) estimators of Restricted Boltzmann Machines (RBMs). We denote our approach Markov Chain Las Vegas (MCLV). MCLV gives statistical guarantees in exchange for random running times. MCLV uses a stopping set built from the training data and has maximum number of Markov chain steps K (referred as MCLV-K). We present a MCLV-K gradient estimator (LVS-K) for RBMs and explore the correspondence and differences between LVS-K and Contrastive Divergence (CD-K), with LVS-K significantly outperforming CD-K training RBMs over the MNIST dataset, indicating MCLV to be a promising direction in learning generative models.
Fast and Stable Pascal Matrix Algorithms
Venue: arXiv cs.NA 2017
Year: 2017

In this paper, we derive a family of fast and stable algorithms for multiplying and inverting $n \times n$ Pascal matrices that run in $O(n log^2 n)$ time and are closely related to De Casteljau's algorithm for Bézier curve evaluation. These algorithms use a recursive factorization of the triangular Pascal matrices and improve upon the cripplingly unstable $O(n log n)$ fast Fourier transform-based algorithms which involve a Toeplitz matrix factorization. We conduct numerical experiments which establish the speed and stability of our algorithm, as well as the poor performance of the Toeplitz factorization algorithm. As an example, we show how our formulation relates to Bézier curve evaluation.
BILBO-friendly Hybrid BIST Architecture with Asymmetric Polynomial Reseeding
Venue: arXiv cs.AR 2017
Year: 2017

By advances in technology, integrated circuits have come to include more functionality and more complexity in a single chip. Although methods of testing have improved, but the increase in complexity of circuits, keeps testing a challenging problem. Two important challenges in testing of digital circuits are test time and accessing the circuit under test (CUT) for testing. These challenges become even more important in complex system on chip (SoC) zone. This paper presents a multistage test strategy to be implemented on a BIST architecture for reducing test time of a simple core as solution for more global application of SoC testing strategy. This strategy implements its test pattern generation and output response analyzer in a BILBO architecture. The proposed method benefits from an irregular polynomial BILBO (IP-BILBO) structure to improve its test results. Experimental results on ISCAS-89 benchmark circuits show an average of 35% improvement in test time in proportion to pervious work.
Lightweight Fingerprints for Fast Approximate Keyword Matching Using Bitwise Operations
Venue: arXiv cs.DS 2017
Year: 2017

We aim to speed up approximate keyword matching by storing a lightweight, fixed-size block of data for each string, called a fingerprint. These work in a similar way to hash values; however, they can be also used for matching with errors. They store information regarding symbol occurrences using individual bits, and they can be compared against each other with a constant number of bitwise operations. In this way, certain strings can be deduced to be at least within the distance $k$ from each other (using Hamming or Levenshtein distance) without performing an explicit verification. We show experimentally that for a preprocessed collection of strings, fingerprints can provide substantial speedups for $k = 1$, namely over $2.5$ times for the Hamming distance and over $10$ times for the Levenshtein distance. Tests were conducted on synthetic and real-world English and URL data.
A Study on Modeling of Inputting Electrical Power of Ultra High Power Electric Furnace by using Fuzzy Rule and Regression Model
Venue: arXiv cs.SY 2017
Year: 2017

: In this paper a method to make inputting electrical model upon factors that affect melting process of high ultra power(UHP) electric furnace by using fuzzy rule and regression model is suggested and its effectiveness is verified with simulation experiment.
Regularization of Deep Neural Networks with Spectral Dropout
Venue: arXiv cs.CV 2017
Year: 2017

The big breakthrough on the ImageNet challenge in 2012 was partially due to the `dropout' technique used to avoid overfitting. Here, we introduce a new approach called `Spectral Dropout' to improve the generalization ability of deep neural networks. We cast the proposed approach in the form of regular Convolutional Neural Network (CNN) weight layers using a decorrelation transform with fixed basis functions. Our spectral dropout method prevents overfitting by eliminating weak and `noisy' Fourier domain coefficients of the neural network activations, leading to remarkably better results than the current regularization methods. Furthermore, the proposed is very efficient due to the fixed basis functions used for spectral transformation. In particular, compared to Dropout and Drop-Connect, our method significantly speeds up the network convergence rate during the training process (roughly x2), with considerably higher neuron pruning rates (an increase of ~ 30%). We demonstrate that the spectral dropout can also be used in conjunction with other regularization approaches resulting in additional performance gains.
Robust Beamforming for Physical Layer Security in BDMA Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we design robust beamforming to guarantee the physical layer security for a multiuser beam division multiple access (BDMA) massive multiple-input multiple-output (MIMO) system, when the channel estimation errors are taken into consideration. With the aid of artificial noise (AN), the proposed design are formulated as minimizing the transmit power of the base station (BS), while providing legal users and the eavesdropper (Eve) with different signal-to-interference-plus-noise ratio (SINR). It is strictly proved that, under BDMA massive MIMO scheme, the initial non-convex optimization can be equivalently converted to a convex semi-definite programming (SDP) problem and the optimal rank-one beamforming solutions can be guaranteed. In stead of directly resorting to the convex tool, we make one step further by deriving the optimal beamforming direction and the optimal beamforming power allocation in closed-form, which greatly reduces the computational complexity and makes the proposed design practical for real world applications. Simulation results are then provided to verify the efficiency of the proposed algorithm.
Software Development Under Stringent Hardware Constraints: Do Agile Methods Have a Chance?
Venue: arXiv cs.SE 2017
Year: 2017

Agile software development methods have been suggested as useful in many situations and contexts. However, only few (if any) experiences are available regarding the use of agile methods in embedded domain where the hardware sets tight requirements for the software. This development domain is arguably far away from the agile home ground. This paper explores the possibility of using agile development techniques in this environment and defines the requirements for new agile methods targeted to facilitate the development of embedded software. The findings are based on an empirical study over a period 12 months in the development of low-level telecommunications software. We maintain that by addressing the requirements we discovered, agile methods can be successful also in the embedded software domain.
Functorial Semantics for Relational Theories
Venue: arXiv cs.LO 2017
Year: 2017

We introduce the concept of Frobenius theory as a generalisation of Lawvere's functorial semantics approach to categorical universal algebra. Whereas the universe for models of Lawvere theories is the category of sets and functions, or more generally cartesian categories, Frobenius theories take their models in the category of sets and relations, or more generally in cartesian bicategories.
Parallel transport in shape analysis: a scalable numerical scheme
Venue: arXiv cs.CV 2017
Year: 2017

The analysis of manifold-valued data requires efficient tools from Riemannian geometry to cope with the computational complexity at stake. This complexity arises from the always-increasing dimension of the data, and the absence of closed-form expressions to basic operations such as the Riemannian logarithm. In this paper, we adapt a generic numerical scheme recently introduced for computing parallel transport along geodesics in a Riemannian manifold to finite-dimensional manifolds of diffeomorphisms. We provide a qualitative and quantitative analysis of its behavior on high-dimensional manifolds, and investigate an application with the prediction of brain structures progression.
An Overview of Polynomially Computable Characteristics of Special Interval Matrices
Venue: arXiv cs.NA 2017
Year: 2017

It is well known that many problems in interval computation are intractable, which restricts our attempts to solve large problems in reasonable time. This does not mean, however, that all problems are computationally hard. Identifying polynomially solvable classes thus belongs to important current trends. The purpose of this paper is to review some of such classes. In particular, we focus on several special interval matrices and investigate their convenient properties. We consider tridiagonal matrices, {M,H,P,B}-matrices, inverse M-matrices, inverse nonnegative matrices, nonnegative matrices, totally positive matrices and some others. We focus in particular on computing the range of the determinant, eigenvalues, singular values, and selected norms. Whenever possible, we state also formulae for determining the inverse matrix and the hull of the solution set of an interval system of linear equations. We survey not only the known facts, but we present some new views as well.
fpgaConvNet: A Toolflow for Mapping Diverse Convolutional Neural Networks on Embedded FPGAs
Venue: arXiv cs.CV 2017
Year: 2017

In recent years, Convolutional Neural Networks (ConvNets) have become an enabling technology for a wide range of novel embedded Artificial Intelligence systems. Across the range of applications, the performance needs vary significantly, from high-throughput video surveillance to the very low-latency requirements of autonomous cars. In this context, FPGAs can provide a potential platform that can be optimally configured based on the different performance needs. However, the complexity of ConvNet models keeps increasing making their mapping to an FPGA device a challenging task. This work presents fpgaConvNet, an end-to-end framework for mapping ConvNets on FPGAs. The proposed framework employs an automated design methodology based on the Synchronous Dataflow (SDF) paradigm and defines a set of SDF transformations in order to efficiently explore the architectural design space. By selectively optimising for throughput, latency or multiobjective criteria, the presented tool is able to efficiently explore the design space and generate hardware designs from high-level ConvNet specifications, explicitly optimised for the performance metric of interest. Overall, our framework yields designs that improve the performance by up to 6.65x over highly optimised embedded GPU designs for the same power constraints in embedded environments.
Boosted Cascaded Convnets for Multilabel Classification of Thoracic Diseases in Chest Radiographs
Venue: arXiv cs.CV 2017
Year: 2017

Chest X-ray is one of the most accessible medical imaging technique for diagnosis of multiple diseases. With the availability of ChestX-ray14, which is a massive dataset of chest X-ray images and provides annotations for 14 thoracic diseases; it is possible to train Deep Convolutional Neural Networks (DCNN) to build Computer Aided Diagnosis (CAD) systems. In this work, we experiment a set of deep learning models and present a cascaded deep neural network that can diagnose all 14 pathologies better than the baseline and is competitive with other published methods. Our work provides the quantitative results to answer following research questions for the dataset: 1) What loss functions to use for training DCNN from scratch on ChestX-ray14 dataset that demonstrates high class imbalance and label co occurrence? 2) How to use cascading to model label dependency and to improve accuracy of the deep learning model?