OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Deep Q-Learning
Venue: arXiv cs.LG 2015
Year: 2015

We propose a distributed deep learning model to successfully learn control policies directly from high-dimensional sensory input using reinforcement learning. The model is based on the deep Q-network, a convolutional neural network trained with a variant of Q-learning. Its input is raw pixels and its output is a value function estimating future rewards from taking an action given a system state. To distribute the deep Q-network training, we adapt the DistBelief software framework to the context of efficiently training reinforcement learning agents. As a result, the method is completely asynchronous and scales well with the number of machines. We demonstrate that the deep Q-network agent, receiving only the pixels and the game score as inputs, was able to achieve reasonable success on a simple game with minimal parameter tuning.
Second-Order Region for Gray-Wyner Network
Venue: arXiv cs.IT 2015
Year: 2015

The coding problem over the Gray-Wyner network is studied from the second-order coding rates perspective. A tilted information density for this network is introduced in the spirit of Kostina-Verdú, and, under a certain regularity condition, the second-order region is characterized in terms of the variance of this tilted information density and the tangent vector of the first-order region. The second-order region is proved by the type method: the achievability part is proved by the type-covering argument, and the converse part is proved by a refinement of the perturbation approach that was used by Gu-Effros to show the strong converse of the Gray-Wyner network. This is the first instance that the second-order region is characterized for a multi-terminal problem where the characterization of the first-order region involves an auxiliary random variable.
Superposition Coding is Almost Always Optimal for the Poisson Broadcast Channel
Venue: arXiv cs.IT 2015
Year: 2015

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton's inner bound and the UV outer bound.
Exploring Metaphorical Senses and Word Representations for Identifying Metonyms
Venue: arXiv cs.CL 2015
Year: 2015

A metonym is a word with a figurative meaning, similar to a metaphor. Because metonyms are closely related to metaphors, we apply features that are used successfully for metaphor recognition to the task of detecting metonyms. On the ACL SemEval 2007 Task 8 data with gold standard metonym annotations, our system achieved 86.45% accuracy on the location metonyms. Our code can be found on GitHub.
Recognizing Extended Spatiotemporal Expressions by Actively Trained Average Perceptron Ensembles
Venue: arXiv cs.CL 2015
Year: 2015

Precise geocoding and time normalization for text requires that location and time phrases be identified. Many state-of-the-art geoparsers and temporal parsers suffer from low recall. Categories commonly missed by parsers are: nouns used in a non- spatiotemporal sense, adjectival and adverbial phrases, prepositional phrases, and numerical phrases. We collected and annotated data set by querying commercial web searches API with such spatiotemporal expressions as were missed by state-of-the- art parsers. Due to the high cost of sentence annotation, active learning was used to label training data, and a new strategy was designed to better select training examples to reduce labeling cost. For the learning algorithm, we applied an average perceptron trained Featurized Hidden Markov Model (FHMM). Five FHMM instances were used to create an ensemble, with the output phrase selected by voting. Our ensemble model was tested on a range of sequential labeling tasks, and has shown competitive performance. Our contributions include (1) an new dataset annotated with named entities and expanded spatiotemporal expressions; (2) a comparison of inference algorithms for ensemble models showing the superior accuracy of Belief Propagation over Viterbi Decoding; (3) a new example re-weighting method for active ensemble learning that 'memorizes' the latest examples trained; (4) a spatiotemporal parser that jointly recognizes expanded spatiotemporal expressions as well as named entities.
Personalized QoS Prediction of Cloud Services via Learning Neighborhood-based Model
Venue: arXiv cs.DC 2015
Year: 2015

The explosion of cloud services on the Internet brings new challenges in service discovery and selection. Particularly, the demand for efficient quality-of-service (QoS) evaluation is becoming urgently strong. To address this issue, this paper proposes neighborhood-based approach for QoS prediction of cloud services by taking advantages of collaborative intelligence. Different from heuristic collaborative filtering and matrix factorization, we define a formal neighborhood-based prediction framework which allows an efficient global optimization scheme, and then exploit different baseline estimate component to improve predictive performance. To validate the proposed methods, a large-scale QoS-specific dataset which consists of invocation records from 339 service users on 5,825 web services on a world-scale distributed network is used. Experimental results demonstrate that the learned neighborhood-based models can overcome existing difficulties of heuristic collaborative filtering methods and achieve superior performance than state-of-the-art prediction methods.
Proposal for the creation of a research facility for the development of the SP machine
Venue: arXiv cs.AI 2015
Year: 2015

This is a proposal to create a research facility for the development of a high-parallel version of the "SP machine", based on the "SP theory of intelligence". We envisage that the new version of the SP machine will be an open-source software virtual machine, derived from the existing "SP computer model", and hosted on an existing high-performance computer. It will be a means for researchers everywhere to explore what can be done with the system and to create new versions of it. The SP system is a unique attempt to simplify and integrate observations and concepts across artificial intelligence, mainstream computing, mathematics, and human perception and cognition, with information compression as a unifying theme. Potential benefits and applications include helping to solve problems associated with big data; facilitating the development of autonomous robots; unsupervised learning, natural language processing, several kinds of reasoning, fuzzy pattern recognition at multiple levels of abstraction, computer vision, best-match and semantic forms of information retrieval, software engineering, medical diagnosis, simplification of computing systems, and the seamless integration of diverse kinds of knowledge and diverse aspects of intelligence. Additional motivations include the potential of the SP system to help solve problems in defence, security, and the detection and prevention of crime; potential in terms of economic, social, environmental, and academic criteria, and in terms of publicity; and the potential for international influence in research. The main elements of the proposed facility are described, including support for the development of "SP-neural", a neural version of the SP machine. The facility should be permanent in the sense that it should be available for the foreseeable future, and it should be designed to facilitate its use by researchers anywhere in the world.
On the Computation Power of Name Parameterization in Higher-order Processes
Venue: arXiv cs.LO 2015
Year: 2015

Parameterization extends higher-order processes with the capability of abstraction (akin to that in lambda-calculus), and is known to be able to enhance the expressiveness. This paper focuses on the parameterization of names, i.e. a construct that maps a name to a process, in the higher-order setting. We provide two results concerning its computation capacity. First, name parameterization brings up a complete model, in the sense that it can express an elementary interactive model with built-in recursive functions. Second, we compare name parameterization with the well-known pi-calculus, and provide two encodings between them.
Deductive Verification of Parallel Programs Using Why3
Venue: arXiv cs.PL 2015
Year: 2015

The Message Passing Interface specification (MPI) defines a portable message-passing API used to program parallel computers. MPI programs manifest a number of challenges on what concerns correctness: sent and expected values in communications may not match, resulting in incorrect computations possibly leading to crashes; and programs may deadlock resulting in wasted resources. Existing tools are not completely satisfactory: model-checking does not scale with the number of processes; testing techniques wastes resources and are highly dependent on the quality of the test set. As an alternative, we present a prototype for a type-based approach to programming and verifying MPI like programs against protocols. Protocols are written in a dependent type language designed so as to capture the most common primitives in MPI, incorporating, in addition, a form of primitive recursion and collective choice. Protocols are then translated into Why3, a deductive software verification tool. Source code, in turn, is written in WhyML, the language of the Why3 platform, and checked against the protocol. Programs that pass verification are guaranteed to be communication safe and free from deadlocks. We verified several parallel programs from textbooks using our approach, and report on the outcome.
Efficient Computation of Exact IRV Margins
Venue: arXiv cs.AI 2015
Year: 2015

The margin of victory is easy to compute for many election schemes but difficult for Instant Runoff Voting (IRV). This is important because arguments about the correctness of an election outcome usually rely on the size of the electoral margin. For example, risk-limiting audits require a knowledge of the margin of victory in order to determine how much auditing is necessary. This paper presents a practical branch-and-bound algorithm for exact IRV margin computation that substantially improves on the current best-known approach. Although exponential in the worst case, our algorithm runs efficiently in practice on all the real examples we could find. We can efficiently discover exact margins on election instances that cannot be solved by the current state-of-the-art.
Semi-supervised Learning with Regularized Laplacian
Venue: arXiv cs.LG 2015
Year: 2015

We study a semi-supervised learning method based on the similarity graph and RegularizedLaplacian. We give convenient optimization formulation of the Regularized Laplacian method and establishits various properties. In particular, we show that the kernel of the methodcan be interpreted in terms of discrete and continuous time random walks and possesses several importantproperties of proximity measures. Both optimization and linear algebra methods can be used for efficientcomputation of the classification functions. We demonstrate on numerical examples that theRegularized Laplacian method is competitive with respect to the other state of the art semi-supervisedlearning methods.
Generalized Independent Component Analysis Over Finite Alphabets
Venue: arXiv cs.IT 2015
Year: 2015

Independent component analysis (ICA) is a statistical method for transforming an observable multidimensional random vector into components that are as statistically independent as possible from each other.Usually the ICA framework assumes a model according to which the observations are generated (such as a linear transformation with additive noise). ICA over finite fields is a special case of ICA in which both the observations and the independent components are over a finite alphabet. In this work we consider a generalization of this framework in which an observation vector is decomposed to its independent components (as much as possible) with no prior assumption on the way it was generated. This generalization is also known as Barlow's minimal redundancy representation problem and is considered an open problem. We propose several theorems and show that this NP hard problem can be accurately solved with a branch and bound search tree algorithm, or tightly approximated with a series of linear problems. Our contribution provides the first efficient and constructive set of solutions to Barlow's problem.The minimal redundancy representation (also known as factorial code) has many applications, mainly in the fields of Neural Networks and Deep Learning. The Binary ICA (BICA) is also shown to have applications in several domains including medical diagnosis, multi-cluster assignment, network tomography and internet resource management. In this work we show this formulation further applies to multiple disciplines in source coding such as predictive coding, distributed source coding and coding of large alphabet sources.
High-Contrast Color-Stripe Pattern for Rapid Structured-Light Range Imaging
Venue: arXiv cs.CV 2015
Year: 2015

For structured-light range imaging, color stripes can be used for increasing the number of distinguishable light patterns compared to binary BW stripes. Therefore, an appropriate use of color patterns can reduce the number of light projections and range imaging is achievable in single video frame or in "one shot". On the other hand, the reliability and range resolution attainable from color stripes is generally lower than those from multiply projected binary BW patterns since color contrast is affected by object color reflectance and ambient light. This paper presents new methods for selecting stripe colors and designing multiple-stripe patterns for "one-shot" and "two-shot" imaging. We show that maximizing color contrast between the stripes in one-shot imaging reduces the ambiguities resulting from colored object surfaces and limitations in sensor/projector resolution. Two-shot imaging adds an extra video frame and maximizes the color contrast between the first and second video frames to diminish the ambiguities even further. Experimental results demonstrate the effectiveness of the presented one-shot and two-shot color-stripe imaging schemes.
Participatory Sensing for Government-Centric Applications: A Singapore Case Study
Venue: arXiv cs.CY 2015
Year: 2015

Singapore, an urbanized and populated country with high penetration of smartphones, provides an excellent base for citizen-centric participatory sensing applications. Mobile participatory sensing applications offer an efficient means of directing feedback to government agencies for timely identifying and solving problems of citizens' concern. While real deployments of such applications are on an uprising trend in Singapore, there is no concerted effort that studies the {\em user experience} of these applications. To fill this gap, we conduct a market study by analyzing the user reviews on the Google Play and Apple App Store for six major mobile crowdsourcing applications created by Singapore government agencies. This study was carried out for a period of 4 months during which we collected and analyzed 592 customer reviews. This was also supplemented by our personal use of the applications during the same period. This paper presents the methodology and findings of this study, as well as our recommendations of what improvements that these applications could incorporate. We classify user reviews into 8 major concerns, and recommend 9 features to enhance the applications' utility. The recommendations are presented in terms of user interface, incentive, and publicity.
Cultures in Community Question Answering
Venue: arXiv cs.SI 2015
Year: 2015

CQA services are collaborative platforms where users ask and answer questions. We investigate the influence of national culture on people's online questioning and answering behavior. For this, we analyzed a sample of 200 thousand users in Yahoo Answers from 67 countries. We measure empirically a set of cultural metrics defined in Geert Hofstede's cultural dimensions and Robert Levine's Pace of Life and show that behavioral cultural differences exist in community question answering platforms. We find that national cultures differ in Yahoo Answers along a number of dimensions such as temporal predictability of activities, contribution-related behavioral patterns, privacy concerns, and power inequality.
A characterization of a class of optimal three-weight cyclic codes of dimension 3 over any finite field
Venue: arXiv cs.IT 2015
Year: 2015

It is well known that the problem of determining the weight distributions of families of cyclic codes is, in general, notoriously difficult. An even harder problem is to find characterizations of families of cyclic codes in terms of their weight distributions. On the other hand, it is also well known that cyclic codes with few weights have a great practical importance in coding theory and cryptography. In particular, cyclic codes having three nonzero weights have been studied by several authors, however, most of these efforts focused on cyclic codes over a prime field. In this work we present a characterization of a class of optimal three-weight cyclic codes of dimension 3 over any finite field. The codes under this characterization are, indeed, optimal in the sense that their lengths reach the Griesmer lower bound for linear codes. Consequently, these codes reach, simultaneously, the best possible coding capacity, and also the best possible capabilities of error detection and correction for linear codes. But because they are cyclic in nature, they also possess a rich algebraic structure that can be utilized in a variety of ways, particularly, in the design of very efficient coding and decoding algorithms. What is also worth pointing out, is the simplicity of the necessary and sufficient numerical conditions that characterize our class of optimal three-weight cyclic codes. As we already pointed out, it is a hard problem to find this kind of characterizations. However, for this particular case the fundamental tool that allowed us to find our characterization was the characterization for all two-weight irreducible cyclic codes that was introduced by B. Schmidt and C. White (2002). Lastly, another feature about the codes in this class, is that their duals seem to have always the same parameters as the best known linear codes.
How Many Small Cells Can Be Turned off via Vertical Offloading under a Separation Architecture?
Venue: arXiv cs.NI 2015
Year: 2015

To further improve the energy efficiency of heterogeneous networks, a separation architecture called hyper-cellular network (HCN) has been proposed, which decouples the control signaling and data transmission functions. Specifically, the control coverage is guaranteed by macro base stations (MBSs), whereas small cells (SCs) are only utilized for data transmission. Under HCN, SCs can be dynamically turned off when traffic load decreases for energy saving. A fundamental problem then arises: how many SCs can be turned off as traffic varies? In this paper, we address this problem in a theoretical way, where two sleeping schemes (i.e., random and repulsive schemes) with vertical inter-layer offloading are considered. Analytical results indicate the following facts: (1) Under the random scheme where SCs are turned off with certain probability, the expected ratio of sleeping SCs is inversely proportional to the traffic load of SC-layer and decreases linearly with the traffic load of MBS-layer; (2) The repulsive scheme, which only turns off the SCs close to MBSs, is less sensitive to the traffic variations; (3) deploying denser MBSs enables turning off more SCs, which may help to improve network energy-efficiency. Numerical results show that about 50% SCs can be turned off on average under the predefined daily traffic profiles, and 10% more SCs can be further turned off with inter-layer channel borrowing.
Simple Text Mining for Sentiment Analysis of Political Figure Using Naive Bayes Classifier Method
Venue: arXiv cs.CL 2015
Year: 2015

Text mining can be applied to many fields. One of the application is using text mining in digital newspaper to do politic sentiment analysis. In this paper sentiment analysis is applied to get information from digital news articles about its positive or negative sentiment regarding particular politician. This paper suggests a simple model to analyze digital newspaper sentiment polarity using naive Bayes classifier method. The model uses a set of initial data to begin with which will be updated when new information appears. The model showed promising result when tested and can be implemented to some other sentiment analysis problems.
A Case Study on Covert Channel Establishment via Software Caches in High-Assurance Computing Systems
Venue: arXiv cs.CR 2015
Year: 2015

Covert channels can be utilized to secretly deliver information from high privileged processes to low privileged processes in the context of a high-assurance computing system. In this case study, we investigate the possibility of covert channel establishment via software caches in the context of a framework for component-based operating systems. While component-based operating systems offer security through the encapsulation of system service processes, complete isolation of these processes is not reasonably feasible. This limitation is practically demonstrated with our concept of a specific covert timing channel based on file system caching. The stability of the covert channel is evaluated and a methodology to disrupt the covert channel transmission is presented. While these kinds of attacks are not limited to high-assurance computing systems, our study practically demonstrates that even security-focused computing systems with a minimal trusted computing base are vulnerable for such kinds of attacks and careful design decisions are necessary for secure operating system architectures.
Price of Fairness for Allocating a Bounded Resource
Venue: arXiv cs.GT 2015
Year: 2015

In this paper we study the problem of allocating a scarce resource among several players (or agents). A central decision maker wants to maximize the total utility of all agents. However, such a solution may be unfair for one or more agents in the sense that it can be achieved through a very unbalanced allocation of the resource. On the other hand fair/balanced allocations may be far from being optimal from a central point of view. So, in this paper we are interested in assessing the quality of fair solutions, i.e. in measuring the system efficiency loss under a fair allocation compared to the one that maximizes the sum of agents utilities. This indicator is usually called the Price of Fairness and we study it under three different definitions of fairness, namely maximin, Kalai-Smorodinski and proportional fairness. Our results are of two different types. We first formalize a number of properties holding for any general multi-agent problem without any special assumption on the agents utility sets. Then we introduce an allocation problem, where each agent can consume the resource in given discrete quantities (items), such that the maximization of the total utility is given by a Subset Sum Problem. For the resulting Fair Subset Sum Problem, in the case of two agents, we provide upper and lower bounds on the Price of Fairness as functions of an upper bound on the items size.