OpenRaiser/Intern-Atlas huggingface dataset:
Qualitative Models for Decision Under Uncertainty without the Commensurability Assumption
Venue: arXiv cs.AI 2013
Year: 2013

This paper investigates a purely qualitative version of Savage's theory for decision making under uncertainty. Until now, most representation theorems for preference over acts rely on a numerical representation of utility and uncertainty where utility and uncertainty are commensurate. Disrupting the tradition, we relax this assumption and introduce a purely ordinal axiom requiring that the Decision Maker (DM) preference between two acts only depends on the relative position of their consequences for each state. Within this qualitative framework, we determine the only possible form of the decision rule and investigate some instances compatible with the transitivity of the strict preference. Finally we propose a mild relaxation of our ordinality axiom, leaving room for a new family of qualitative decision rules compatible with transitivity.
Quantifier Elimination for Statistical Problems
Venue: arXiv cs.AI 2013
Year: 2013

Recent improvement on Tarski's procedure for quantifier elimination in the first order theory of real numbers makes it feasible to solve small instances of the following problems completely automatically: 1. listing all equality and inequality constraints implied by a graphical model with hidden variables. 2. Comparing graphyical models with hidden variables (i.e., model equivalence, inclusion, and overlap). 3. Answering questions about the identification of a model or portion of a model, and about bounds on quantities derived from a model. 4. Determing whether a given set of independence assertions. We discuss the foundation of quantifier elimination and demonstrate its application to these problems.
Approximate Planning for Factored POMDPs using Belief State Simplification
Venue: arXiv cs.AI 2013
Year: 2013

We are interested in the problem of planning for factored POMDPs. Building on the recent results of Kearns, Mansour and Ng, we provide a planning algorithm for factored POMDPs that exploits the accuracy-efficiency tradeoff in the belief state simplification introduced by Boyen and Koller.
A Variational Approximation for Bayesian Networks with Discrete and Continuous Latent Variables
Venue: arXiv cs.AI 2013
Year: 2013

We show how to use a variational approximation to the logistic function to perform approximate inference in Bayesian networks containing discrete nodes with continuous parents. Essentially, we convert the logistic function to a Gaussian, which facilitates exact inference, and then iteratively adjust the variational parameters to improve the quality of the approximation. We demonstrate experimentally that this approximation is faster and potentially more accurate than sampling. We also introduce a simple new technique for handling evidence, which allows us to handle arbitrary distributions on observed nodes, as well as achieving a significant speedup in networks with discrete variables of large cardinality.
Mixture Approximations to Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Structure and parameters in a Bayesian network uniquely specify the probability distribution of the modeled domain. The locality of both structure and probabilistic information are the great benefits of Bayesian networks and require the modeler to only specify local information. On the other hand this locality of information might prevent the modeler - and even more any other person - from obtaining a general overview of the important relationships within the domain. The goal of the work presented in this paper is to provide an "alternative" view on the knowledge encoded in a Bayesian network which might sometimes be very helpful for providing insights into the underlying domain. The basic idea is to calculate a mixture approximation to the probability distribution represented by the Bayesian network. The mixture component densities can be thought of as representing typical scenarios implied by the Bayesian model, providing intuition about the basic relationships. As an additional benefit, performing inference in the approximate model is very simple and intuitive and can provide additional insights. The computational complexity for the calculation of the mixture approximations criticaly depends on the measure which defines the distance between the probability distribution represented by the Bayesian network and the approximate distribution. Both the KL-divergence and the backward KL-divergence lead to inefficient algorithms. Incidentally, the latter is used in recent work on mixtures of mean field solutions to which the work presented here is closely related. We show, however, that using a mean squared error cost function leads to update equations which can be solved using the junction tree algorithm. We conclude that the mean squared error cost function can be used for Bayesian networks in which inference based on the junction tree is tractable. For large networks, however, one may have to rely on mean field approximations.
Bayesian Control for Concentrating Mixed Nuclear Waste
Venue: arXiv cs.AI 2013
Year: 2013

A control algorithm for batch processing of mixed waste is proposed based on conditional Gaussian Bayesian networks. The network is compiled during batch staging for real-time response to sensor input.
On Graph Stream Clustering with Side Information
Venue: arXiv cs.DB 2013
Year: 2013

Graph clustering becomes an important problem due to emerging applications involving the web, social networks and bio-informatics. Recently, many such applications generate data in the form of streams. Clustering massive, dynamic graph streams is significantly challenging because of the complex structures of graphs and computational difficulties of continuous data. Meanwhile, a large volume of side information is associated with graphs, which can be of various types. The examples include the properties of users in social network activities, the meta attributes associated with web click graph streams and the location information in mobile communication networks. Such attributes contain extremely useful information and has the potential to improve the clustering process, but are neglected by most recent graph stream mining techniques. In this paper, we define a unified distance measure on both link structures and side attributes for clustering. In addition, we propose a novel optimization framework DMO, which can dynamically optimize the distance metric and make it adapt to the newly received stream data. We further introduce a carefully designed statistics SGS(C) which consume constant storage spaces with the progression of streams. We demonstrate that the statistics maintained are sufficient for the clustering process as well as the distance optimization and can be scalable to massive graphs with side attributes. We will present experiment results to show the advantages of the approach in graph stream clustering with both links and side information over the baselines.
Approximation of Classification and Measures of Uncertainty in Rough Set on Two Universal Sets
Venue: arXiv cs.AI 2013
Year: 2013

The notion of rough set captures indiscernibility of elements in a set. But, in many real life situations, an information system establishes the relation between different universes. This gave the extension of rough set on single universal set to rough set on two universal sets. In this paper, we introduce approximation of classifications and measures of uncertainty basing upon rough set on two universal sets employing the knowledge due to binary relations.
Discrimination in Online Ad Delivery
Venue: arXiv cs.IR 2013
Year: 2013

A Google search for a person's name, such as "Trevon Jones", may yield a personalized ad for public records about Trevon that may be neutral, such as "Looking for Trevon Jones?", or may be suggestive of an arrest record, such as "Trevon Jones, Arrested?". This writing investigates the delivery of these kinds of ads by Google AdSense using a sample of racially associated names and finds statistically significant discrimination in ad delivery based on searches of 2184 racially associated personal names across two websites. First names, assigned at birth to more black or white babies, are found predictive of race (88% black, 96% white), and those assigned primarily to black babies, such as DeShawn, Darnell and Jermaine, generated ads suggestive of an arrest in 81 to 86 percent of name searches on one website and 92 to 95 percent on the other, while those assigned at birth primarily to whites, such as Geoffrey, Jill and Emma, generated more neutral copy: the word "arrest" appeared in 23 to 29 percent of name searches on one site and 0 to 60 percent on the other. On the more ad trafficked website, a black-identifying name was 25% more likely to get an ad suggestive of an arrest record. A few names did not follow these patterns. All ads return results for actual individuals and ads appear regardless of whether the name has an arrest record in the company's database. The company maintains Google received the same ad text for groups of last names (not first names), raising questions as to whether Google's technology exposes racial bias.
Towards Interactive Object-Oriented Programming
Venue: arXiv cs.PL 2013
Year: 2013

To represent interactive objects, we propose a choice-disjunctive declaration statement of the form S R where S;R are the (procedure or field) declaration statements within a class. This statement has the following semantics: request the user to choose one between S and R when an object of this class is created. This statement is useful for representing interactive objects that require interactions with the user.
Maximum Likelihood Associative Memories
Venue: arXiv cs.IT 2013
Year: 2013

Associative memories are structures that store data in such a way that it can later be retrieved given only a part of its content -- a sort-of error/erasure-resilience property. They are used in applications ranging from caches and memory management in CPUs to database engines. In this work we study associative memories built on the maximum likelihood principle. We derive minimum residual error rates when the data stored comes from a uniform binary source. Second, we determine the minimum amount of memory required to store the same data. Finally, we bound the computational complexity for message retrieval. We then compare these bounds with two existing associative memory architectures: the celebrated Hopfield neural networks and a neural network architecture introduced more recently by Gripon and Berrou.
Cross-Pollination of Information in Online Social Media: A Case Study on Popular Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Owing to the popularity of Online Social Media (OSM), Internet users share a lot of information (including personal) on and across OSM services every day. For example, it is common to find a YouTube video embedded in a blog post with an option to share the link on Facebook. Users recommend, comment, and forward information they receive from friends, contributing in spreading the information in and across OSM services. We term this information diffusion process from one OSM service to another as Cross-Pollination, and the network formed by users who participate in Cross-Pollination and content produced in the network as \emph{Cross-Pollinated network}. Research has been done about information diffusion within one OSM service, but little is known about Cross-Pollination. In this paper, we aim at filling this gap by studying how information (video, photo, location) from three popular OSM services (YouTube, Flickr and Foursquare) diffuses on Twitter, the most popular microblogging service. Our results show that Cross-Pollinated networks follow temporal and topological characteristics of the diffusion OSM (Twitter in our study). Furthermore, popularity of information on source OSM (YouTube, Flickr and Foursquare) does not imply its popularity on Twitter. Our results also show that Cross-Pollination helps Twitter in terms of traffic generation and user involvement, but only a small fraction of videos and photos gain a significant number of views from Twitter. We believe this is the first research work which explicitly characterizes the diffusion of information across different OSM services.
Increasing Network Visibility Using Coded Repetition Beacon Piggybacking
Venue: arXiv cs.NI 2013
Year: 2013

Vehicular Ad hoc Networks (VANET) is one of the most challenging research areas in the field of Mobile Ad Hoc Networks. In this research, we propose a new mechanism for increasing network visibility, by taking the information gained from periodic safety messages (beacons), and inserting it into a 'neighbor' table. The table will be propagated to all neighbors giving a wider vision for each vehicle belonging to the network. It will also decrease the risk of collision at road junctions as each vehicle will have prior knowledge oncoming vehicles before reaching the junction.
Spatial degrees of freedom of MIMO systems in Line-of-Sight Environment
Venue: arXiv cs.IT 2013
Year: 2013

While the efficiency of MIMO transmissions in a rich scattering environment has been demonstrated, less is known about the situation where the fading matrix coefficients come from a line-of-sight model. In this paper, we study in detail how this line-of-sight assumption affects the performance of distributed MIMO transmissions between far away clusters of nodes in a wireless network. Our analysis pertains to the study of a new class of random matrices.
Empirical Evidence for the Relevance of Fractional Scoring in the Calculation of Percentile Rank Scores
Venue: arXiv cs.DL 2013
Year: 2013

Fractional scoring has been proposed to avoid inconsistencies in the attribution of publications to percentile rank classes. Uncertainties and ambiguities in the evaluation of percentile ranks can be demonstrated most easily with small datasets. But for larger datasets an often large number of papers with the same citation count leads to the same uncertainties and ambiguities which can be avoided by fractional scoring. This is demonstrated for four different empirical datasets with several thousand publications each which are assigned to 6 percentile rank classes. Only by utilizing fractional scoring the total score of all papers exactly reproduces the theoretical value in each case.
The Parity of Directed Hamiltonian Cycles
Venue: arXiv cs.DS 2013
Year: 2013

We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619^n) time and polynomial space. For bipartite graphs, we give a 1.5^n poly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
Irrelevance and Independence Relations in Quasi-Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

This paper analyzes irrelevance and independence relations in graphical models associated with convex sets of probability distributions (called Quasi-Bayesian networks). The basic question in Quasi-Bayesian networks is, How can irrelevance/independence relations in Quasi-Bayesian networks be detected, enforced and exploited? This paper addresses these questions through Walley's definitions of irrelevance and independence. Novel algorithms and results are presented for inferences with the so-called natural extensions using fractional linear programming, and the properties of the so-called type-1 extensions are clarified through a new generalization of d-separation.
Comparative Uncertainty, Belief Functions and Accepted Beliefs
Venue: arXiv cs.AI 2013
Year: 2013

This paper relates comparative belief structures and a general view of belief management in the setting of deductively closed logical representations of accepted beliefs. We show that the range of compatibility between the classical deductive closure and uncertain reasoning covers precisely the nonmonotonic 'preferential' inference system of Kraus, Lehmann and Magidor and nothing else. In terms of uncertain reasoning any possibility or necessity measure gives birth to a structure of accepted beliefs. The classes of probability functions and of Shafer's belief functions which yield belief sets prove to be very special ones.
Lazy Propagation in Junction Trees
Venue: arXiv cs.AI 2013
Year: 2013

The efficiency of algorithms using secondary structures for probabilistic inference in Bayesian networks can be improved by exploiting independence relations induced by evidence and the direction of the links in the original network. In this paper we present an algorithm that on-line exploits independence relations induced by evidence and the direction of the links in the original network to reduce both time and space costs. Instead of multiplying the conditional probability distributions for the various cliques, we determine on-line which potentials to multiply when a message is to be produced. The performance improvement of the algorithm is emphasized through empirical evaluations involving large real world Bayesian networks, and we compare the method with the HUGIN and Shafer-Shenoy inference algorithms.
A Multivariate Discretization Method for Learning Bayesian Networks from Mixed Data
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we address the problem of discretization in the context of learning Bayesian networks (BNs) from data containing both continuous and discrete variables. We describe a new technique for <EM>multivariate</EM> discretization, whereby each continuous variable is discretized while taking into account its interaction with the other variables. The technique is based on the use of a Bayesian scoring metric that scores the discretization policy for a continuous variable given a BN structure and the observed data. Since the metric is relative to the BN structure currently being evaluated, the discretization of a variable needs to be dynamically adjusted as the BN structure changes.
Phishing, Personality Traits and Facebook
Venue: arXiv cs.HC 2013
Year: 2013

Phishing attacks have become an increasing threat to online users. Recent research has begun to focus on the factors that cause people to respond to them. Our study examines the correlation between the Big Five personality traits and email phishing response. We also examine how these factors affect users behavior on Facebook, including posting personal information and choosing Facebook privacy settings. Our research shows that when using a prize phishing email, we find a strong correlation between gender and the response to the phishing email. In addition, we find that the neuroticism is the factor most correlated to responding to this email. Our study also found that people who score high on the openness factor tend to both post more information on Facebook as well as have less strict privacy settings, which may cause them to be susceptible to privacy attacks. In addition, our work detected no correlation between the participants estimate of being vulnerable to phishing attacks and actually being phished, which suggests susceptibility to phishing is not due to lack of awareness of the phishing risks and that realtime response to phishing is hard to predict in advance by online users. We believe that better understanding of the traits which contribute to online vulnerability can help develop methods for increasing users privacy and security in the future.
Fast non parametric entropy estimation for spatial-temporal saliency method
Venue: arXiv cs.CV 2013
Year: 2013

This paper formulates bottom-up visual saliency as center surround conditional entropy and presents a fast and efficient technique for the computation of such a saliency map. It is shown that the new saliency formulation is consistent with self-information based saliency, decision-theoretic saliency and Bayesian definition of surprises but also faces the same significant computational challenge of estimating probability density in very high dimensional spaces with limited samples. We have developed a fast and efficient nonparametric method to make the practical implementation of these types of saliency maps possible. By aligning pixels from the center and surround regions and treating their location coordinates as random variables, we use a k-d partitioning method to efficiently estimating the center surround conditional entropy. We present experimental results on two publicly available eye tracking still image databases and show that the new technique is competitive with state of the art bottom-up saliency computational methods. We have also extended the technique to compute spatiotemporal visual saliency of video and evaluate the bottom-up spatiotemporal saliency against eye tracking data on a video taken onboard a moving vehicle with the driver's eye being tracked by a head mounted eye-tracker.
Toward a Dynamic Programming Solution for the 4-peg Tower of Hanoi Problem with Configurations
Venue: arXiv cs.PL 2013
Year: 2013

The Frame-Stewart algorithm for the 4-peg variant of the Tower of Hanoi, introduced in 1941, partitions disks into intermediate towers before moving the remaining disks to their destination. Algorithms that partition the disks have not been proven to be optimal, although they have been verified for up to 30 disks. This paper presents a dynamic programming approach to this algorithm, using tabling in B-Prolog. This study uses a variation of the problem, involving configurations of disks, in order to contrast the tabling approach with the approaches utilized by other solvers. A comparison of different partitioning locations for the Frame-Stewart algorithm indicates that, although certain partitions are optimal for the classic problem, they need to be modified for certain configurations, and that random configurations might require an entirely new algorithm.
A direct reduction of PPAD Lemke-verified linear complementarity problems to bimatrix games
Venue: arXiv cs.CC 2013
Year: 2013

The linear complementarity problem, LCP(q,M), is defined as follows. For given M,q find z such that q+Mz>=0, z>=0, z(q + M z)=0,or certify that there is no such z. It is well known that the problem of finding a Nash equilibrium for a bimatrix game (2-NASH) can be formulated as a linear complementarity problem (LCP). In addition, 2-NASH is known to be complete in the complexity class PPAD (Polynomial-time Parity Argument Directed). However, the ingeniously constructed reduction (which is designed for any PPAD problem) is very complicated, so while of great theoretical significance, it is not practical for actually solving an LCP via 2-NASH, and it may not provide the potential insight that can be gained from studying the game obtained from a problem formulated as an LCP (e.g. market equilibrium). The main goal of this paper is the construction of a simple explicit reduction of any LCP(q,M) that can be verified as belonging to PPAD via the graph induced by the generic Lemke algorithm with some positive covering vector d, to a symmetric 2-NASH. In particular, any endpoint of this graph (with the exception of the initial point of the algorithm) corresponds to either a solution or to a so-called secondary ray. Thus, an LCP problem is verified as belonging to PPAD if any secondary ray can be used to construct, in polynomial time, a certificate that there is no solution to the problem. We achieve our goal by showing that for any M,q and a positive d satisfying a certain nondegeneracy assumption with respect to M, we can simply and directly construct a symmetric 2-NASH whose Nash equilibria correspond one-to-one to the end points of the graph induced by LCP(q,M) and the Lemke algorithm with a covering vector d. We note that for a given M the reduction works for all positive d with the exception of a subset of measure 0.