Consider random hypergraphs on n vertices, where each k -element subset of vertices is selected with probability $independently and randomly as a hyperedge. By sparse we mean that the total number of hyperedges is  O ( n) or O ( n  ln n ). When k = 2, these are exactly the classical Erdös-Rényi random graphs G(n,p ). We prove that with high probability, hinge width on these sparse random hypergraphs can grow linearly with the expected number of hyperedges. Some random constraint satisfaction problems such as Model RB and Model RD have satisfiability thresholds on these sparse constraint hypergraphs, thus the large hinge width results provide some theoretical evidence for random instances around satisfiability thresholds to be hard for a standard hinge-decomposition based algorithm. We also conduct experiments on these and other kinds of random graphs with several hundreds vertices, including regular random graphs and power law random graphs. The experimental results also show that hinge width can grow linearly with the number of edges on these different random graphs. These results may be of further interests.

Cooperation among automated agents is becoming increasingly important in various artificial intelligence applications. Coalitional (i.e., cooperative) game theory supplies conceptual and mathematical tools useful in the analysis of such interactions, and in particular in the achievement of stable outcomes among self-interested agents. Here, we study the minimal external subsidy required to stabilize the core of a coalitional game. Following the Cost of Stability (CoS) model introduced by Bachrach et al. [2009a], we give tight bounds on the required subsidy under various restrictions on the social structure of the game. We then compare the extended core induced by subsidies with the least core of the game, proving tight bounds on the ratio between the minimal subsidy and the minimal demand relaxation that each lead to stability.

Another example is items to users based on their historical ratings. In that, although many people don't like animations, they may real-world scenarios, user interests may drift over still have interests in emerging 3-D animations because of the time since they are affected by moods, contexts, fantastic 3-D visual effects. These observations show that, and pop culture trends. This leads to the fact that although many aspects of user interests can be found based a user's historical ratings comprise many aspects of on users' historical ratings, at a certain time slice, one user's user interests spanning a long time period. However, interest may only focus on one or a couple of aspects. Thus, at a certain time slice, one user's interest may the static CF methods built on the entire historical ratings are only focus on one or a couple of aspects. Thus, inadequate to capture user-interest drift. In order to track user CF techniques based on the entire historical ratings interests and create comprehensive user profiles such that different may recommend inappropriate items. In this paper, recommendation strategies can be used for consistenttaste we consider modeling user-interest drift over time users and changing-taste users, a CF method that can based on the assumption that each user has multiple model user interests over time is required.

We study the existence and computational complexity of coalitional stability concepts based on social networks. Our concepts represent a natural and rich combinatorial generalization of a recent notion termed partition equilibrium. We assume that players in a strategic game are embedded in a social (or, communication) network, and there are coordination constraints defining the set of coalitions that can jointly deviate in the game. A main feature of our approach is that players act in a "considerate" fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors in the network. We explore the properties of such considerate equilibria in application to the celebrated class of resource selection games (RSGs). Our main result proves existence of a super-strong considerate equilibrium in all symmetric RSGs with strictly increasing delays, for any social network among the players and feasible coalitions represented by the set of cliques. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for a standard RSG, thus showing that there exists a state that is stable against selfish and considerate behavior simultaneously. Furthermore, we provide results on convergence of considerate dynamics.

Extracting the relations that exist between two entities is an important step in numerousWeb-related tasks such as information extraction.A supervised relation extraction system that is trained to extract a particular relation type might not accurately extract a new type of a relation for which it has not been trained.However, it is costly to create training data manually for every new relation type that one might want to extract.We propose a method to adapt an existing relation extraction system to extractnew relation types with minimum supervision. Our proposed method comprises two stages: learning a lower-dimensional projection between different relations, and learning a relational classifier for the target relation type with instance sampling. We evaluate the proposed method using a dataset that contains 2000 instances for 20 different relation types. Our experimental results show that the proposed method achieves a statistically significant macro-average F-score of 62.77. Moreover, the proposed method outperforms numerous baselines and a previously proposed weakly-supervised relation extraction method.

The possibility that influenza activity can be generally detected through search log analysis has been explored in recent years. However, previous studies have mainly focused on influenza, and little attention has been paid to other epidemics. With an analysis of web user behavior data, we consider the problem of predicting the tendency of hand-foot -and-mouth disease  (HFMD), whose out-break in 2010 resulted in a great panic in China. In addi-tion to search queries, we consider users’ interactions with search engines. Given the collected search logs, we cluster HFMD-related search queries, medical pages and news reports into the following sets: epidemic-related queries (ERQs), epidemic-related pages (ERPs) and ep-idemic-related news (ERNs). Furthermore, we count their own frequencies as different features, and we conduct a regression analysis with current HFMD occurrences. The experimental results show that these features exhibit good performances on both accuracy and timeliness.

Positive and unlabelled learning (PU learning) has been investigated to deal with the situation where only the positive examples and the unlabelled examples are available. Most of the previous works focus on identifying some negative examples from the unlabelled data, so that the supervised learning methods can be applied to build a classifier. However, for the remaining unlabelled data, which can not be explicitly identified as positive or negative (we call them ambiguous examples), they either exclude them from the training phase or simply enforce them to either class. Consequently, their performance may be constrained. This paper proposes a novel approach, called similarity-based PU learning (SPUL) method, by associating the ambiguous examples with two similarity weights, which indicate the similarity of an ambiguous example towards the positive class and the negative class, respectively. The local similarity-based and global similarity-based mechanisms are proposed to generate the similarity weights. The ambiguous examples and their similarity-weights are thereafter incorporated into an SVM-based learning phase to build a more accurate classifier. Extensive experiments on real-world datasets have shown that SPUL outperforms state-of-the-art PU learning methods.  

In binary-utility games, an agent can have only two possible utility values for final states, 1 (win) and 0 (lose). An adversarial binaryutility game is one where for each final state there must be at least one winning and one losing agent. We define an unbiased rational agent as one that seeks to maximize its utility value, but is equally likely to choose between states with the same utility value. This induces a probability distribution over the outcomes of the game, from which an agent can infer its probability to win. A single adversary binary game is one where there are only two possible outcomes, so that the winning probabilities remain binary values. In this case, the rational action for an agent is to play minimax. In this work we focus on the more complex, multiple-adversary environment. We propose a new algorithmic framework where agents try to maximize their winning probabilities. We begin by theoretically analyzing why an unbiased rational agent should take our approach in an unbounded environment and not that of the existing Paranoid or MaxN algorithms. We then expand our framework to a resource-bounded environment, where winning probabilities are estimated, and show empirical results supporting our claims.

During the design of a microprocessor, Design Space Exploration (DSE) is a critical step which determines the appropriate design configuration of the microprocessor. In the computer architecture community, supervised learning techniques have been applied to DSE to build models for predicting the qualities of design configurations. For supervised learning, however, considerable simulation costs are required for attaining the labeled design configurations. Given limited resources, it is difficult to achieve high accuracy. In this paper, inspired by recent advances in semi-supervised learning, we propose the COMT approach which can exploit unlabeled design configurations to improve the models. In addition to an improved predictive accuracy, COMT is able to guide the design of microprocessors, owing to the use of comprehensible model trees. Empirical study demonstrates that COMT significantly outperforms state-of-the-art DSE technique through reducing mean squared error by 30% to 84%, and thus, promising architectures can be attained more efficiently.

Consistent word selection in machine translation is currently realized by resolving word sense ambiguity through the context of a single sentence or neighboring sentences. However, consistent word selection over the whole article has yet to be achieved. Consistency over the whole article is extremely important when applying machine translation to collectively developed documents like Wikipedia. In this paper, we propose to consider constraints between words in the whole article based on their semantic relatedness and contextual distance. The proposed method is successfully implemented in both statistical and rule-based translators. We evaluate those systems by translating 100 articles in the English Wikipedia into Japanese. The results show that the ratio of appropriate word selection for common nouns increased to around 75% with our method, while it was around 55% without our method.