A key strategy for speeding up computation is to run in parallel on multiple cores. However, on hard combinatorial problems, exploiting parallelism has been surprisingly challenging. It appears that traditional divide-and-conquer strategies do not work well, due to the intricate non-local nature of the interactions between the problem variables. In this paper, we introduce a novel way in which parallelism can be used to exploit hidden structure of hard combinatorial problems. We demonstrate the success of this approach on minimal set basis problem, which has a wide range of applications in machine learning and system security, etc. We also show the effectiveness on a related application problem from materials discovery. In our approach, a large number of smaller sub-problems are identified and solved concurrently. We then aggregate the information from those solutions, and use this to initialize the search of a global, complete solver. We show that this strategy leads to a significant speed-up over a sequential approach. The strategy also greatly outperforms state-of-the-art incomplete solvers in terms of solution quality. Our work opens up a novel angle for using parallelism to solve hard combinatorial problems.

We describe a data complexity approach to kernel selection based on the behavior of polynomial and Gaussian kernels. Our resultsshow how the use of a Gaussian kernel produces a gram matrix with useful local information that has no equivalent counterpart inpolynomial kernels.By exploiting neighborhood information embedded by data complexity measures, we are able to carry out a form of meta-generalization.Our goal is to predict which data sets are more favorable to particular kernels (Gaussian or polynomial).The end result is a framework to improve the model selection process in Support Vector Machines.

With the rapid growth of event-based social networks, the demand of event recommendation becomes increasingly important. Different from classic recommendation problems, event recommendation generally faces the problems of heterogenous online and offline social relationships among users and implicit feedback data. In this paper, we present a baysian probability model that can fully unleash the power of heterogenous social relations and efficiently tackle with implicit feedback characteristic for event recommendation. Experimental results on several real-world datasets demonstrate the utility of our method.

Reputation models depend on the ratings provided by buyers togauge the reliability of sellers in multi-agent based e-commerce environment. However, there is no prevention forthe cases in which a buyer misjudges a seller, and provides a negative rating to an original satisfactory transaction. In this case,how should the seller get his reputation repaired andutility loss recovered? In this work, we propose a mechanism to mitigate the negativeeffect of the misreported ratings. It temporarily inflates the reputation of thevictim seller with a certain value for a period of time. This allows the seller to recover hisutility loss due to lost opportunities caused by the misreported ratings. Experiments demonstrate the necessity and effectiveness of the proposed mechanism.

Users of a social network like to follow the posts published by influential users. Such posts usually are delivered quickly and thus will produce a strong influence on public opinions. In this paper, we focus on the problem of identifying domain-dependent influential users(or topic experts). Some of traditional approaches are based on the post contents of users user’s to identify influential users, which may be biased by spammers who try to make posts related to some topics through a simple copy and paste. Others make use of user authentication information given by a service platform or user self description (introduction or label) in finding influential users. However, what users have published is not necessarily related to what they have registed and described. In addition, if there is no comments from other users, it’s less objective to assess a user’s post quality. To improve effectiveness of recognizing influential users in a topic of microblogs, we propose a post-feature based approach which is supplementary to post-content based approaches. Our experimental results show that the post-feature based approach produces relatively higher precision than that of the content based approach.

One challenge of link prediction in online social networks is the large scale of many such networks. The measures used by existing work lack a computational consideration in the large scale setting. We propose the notion of social distance in a multi-dimensional form to measure the closeness among a group of people in Microblogs. We proposed a fast hashing approach called Locality-sensitive Social Distance Hashing (LSDH), which works in an unsupervised setup and performs approximate near neighbor search without high-dimensional distance computation. Experiments were applied over a Twitter dataset and the preliminary results testified the effectiveness of LSDH in predicting the likelihood of future associations between people.

Keepaway soccer is a challenging robot control task that has been widely used as a benchmark for evaluating multi-agent learning systems. The majority of research in this domain has been from the perspective of reinforcement learning (function approximation) and neuroevolution. One of the challenges under multi-agent tasks such as keepaway is to formulate effective mechanisms for diversity maintenance. Indeed the best results to date on this task utilize some form of neuroevolution with genotypic diversity. In this work, a symbiotic framework for evolving teams of programs is utilized with both genotypic and behavioural forms of diversity maintenance considered. Specific contributions of this work include a simple scheme for characterizing genotypic diversity under teams of programs and its comparison to behavioural formulations for diversity under the keepaway soccer task. Unlike previous research concerning diversity maintenance in genetic programming (GP), we are explicitly interested in solutions taking the form of teams of programs.

Today, people benefit from utilizing data mining technologies, such as association rule mining methods, to find valuable knowledge residing in a large amount of data. However, they also face the risk of exposing sensitive or confidential information, when data is shared among different organizations. Thus, a question arise: how can we prevent that sensitive knowledge is discovered, while ensuring that ordinary non-sensitive knowledge can be mined to the maximum extent possible. In this paper, we address the problem of privacy preserving in association rule mining from the perspective of multi-objective optimization. A new hiding method based evolutionary multi-objective optimization (EMO) is proposed and the side effects generated by the hiding process are formulated as optimization goals. EMO is used to find candidate transactions to modify so that side effects are minimized. Comparative experiments with exact methods on real datasets demonstrated that the proposed method can hide sensitive rules with fewer side effects.

Choice selection processes are a family of bilateral games of incomplete information in which a computer agent generates advice for a human user while considering the effect of the advice on the user's behavior in future interactions. The human and the agent may share certain goals, but are essentially self-interested. This paper extends selection processes to settings in which the actions available to the human are ordered and thus the user may be influenced by the advice even though he doesn't necessarily follow it exactly. In this work we also consider the case in which the user obtains some observation on the sate of the world. We propose several approaches to model human decision making in such settings. We incorporate these models into two optimization techniques for the agent advice provision strategy. In the first one the agent used a social utility approach which considered the benefits and costs for both agent and person when making suggestions. In the second approach we simplified the human model in order to allow modeling and solving the agent strategy as an MDP. In an empirical evaluation involving human users on AMT, we showed that the social utility approach significantly outperformed the MDP approach.

We provide an approach to estimate trust between agents from their interactions. Our approach takes a probabilistic model of trust founded on commitments. We assume commitments to estimate trust because a commitment describes what an agent may expect of another. Therefore, the satisfaction or violation of a commitment provides a natural basis for determining how much to trust another agent. We evaluate our approach empirically. In one study, 30 subjects read emails extracted from the Enron dataset augmented with some synthetic emails to capture commitment operations missing in the Enron corpus. The subjects estimated trust between each pair of communicating participants. We trained model parameters for each subject with respect to our automated analysis of the emails, showing that our trained parameters yield a lower prediction error of a subject's trust rating given automatically inferred commitments than fixed parameters.