OpenRaiser/Intern-Atlas huggingface dataset:
Effects of Information Heterogeneity in Bayesian Routing Games
Venue: arXiv cs.GT 2016
Year: 2016

This article studies the value of information in route choice decisions when a fraction of players have access to high accuracy information about traffic incidents relative to others. To model such environments, we introduce a Bayesian congestion game, in which players have private information about incidents, and each player chooses her route on a network of parallel links. The links are prone to incidents that occur with an ex-ante known probability. The demand is comprised of two player populations: one with access to high accuracy incident information and another with low accuracy information, i.e. the populations differ only by their access to information. The common knowledge includes: (i) the demand and route cost functions, (ii) the fraction of highly-informed players, (iii) the incident probability, and (iv) the marginal type distributions induced by the information structure of the game. We present a full characterization of the Bayesian Wardrop Equilibrium of this game under the assumption that low information players receive no additional information beyond common knowledge. We also compute the cost to individual players and the social cost as a function of the fraction of highly-informed players when they receive perfectly accurate information. Our first result suggests that below a certain threshold of highly-informed players, both populations experience a reduction in individual cost, with the highly-informed players receiving a greater reduction. However, above this threshold, both populations realize the same equilibrium cost. Secondly, there exists another (lower or equal) threshold above which a further increase in the fraction of highly-informed players does not reduce the expected social costs. Thus, once a sufficiently large number of players are highly informed, wider distribution of more accurate information is ineffective at best, and otherwise socially harmful.
Algorithms for Batch Hierarchical Reinforcement Learning
Venue: arXiv cs.AI 2016
Year: 2016

Hierarchical Reinforcement Learning (HRL) exploits temporal abstraction to solve large Markov Decision Processes (MDP) and provide transferable subtask policies. In this paper, we introduce an off-policy HRL algorithm: Hierarchical Q-value Iteration (HQI). We show that it is possible to effectively learn recursive optimal policies for any valid hierarchical decomposition of the original MDP, given a fixed dataset collected from a flat stochastic behavioral policy. We first formally prove the convergence of the algorithm for tabular MDP. Then our experiments on the Taxi domain show that HQI converges faster than a flat Q-value Iteration and enjoys easy state abstraction. Also, we demonstrate that our algorithm is able to learn optimal policies for different hierarchical structures from the same fixed dataset, which enables model comparison without recollecting data.
To Observe or Not to Observe: Queuing Game Framework for Urban Parking
Venue: arXiv cs.SY 2016
Year: 2016

We model parking in urban centers as a set of parallel queues and overlay a game theoretic structure that allows us to compare the user-selected (Nash) equilibrium to the socially optimal equilibrium. We model arriving drivers as utility maximizers and consider the game in which observing the queue length is free as well as the game in which drivers must pay to observe the queue length. In both games, drivers must decide between balking and joining. We compare the Nash induced welfare to the socially optimal welfare. We find that gains to welfare do not require full information penetration---meaning, for social welfare to increase, not everyone needs to pay to observe. Through simulation, we explore a more complex scenario where drivers decide based the queueing game whether or not to enter a collection of queues over a network. We examine the occupancy-congestion relationship, an important relationship for determining the impact of parking resources on overall traffic congestion. Our simulated models use parameters informed by real-world data collected by the Seattle Department of Transportation.
Computing Educator Attitudes about Motivation
Venue: arXiv cs.CY 2016
Year: 2016

While motivation is of great interest to computing educators, relatively little work has been done on understanding faculty attitudes toward student motivation. Two previous qualitative studies of instructor attitudes found results identical to those from other disciplines, but neither study considered whether instructors perceive student motivation to be more important in certain computing classes. In this work we present quantitative results about the perceived importance of student motivation in computing courses on the part of computing educators. Our survey results show that while a majority of respondents believe student motivation is necessary in all computing courses, the structure and audience in certain computing classes elevate the importance of student motivation.
Shortest path and maximum flow problems in planar flow networks with additive gains and losses
Venue: arXiv cs.CC 2016
Year: 2016

In contrast to traditional flow networks, in additive flow networks, to every edge e is assigned a gain factor g(e) which represents the loss or gain of the flow while using edge e. Hence, if a flow f(e) enters the edge e and f(e) is less than the designated capacity of e, then f(e) + g(e) = 0 units of flow reach the end point of e, provided e is used, i.e., provided f(e) != 0. In this report we study the maximum flow problem in additive flow networks, which we prove to be NP-hard even when the underlying graphs of additive flow networks are planar. We also investigate the shortest path problem, when to every edge e is assigned a cost value for every unit flow entering edge e, which we show to be NP-hard in the strong sense even when the additive flow networks are planar.
Variable p norm constrained LMS algorithm based on gradient of root relative deviation.pdf
Venue: arXiv cs.SY 2016
Year: 2016

A new Lp-norm constraint least mean square (Lp-LMS) algorithm with new strategy of varying p is presented, which is applied to system identification in this letter. The parameter p is iteratively adjusted by the gradient method applied to the root relative deviation of the estimated weight vector. Numerical simulations show that this new algorithm achieves lower steady-state error as well as equally fast convergence compared with the traditional Lp-LMS and LMS algorithms in the application setting of sparse system identification in the presence of noise.
Towards Geo-Distributed Machine Learning
Venue: arXiv cs.LG 2016
Year: 2016

Latency to end-users and regulatory requirements push large companies to build data centers all around the world. The resulting data is "born" geographically distributed. On the other hand, many machine learning applications require a global view of such data in order to achieve the best results. These types of applications form a new class of learning problems, which we call Geo-Distributed Machine Learning (GDML). Such applications need to cope with: 1) scarce and expensive cross-data center bandwidth, and 2) growing privacy concerns that are pushing for stricter data sovereignty regulations. Current solutions to learning from geo-distributed data sources revolve around the idea of first centralizing the data in one data center, and then training locally. As machine learning algorithms are communication-intensive, the cost of centralizing the data is thought to be offset by the lower cost of intra-data center communication during training. In this work, we show that the current centralized practice can be far from optimal, and propose a system for doing geo-distributed training. Furthermore, we argue that the geo-distributed approach is structurally more amenable to dealing with regulatory constraints, as raw data never leaves the source data center. Our empirical evaluation on three real datasets confirms the general validity of our approach, and shows that GDML is not only possible but also advisable in many scenarios.
Vector Quantization for Machine Vision
Venue: arXiv cs.CV 2016
Year: 2016

This paper shows how to reduce the computational cost for a variety of common machine vision tasks by operating directly in the compressed domain, particularly in the context of hardware acceleration. Pyramid Vector Quantization (PVQ) is the compression technique of choice and its properties are exploited to simplify Support Vector Machines (SVM), Convolutional Neural Networks(CNNs), Histogram of Oriented Gradients (HOG) features, interest points matching and other algorithms.
Trust-Aware Network Utility Optimization in Multihop Wireless Networks with Delay Constraints
Venue: arXiv cs.NI 2016
Year: 2016

Many resource allocation problems can be formulated as a constrained maximization of a utility function. Network Utility Maximization (NUM) applies optimization techniques to achieve decomposition by duality or the primal-dual method. Several important problems, for example joint source rate control, routing, and scheduling design, can be optimized by using this framework. In this work, we introduce an important network security concept, "trust", into the NUM formulation and we integrate nodes' trust values in the optimization framework. These trust values are based on the interaction history between network entities and community based monitoring. Our objective is to avoid routing packets though paths with large percentage of malicious nodes. We also add end-to-end delay constraints for each of the traffic flows. The delay constraints are introduced to capture the quality of service (QoS) requirements imposed to each traffic flow.
Clinical Information Extraction via Convolutional Neural Network
Venue: arXiv cs.LG 2016
Year: 2016

We report an implementation of a clinical information extraction tool that leverages deep neural network to annotate event spans and their attributes from raw clinical notes and pathology reports. Our approach uses context words and their part-of-speech tags and shape information as features. Then we hire temporal (1D) convolutional neural network to learn hidden feature representations. Finally, we use Multilayer Perceptron (MLP) to predict event spans. The empirical evaluation demonstrates that our approach significantly outperforms baselines.
Mutual Dimension and Random Sequences
Venue: arXiv cs.CC 2016
Year: 2016

If $S$ and $T$ are infinite sequences over a finite alphabet, then the lower and upper mutual dimensions $mdim(S:T)$ and $Mdim(S:T)$ are the upper and lower densities of the algorithmic information that is shared by $S$ and $T$. In this paper we investigate the relationships between mutual dimension and coupled randomness, which is the algorithmic randomness of two sequences $R_1$ and $R_2$ with respect to probability measures that may be dependent on one another. For a restricted but interesting class of coupled probability measures we prove an explicit formula for the mutual dimensions $mdim(R_1:R_2)$ and $Mdim(R_1:R_2)$, and we show that the condition $Mdim(R_1:R_2) = 0$ is necessary but not sufficient for $R_1$ and $R_2$ to be independently random. We also identify conditions under which Billingsley generalizations of the mutual dimensions $mdim(S:T)$ and $Mdim(S:T)$ can be meaningfully defined; we show that under these conditions these generalized mutual dimensions have the "correct" relationships with the Billingsley generalizations of $dim(S)$, $Dim(S)$, $dim(T)$, and $Dim(T)$ that were developed and applied by Lutz and Mayordomo; and we prove a divergence formula for the values of these generalized mutual dimensions.
Accurate Text Localization in Natural Image with Cascaded Convolutional Text Network
Venue: arXiv cs.CV 2016
Year: 2016

We introduce a new top-down pipeline for scene text detection. We propose a novel Cascaded Convolutional Text Network (CCTN) that joints two customized convolutional networks for coarse-to-fine text localization. The CCTN fast detects text regions roughly from a low-resolution image, and then accurately localizes text lines from each enlarged region. We cast previous character based detection into direct text region estimation, avoiding multiple bottom- up post-processing steps. It exhibits surprising robustness and discriminative power by considering whole text region as detection object which provides strong semantic information. We customize convolutional network by develop- ing rectangle convolutions and multiple in-network fusions. This enables it to handle multi-shape and multi-scale text efficiently. Furthermore, the CCTN is computationally efficient by sharing convolutional computations, and high-level property allows it to be invariant to various languages and multiple orientations. It achieves 0.84 and 0.86 F-measures on the ICDAR 2011 and ICDAR 2013, delivering substantial improvements over state-of-the-art results [23, 1].
Document Selection in a Distributed Search Engine Architecture
Venue: arXiv cs.IR 2016
Year: 2016

Distributed Search Engine Architecture (DSEA) hosts numerous independent topic-specific search engines and selects a subset of the databases to search within the architecture. The objective of this approach is to reduce the amount of space needed to perform a search by querying only a subset of the total data available. In order to manipulate data across many databases, it is most efficient to identify a smaller subset of databases that would be most likely to return the data of specific interest that can then be examined in greater detail. The selection index has been most commonly used as a method for choosing the most applicable databases as it captures broad information about each database and its indexed documents. Employing this type of database allows the researcher to find information more quickly, not only with less cost, but it also minimizes the potential for biases. This paper investigates the effectiveness of different databases selected within the framework and scope of the distributed search engine architecture. The purpose of the study is to improve the quality of distributed information retrieval.
Exemplar-AMMs: Recognizing Crowd Movements from Pedestrian Trajectories
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present a novel method to recognize the types of crowd movement from crowd trajectories using agent-based motion models (AMMs). Our idea is to apply a number of AMMs, referred to as exemplar-AMMs, to describe the crowd movement. Specifically, we propose an optimization framework that filters out the unknown noise in the crowd trajectories and measures their similarity to the exemplar-AMMs to produce a crowd motion feature. We then address our real-world crowd movement recognition problem as a multi-label classification problem. Our experiments show that the proposed feature outperforms the state-of-the-art methods in recognizing both simulated and real-world crowd movements from their trajectories. Finally, we have created a synthetic dataset, SynCrowd, which contains 2D crowd trajectories in various scenarios, generated by various crowd simulators. This dataset can serve as a training set or benchmark for crowd analysis work.
A ParaBoost Stereoscopic Image Quality Assessment (PBSIQA) System
Venue: arXiv cs.CV 2016
Year: 2016

The problem of stereoscopic image quality assessment, which finds applications in 3D visual content delivery such as 3DTV, is investigated in this work. Specifically, we propose a new ParaBoost (parallel-boosting) stereoscopic image quality assessment (PBSIQA) system. The system consists of two stages. In the first stage, various distortions are classified into a few types, and individual quality scorers targeting at a specific distortion type are developed. These scorers offer complementary performance in face of a database consisting of heterogeneous distortion types. In the second stage, scores from multiple quality scorers are fused to achieve the best overall performance, where the fuser is designed based on the parallel boosting idea borrowed from machine learning. Extensive experimental results are conducted to compare the performance of the proposed PBSIQA system with those of existing stereo image quality assessment (SIQA) metrics. The developed quality metric can serve as an objective function to optimize the performance of a 3D content delivery system.
Verifiability of Argumentation Semantics
Venue: arXiv cs.AI 2016
Year: 2016

Dung's abstract argumentation theory is a widely used formalism to model conflicting information and to draw conclusions in such situations. Hereby, the knowledge is represented by so-called argumentation frameworks (AFs) and the reasoning is done via semantics extracting acceptable sets. All reasonable semantics are based on the notion of conflict-freeness which means that arguments are only jointly acceptable when they are not linked within the AF. In this paper, we study the question which information on top of conflict-free sets is needed to compute extensions of a semantics at hand. We introduce a hierarchy of so-called verification classes specifying the required amount of information. We show that well-known standard semantics are exactly verifiable through a certain such class. Our framework also gives a means to study semantics lying inbetween known semantics, thus contributing to a more abstract understanding of the different features argumentation semantics offer.
On Optimizing Cooperative Cognitive User Performance under Primary QoS Constraints
Venue: arXiv cs.NI 2016
Year: 2016

We study the problem of optimizing the performance of cognitive radio users with opportunistic real-time applications subject to primary users quality-of-service (QoS) constraints. Two constrained optimization problems are formulated; the first problem is maximizing the secondary user throughput while the second problem is minimizing the secondary user average delay, subject to a common constraint on the primary user average delay. In spite of the complexity of the optimization problems, due to their non-convexity, we transform the first problem into a set of linear programs and the second problem into a set of quasiconvex optimization problems. We prove that both problems are equivalent with identical feasible sets and optimal solutions. We show, through numerical results, that the proposed cooperation policy represents the best compromise between enhancing the secondary users QoS and satisfying the primary users QoS requirements.
VapeTracker: Tracking Vapor Consumption to Help E-cigarette Users Quit
Venue: arXiv cs.HC 2016
Year: 2016

Despite current controversy over e-cigarettes as a smoking cessation aid, we present early work based on a web survey (N=249) that shows that some e-cigarette users (46.2%) want to quit altogether, and that behavioral feedback that can be tracked can fulfill that purpose. Based on our survey findings, we designed VapeTracker, an early prototype that can attach to any e-cigarette device to track vaping activity. We discuss our future research on vaping cessation, addressing how to improve our VapeTracker prototype, ambient feedback mechanisms, and the future inclusion of behavior change models to support quitting e-cigarettes.
Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
Venue: arXiv cs.DS 2016
Year: 2016

We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) $k$-median and $k$-means in edge-weighted planar graphs; (3) $k$-means in Euclidean spaces of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the $p$-th power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution $S$ consists of all solutions obtained from $S$ by removing and adding $1/ε^{O(1)}$ centers.
On a special class of boxicity 2 graphs
Venue: arXiv cs.DM 2016
Year: 2016

We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectangle intersection graph where the rectangles have unit height (that is, length of the side parallel to $Y$-axis) and intersects either of the two fixed lines, parallel to the $X$-axis, distance $1+ε$ ($0 < ε< 1$) apart. Intuitively, 2SIG is a graph obtained by putting some edges between two interval graphs in a particular rule. It turns out that for these kind of graphs, the chromatic number of any of its induced subgraphs is bounded by twice of its (induced subgraph) clique number. This shows that the graph, even though not perfect, is not very far from it. Then we prove similar results for some subclasses of 2SIG and provide efficient algorithm for finding their clique number. We provide a matrix characterization for a subclass of 2SIG graph.
Using Alloy to Formally Model and Reason About an OpenFlow Network Switch
Venue: arXiv cs.NI 2016
Year: 2016

Openflow provides a standard interface for separating a network into a data plane and a programmatic control plane. This enables easy network reconfiguration, but introduces the potential for programming bugs to cause network effects. To study OpenFlow switch behavior, we used Alloy to create a software abstraction describing the internal state of a network and its OpenFlow switches. This work is an attempt to model the static and dynamic behaviour a network built using OpenFlow switches.
Variational reaction-diffusion systems for semantic segmentation
Venue: arXiv cs.CV 2016
Year: 2016

A novel global energy model for multi-class semantic image segmentation is proposed that admits very efficient exact inference and derivative calculations for learning. Inference in this model is equivalent to MAP inference in a particular kind of vector-valued Gaussian Markov random field, and ultimately reduces to solving a linear system of linear PDEs known as a reaction-diffusion system. Solving this system can be achieved in time scaling near-linearly in the number of image pixels by reducing it to sequential FFTs, after a linear change of basis. The efficiency and differentiability of the model make it especially well-suited for integration with convolutional neural networks, even allowing it to be used in interior, feature-generating layers and stacked multiple times. Experimental results are shown demonstrating that the model can be employed profitably in conjunction with different convolutional net architectures, and that doing so compares favorably to joint training of a fully-connected CRF with a convolutional net.
Semi-supervised and Unsupervised Methods for Categorizing Posts in Web Discussion Forums
Venue: arXiv cs.CL 2016
Year: 2016

Web discussion forums are used by millions of people worldwide to share information belonging to a variety of domains such as automotive vehicles, pets, sports, etc. They typically contain posts that fall into different categories such as problem, solution, feedback, spam, etc. Automatic identification of these categories can aid information retrieval that is tailored for specific user requirements. Previously, a number of supervised methods have attempted to solve this problem; however, these depend on the availability of abundant training data. A few existing unsupervised and semi-supervised approaches are either focused on identifying a single category or do not report category-specific performance. In contrast, this work proposes unsupervised and semi-supervised methods that require no or minimal training data to achieve this objective without compromising on performance. A fine-grained analysis is also carried out to discuss their limitations. The proposed methods are based on sequence models (specifically, Hidden Markov Models) that can model language for each category using word and part-of-speech probability distributions, and manually specified features. Empirical evaluations across domains demonstrate that the proposed methods are better suited for this task than existing ones.