This paper presents an algorithm for finding approximately optimal policies in very large Markov decision processes by constructing a hierarchical model and then solving it approximately. It exploits factored representations to achieve compactness and efficiency and to discover connectivity properties of the domain. We provide a bound on the quality of the solutions and give asymptotic analysis of the runtimes; in addition we demonstrate performance on a collection of very large domains. Results show that the quality of resulting policies is very good and the total running times, for both creating and solving the hierarchy, are significantly less than for an optimal factored MDP solver.

Recent real-world deployments of Stackelberg security games make it critical that we address human adversaries' bounded rationality in computing optimal strategies. To that end, this paper provides three key contributions: (i) new efficient algorithms for computing optimal strategic solutions using Prospect Theory and Quantal Response Equilibrium; (ii) the most comprehensive experiment to date studying the effectiveness of different models against human subjects for security games; and (iii) new techniques for generating representative payoff structures for behavioral experiments in generic classes of games. Our results with human subjects show that our new techniques outperform the leading contender for modeling human behavior in security games.

We propose a personalized re-ranking algorithm through mining user dwell times derived from a user's previously online reading or browsing activities. We acquire document level user dwell times via a customized web browser, from which we then infer concept word level user dwell times in order to understand a user's personal interest. According to the estimated concept word level user dwell times, our algorithm can estimate a user's potential dwell time over a new document, based on which personalized webpage re-ranking can be carried out. We compare the rankings produced by our algorithm with rankings generated by popular commercial search engines and a recently proposed personalized ranking algorithm. The results clearly show the superiority of our method.

A plan with rich control structures like branches and loops can usually serve as a general solution that solves multiple planning instances in a domain. However, the correctness of such generalized plans is non-trivial to define and verify, especially when it comes to whether or not a plan works for all of the infinitely many instances of the problem. In this paper, we give a precise definition of a generalized plan representation called an FSA plan, with its semantics defined in the situation calculus. Based on this, we identify a class of infinite planning problems, which we call one-dimensional (1d), and prove a correctness result that 1d problems can be verified by finite means. We show that this theoretical result leads to an algorithm that does this verification practically, and a planner based on this verification algorithm efficiently generates provably correct plans for 1d problems.

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Thus, coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. A range of previous studies have found that many problems in coalitional games tend to be computationally intractable when the input is a black-box function. Recently, several concise representation schemes for a characteristic function have been proposed. Although these schemes are effective for reducing the representation size, most problems remain computationally intractable. In this paper, we develop a new concise representation scheme based on the idea of agent types. Intuitively, a type represents a set of agents, which are recognized as having the same contribution. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size. Moreover, we show that most of the problems in coalitional games, including CSG, can be solved in polynomial time in the number of agents, assuming the number of possible types is fixed.

We consider an extension of the propositional modal logic S4 which allows <> to act not only on isolated formulas, but also on sets of formulas. The interpretation of <>A is then given by the tangled closure of the valuations of formulas in A, which over finite transitive, reflexive models indicates the existence of a cluster satisfying A. This extension has been shown to be more expressive than the basic modal language: for example, it is equivalent to the bisimulation-invariant fragment of FOL over finite S4 models, whereas the basic modal language is weaker. However, previous analyses of this logic have been entirely semantic, and no proof system was available. In this paper we present a sound proof system for the polyadic S4 and prove that it is complete. The axiomatization is fairly standard, adding only the fixpoint axioms of the tangled closure to the usual S4 axioms. The proof proceeds by explicitly constructing a finite model from a consistent set of formulas.

We call this task the rating-inference task; Traditional sentiment analysis mainly considers It determines an author's polarity evaluation within a multipoint binary classifications of reviews, but in many scale (e.g. one to five "stars"). We explore solutions for real-world sentiment classification problems, nonbinary this task in the context of product or service reviews, which review ratings are more useful. This is especially are one of the most important opinion resources and widely true when consumers wish to compare two used by costumers and companies. We observe that in many products, both of which are not negative. Previous real-world scenarios, it is important to provide numerical ratings work has addressed this problem by extracting rather than binary decisions, especially when a customer various features from the review text for learning a compares several candidate products, all of them are positive predictor. Since the same word may have different in a binary classification, to make a purchase decision, since sentiment effects when used by different reviewers customers not only need to know whether a product is good or on different products, we argue that it is necessary not, but also how good the product is. A recent study pointed to model such reviewer and product dependent effects out that many consumers are willing to pay at least 20% percent in order to predict review ratings more accurately.

PODTGolog [Rens, 2010] is a Golog dialect attempting Broadly speaking, my research concerns combining to deal with partially observable MDP (POMDP) logic of action and POMDP theory in a coherent, environments. PODTGolog has not been given a mathematical theoretically sound language for agent programming.

Most of the text mining tasks, such as clustering, is dominated by statistical approaches that treat text as a bag of words. Semantics in the text is largely ignored in the mining process, and the mining results are often not easily interpretable. One particular challenge faced by such approaches is short text understanding, as short text lacks enough content from which a statistical conclusion can be drawn. For example, traditional topic analysis methods consider topic segments with tens of hundreds of words. Latent topic modeling, such as latent Dirichlet allocation, also requires sufficient words to infer document topic distribution. We enhance machine learning algorithms by first giving the machine a probabilistic knowledgebase that contains as big, rich, and consistent concepts (of worldly facts) as those in our mental world. Then a Bayesian inference mechanism is developed to conceptualize words and short text. We conducted comprehensive tests of our method on conceptualizing set of text terms, as well as clustering Twitter messages (tweets), which are typically approximately ten words long. Compared to latent semantic topic modeling and other four kinds of methods that using WordNet, Freebase and Wikipedia (category links and explicit semantic analysis), we show significant improvements in terms of tweets clustering accuracy.

Artificial intelligence has a long history of learning from domain problems ranging from chess to jeopardy. In this work, we look at a problem stemming from social science, namely, how do social relationships influence communication content and vice versa. The tools used to study communication content (content analysis) have rarely been combined with those used to study social relationships (social network analysis). Furthermore, there is even less work addressing the longitudinal characteristics of such a combination. This paper presents a general framework for measuring the dynamic bi-directional influence between communication content and social networks. The framework leverages the idea that knowledge about both kinds of networks can be represented using the same knowledge representation. In particular, through the use of Semantic Web standards, the extraction of networks is made easier. The framework is applied to two use-cases: online forum discussions and conference publications. The results provide a new perspective over the dynamics involving both social networks and communication content.