OpenRaiser/Intern-Atlas huggingface dataset:
Spectrum Sharing Scheme Between Cellular Users and Ad-hoc Device-to-Device Users
Venue: arXiv cs.NI 2013
Year: 2013

In an attempt to utilize spectrum resources more efficiently, protocols sharing licensed spectrum with unlicensed users are receiving increased attention. From the perspective of cellular networks, spectrum underutilization makes spatial reuse a feasible complement to existing standards. Interference management is a major component in designing these schemes as it is critical that licensed users maintain their expected quality of service. We develop a distributed dynamic spectrum protocol in which ad-hoc device-to-device users opportunistically access the spectrum actively in use by cellular users. First, channel gain estimates are used to set feasible transmit powers for device-to-device users that keeps the interference they cause within the allowed interference temperature. Then network information is distributed by route discovery packets in a random access manner to help establish either a single-hop or multi-hop route between two device-to-device users. We show that network information in the discovery packet can decrease the failure rate of the route discovery and reduce the number of necessary transmissions to find a route. Using the found route, we show that two device-to-device users can communicate with a low probability of outage while only minimally affecting the cellular network, and can achieve significant power savings when communicating directly with each other instead of utilizing the cellular base station.
The Capacity of Adaptive Group Testing
Venue: arXiv cs.IT 2013
Year: 2013

We define capacity for group testing problems and deduce bounds for the capacity of a variety of noisy models, based on the capacity of equivalent noisy communication channels. For noiseless adaptive group testing we prove an information-theoretic lower bound which tightens a bound of Chan et al. This can be combined with a performance analysis of a version of Hwang's adaptive group testing algorithm, in order to deduce the capacity of noiseless and erasure group testing models.
Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable
Venue: arXiv cs.DM 2013
Year: 2013

For graphs of bounded maximum average degree, we consider the problem of 2-distance coloring. This is the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. It is already known that planar graphs of girth at least 6 and of maximum degree D are list 2-distance (D+2)-colorable when D>=24 (Borodin and Ivanova (2009)) and 2-distance (D+2)-colorable when D>=18 (Borodin and Ivanova (2009)). We prove here that D>=17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and D>=17 are list 2-distance (D+2)-colorable. The proof can be transposed to list injective (D+1)-coloring.
Computable Component-wise Reducibility
Venue: arXiv cs.FL 2013
Year: 2013

We consider equivalence relations and preorders complete for various levels of the arithmetical hierarchy under computable, component-wise reducibility. We show that implication in first order logic is a complete preorder for $\SI 1$, the $\le^P_m$ relation on EXPTIME sets for $\SI 2$ and the embeddability of computable subgroups of $(\QQ,+)$ for $\SI 3$. In all cases, the symmetric fragment of the preorder is complete for equivalence relations on the same level. We present a characterisation of $\PI 1$ equivalence relations which allows us to establish that equality of polynomial time functions and inclusion of polynomial time sets are complete for $\PI 1$ equivalence relations and preorders respectively. We also show that this is the limit of the enquiry: for $n\geq 2$ there are no $\PI n$ nor $\DE n$-complete equivalence relations.
Weak Concurrent Kleene Algebra with Application to Algebraic Verification
Venue: arXiv cs.FL 2013
Year: 2013

We propose a generalisation of concurrent Kleene algebra \cite{Hoa09} that can take account of probabilistic effects in the presence of concurrency. The algebra is proved sound with respect to a model of automata modulo a variant of rooted $η$-simulation equivalence. Applicability is demonstrated by algebraic treatments of two examples: algebraic may testing and Rabin's solution to the choice coordination problem.
Bringing Order to Special Cases of Klee's Measure Problem
Venue: arXiv cs.CG 2013
Year: 2013

Klee's Measure Problem (KMP) asks for the volume of the union of n axis-aligned boxes in d-space. Omitting logarithmic factors, the best algorithm has runtime O*(n^{d/2}) [Overmars,Yap'91]. There are faster algorithms known for several special cases: Cube-KMP (where all boxes are cubes), Unitcube-KMP (where all boxes are cubes of equal side length), Hypervolume (where all boxes share a vertex), and k-Grounded (where the projection onto the first k dimensions is a Hypervolume instance). In this paper we bring some order to these special cases by providing reductions among them. In addition to the trivial inclusions, we establish Hypervolume as the easiest of these special cases, and show that the runtimes of Unitcube-KMP and Cube-KMP are polynomially related. More importantly, we show that any algorithm for one of the special cases with runtime T(n,d) implies an algorithm for the general case with runtime T(n,2d), yielding the first non-trivial relation between KMP and its special cases. This allows to transfer W[1]-hardness of KMP to all special cases, proving that no n^{o(d)} algorithm exists for any of the special cases under reasonable complexity theoretic assumptions. Furthermore, assuming that there is no improved algorithm for the general case of KMP (no algorithm with runtime O(n^{d/2 - eps})) this reduction shows that there is no algorithm with runtime O(n^{floor(d/2)/2 - eps}) for any of the special cases. Under the same assumption we show a tight lower bound for a recent algorithm for 2-Grounded [Yildiz,Suri'12].
Learning by Transduction
Venue: arXiv cs.LG 2013
Year: 2013

We describe a method for predicting a classification of an object given classifications of the objects in the training set, assuming that the pairs object/classification are generated by an i.i.d. process from a continuous probability distribution. Our method is a modification of Vapnik's support-vector machine; its main novelty is that it gives not only the prediction itself but also a practicable measure of the evidence found in support of that prediction. We also describe a procedure for assigning degrees of confidence to predictions made by the support vector machine. Some experimental results are presented, and possible extensions of the algorithms are discussed.
Towards Case-Based Preference Elicitation: Similarity Measures on Preference Structures
Venue: arXiv cs.AI 2013
Year: 2013

While decision theory provides an appealing normative framework for representing rich preference structures, eliciting utility or value functions typically incurs a large cost. For many applications involving interactive systems this overhead precludes the use of formal decision-theoretic models of preference. Instead of performing elicitation in a vacuum, it would be useful if we could augment directly elicited preferences with some appropriate default information. In this paper we propose a case-based approach to alleviating the preference elicitation bottleneck. Assuming the existence of a population of users from whom we have elicited complete or incomplete preference structures, we propose eliciting the preferences of a new user interactively and incrementally, using the closest existing preference structures as potential defaults. Since a notion of closeness demands a measure of distance among preference structures, this paper takes the first step of studying various distance measures over fully and partially specified preference structures. We explore the use of Euclidean distance, Spearmans footrule, and define a new measure, the probabilistic distance. We provide computational techniques for all three measures.
Hierarchical Solution of Markov Decision Processes using Macro-actions
Venue: arXiv cs.AI 2013
Year: 2013

We investigate the use of temporally abstract actions, or macro-actions, in the solution of Markov decision processes. Unlike current models that combine both primitive actions and macro-actions and leave the state space unchanged, we propose a hierarchical model (using an abstract MDP) that works with macro-actions only, and that significantly reduces the size of the state space. This is achieved by treating macroactions as local policies that act in certain regions of state space, and by restricting states in the abstract MDP to those at the boundaries of regions. The abstract MDP approximates the original and can be solved more efficiently. We discuss several ways in which macro-actions can be generated to ensure good solution quality. Finally, we consider ways in which macro-actions can be reused to solve multiple, related MDPs; and we show that this can justify the computational overhead of macro-action generation.
Evaluating Las Vegas Algorithms - Pitfalls and Remedies
Venue: arXiv cs.AI 2013
Year: 2013

Stochastic search algorithms are among the most sucessful approaches for solving hard combinatorial problems. A large class of stochastic search approaches can be cast into the framework of Las Vegas Algorithms (LVAs). As the run-time behavior of LVAs is characterized by random variables, the detailed knowledge of run-time distributions provides important information for the analysis of these algorithms. In this paper we propose a novel methodology for evaluating the performance of LVAs, based on the identification of empirical run-time distributions. We exemplify our approach by applying it to Stochastic Local Search (SLS) algorithms for the satisfiability problem (SAT) in propositional logic. We point out pitfalls arising from the use of improper empirical methods and discuss the benefits of the proposed methodology for evaluating and comparing LVAs.
The Lumiere Project: Bayesian User Modeling for Inferring the Goals and Needs of Software Users
Venue: arXiv cs.AI 2013
Year: 2013

The Lumiere Project centers on harnessing probability and utility to provide assistance to computer software users. We review work on Bayesian user models that can be employed to infer a users needs by considering a user's background, actions, and queries. Several problems were tackled in Lumiere research, including (1) the construction of Bayesian models for reasoning about the time-varying goals of computer users from their observed actions and queries, (2) gaining access to a stream of events from software applications, (3) developing a language for transforming system events into observational variables represented in Bayesian user models, (4) developing persistent profiles to capture changes in a user expertise, and (5) the development of an overall architecture for an intelligent user interface. Lumiere prototypes served as the basis for the Office Assistant in the Microsoft Office '97 suite of productivity applications.
Any Time Probabilistic Reasoning for Sensor Validation
Venue: arXiv cs.AI 2013
Year: 2013

For many real time applications, it is important to validate the information received from the sensors before entering higher levels of reasoning. This paper presents an any time probabilistic algorithm for validating the information provided by sensors. The system consists of two Bayesian network models. The first one is a model of the dependencies between sensors and it is used to validate each sensor. It provides a list of potentially faulty sensors. To isolate the real faults, a second Bayesian network is used, which relates the potential faults with the real faults. This second model is also used to make the validation algorithm any time, by validating first the sensors that provide more information. To select the next sensor to validate, and measure the quality of the results at each stage, an entropy function is used. This function captures in a single quantity both the certainty and specificity measures of any time algorithms. Together, both models constitute a mechanism for validating sensors in an any time fashion, providing at each step the probability of correct/faulty for each sensor, and the total quality of the results. The algorithm has been tested in the validation of temperature sensors of a power plant.
Large Deviation Methods for Approximate Probabilistic Inference
Venue: arXiv cs.LG 2013
Year: 2013

We study two-layer belief networks of binary random variables in which the conditional probabilities Pr[childlparents] depend monotonically on weighted sums of the parents. In large networks where exact probabilistic inference is intractable, we show how to compute upper and lower bounds on many probabilities of interest. In particular, using methods from large deviation theory, we derive rigorous bounds on marginal probabilities such as Pr[children] and prove rates of convergence for the accuracy of our bounds as a function of network size. Our results apply to networks with generic transfer function parameterizations of the conditional probability tables, such as sigmoid and noisy-OR. They also explicitly illustrate the types of averaging behavior that can simplify the problem of inference in large networks.
A Comparison of Lauritzen-Spiegelhalter, Hugin, and Shenoy-Shafer Architectures for Computing Marginals of Probability Distributions
Venue: arXiv cs.AI 2013
Year: 2013

In the last decade, several architectures have been proposed for exact computation of marginals using local computation. In this paper, we compare three architectures - Lauritzen-Spiegelhalter, Hugin, and Shenoy-Shafer - from the perspective of graphical structure for message propagation, message-passing scheme, computational efficiency, and storage efficiency.
Incremental Tradeoff Resolution in Qualitative Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

Qualitative probabilistic reasoning in a Bayesian network often reveals tradeoffs: relationships that are ambiguous due to competing qualitative influences. We present two techniques that combine qualitative and numeric probabilistic reasoning to resolve such tradeoffs, inferring the qualitative relationship between nodes in a Bayesian network. The first approach incrementally marginalizes nodes that contribute to the ambiguous qualitative relationships. The second approach evaluates approximate Bayesian networks for bounds of probability distributions, and uses these bounds to determinate qualitative relationships in question. This approach is also incremental in that the algorithm refines the state spaces of random variables for tighter bounds until the qualitative relationships are resolved. Both approaches provide systematic methods for tradeoff resolution at potentially lower computational cost than application of purely numeric methods.
From Likelihood to Plausibility
Venue: arXiv cs.AI 2013
Year: 2013

Several authors have explained that the likelihood ratio measures the strength of the evidence represented by observations in statistical problems. This idea works fine when the goal is to evaluate the strength of the available evidence for a simple hypothesis versus another simple hypothesis. However, the applicability of this idea is limited to simple hypotheses because the likelihood function is primarily defined on points (simple hypotheses) of the parameter space. In this paper we define a general weight of evidence that is applicable to both simple and composite hypotheses. It is based on the Dempster-Shafer concept of plausibility and is shown to be a generalization of the likelihood ratio. Functional models are of a fundamental importance for the general weight of evidence proposed in this paper. The relevant concepts and ideas are explained by means of a familiar urn problem and the general analysis of a real-world medical problem is presented.
Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents two new approaches to decomposing and solving large Markov decision problems (MDPs), a partial decoupling method and a complete decoupling method. In these approaches, a large, stochastic decision problem is divided into smaller pieces. The first approach builds a cache of policies for each part of the problem independently, and then combines the pieces in a separate, light-weight step. A second approach also divides the problem into smaller pieces, but information is communicated between the different problem pieces, allowing intelligent decisions to be made about which piece requires the most attention. Both approaches can be used to find optimal policies or approximately optimal policies with provable bounds. These algorithms also provide a framework for the efficient transfer of knowledge across problems that share similar structure.
Decision Theoretic Foundations of Graphical Model Selection
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes a decision theoretic formulation of learning the graphical structure of a Bayesian Belief Network from data. This framework subsumes the standard Bayesian approach of choosing the model with the largest posterior probability as the solution of a decision problem with a 0-1 loss function and allows the use of more general loss functions able to trade-off the complexity of the selected model and the error of choosing an oversimplified model. A new class of loss functions, called disintegrable, is introduced, to allow the decision problem to match the decomposability of the graphical model. With this class of loss functions, the optimal solution to the decision problem can be found using an efficient bottom-up search strategy.
Bayesian Networks from the Point of View of Chain Graphs
Venue: arXiv cs.AI 2013
Year: 2013

AThe paper gives a few arguments in favour of the use of chain graphs for description of probabilistic conditional independence structures. Every Bayesian network model can be equivalently introduced by means of a factorization formula with respect to a chain graph which is Markov equivalent to the Bayesian network. A graphical characterization of such graphs is given. The class of equivalent graphs can be represented by a distinguished graph which is called the largest chain graph. The factorization formula with respect to the largest chain graph is a basis of a proposal of how to represent the corresponding (discrete) probability distribution in a computer (i.e. parametrize it). This way does not depend on the choice of a particular Bayesian network from the class of equivalent networks and seems to be the most efficient way from the point of view of memory demands. A separation criterion for reading independency statements from a chain graph is formulated in a simpler way. It resembles the well-known d-separation criterion for Bayesian networks and can be implemented locally.
Flexible and Approximate Computation through State-Space Reduction
Venue: arXiv cs.AI 2013
Year: 2013

In the real world, insufficient information, limited computation resources, and complex problem structures often force an autonomous agent to make a decision in time less than that required to solve the problem at hand completely. Flexible and approximate computations are two approaches to decision making under limited computation resources. Flexible computation helps an agent to flexibly allocate limited computation resources so that the overall system utility is maximized. Approximate computation enables an agent to find the best satisfactory solution within a deadline. In this paper, we present two state-space reduction methods for flexible and approximate computation: quantitative reduction to deal with inaccurate heuristic information, and structural reduction to handle complex problem structures. These two methods can be applied successively to continuously improve solution quality if more computation is available. Our results show that these reduction methods are effective and efficient, finding better solutions with less computation than some existing well-known methods.
An OAI-PMH-based Web Service for the Generation of Co-Author Networks
Venue: arXiv cs.DL 2013
Year: 2013

We will present a new component of our technical framework that was built to provide a brought range of reusable web services for the enhancement of typical scientific retrieval processes. The proposed component computes betweenness of authors in co-authorship networks extracted from publicly available metadata that was harvested using OAI-PMH.
Introduction of Intellectual Property Courses in STEM Curriculum
Venue: arXiv cs.CY 2013
Year: 2013

The paper explains and emphasizes the need to include mandatory Intellectual Property (IP) courses in the undergraduate and graduate curriculum of STEM students. It prescribes the proposed content of IP to be covered at undergraduate level, and graduate depending on the degree pursued by the STEM student. More importantly, this paper advocates for an Integrated PhD/JD degree to produce highly skilled patent attorneys and agents, to overcome the problem of poor quality of patents, and the high number of patent related litigations. A framework is suggested which would enable STEM departments and law schools to successfully offer this integrated degree, and students to successfully pursue and complete this degree program in a realistic manner; without compromising any stake holder's interest.
On Quality of Monitoring for Multi-channel Wireless Infrastructure Networks
Venue: arXiv cs.NI 2013
Year: 2013

Passive monitoring utilizing distributed wireless sniffers is an effective technique to monitor activities in wireless infrastructure networks for fault diagnosis, resource management and critical path analysis. In this paper, we introduce a quality of monitoring (QoM) metric defined by the expected number of active users monitored, and investigate the problem of maximizing QoM by judiciously assigning sniffers to channels based on the knowledge of user activities in a multi-channel wireless network. Two types of capture models are considered. The user-centric model assumes frame-level capturing capability of sniffers such that the activities of different users can be distinguished while the sniffer-centric model only utilizes the binary channel information (active or not) at a sniffer. For the user-centric model, we show that the implied optimization problem is NP-hard, but a constant approximation ratio can be attained via polynomial complexity algorithms. For the sniffer-centric model, we devise stochastic inference schemes to transform the problem into the user-centric domain, where we are able to apply our polynomial approximation algorithms. The effectiveness of our proposed schemes and algorithms is further evaluated using both synthetic data as well as real-world traces from an operational WLAN.
Finite Length Analysis on Listing Failure Probability of Invertible Bloom Lookup Tables
Venue: arXiv cs.IT 2013
Year: 2013

The Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations of the key-value pair. The IBLT can be used to realize efficient set reconciliation for database synchronization. The most notable feature of the IBLT is the complete listing operation of the key-value pairs based on the algorithm similar to the peeling algorithm for low-density generator-matrix (LDGM) codes. In this paper, we will present a stopping set (SS) analysis for the IBLT which reveals finite length behaviors of the listing failure probability. The key of the analysis is enumeration of the number of stopping matrices of given size. We derived a novel recursive formula useful for computationally efficient enumeration. An upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors. It will be shown that, in the error floor region, the dominant SS have size 2. We propose a simple modification on hash functions, which are called SS avoiding hash functions, for preventing occurrences of the SS of size 2.