207161230
FeedMe: a collaborative alert filtering system
As the number of alerts generated by collaborative applications grows, users receive more unwanted alerts. FeedMe is a general alert management system based on XML feed protocols such as RSS and ATOM. In addition to traditional rule-based alert filtering, FeedMe uses techniques from machine-learning to infer alert preferences based on user feedback. In this paper, we present and evaluate a new collaborative naïve Bayes filtering algorithm. Using FeedMe, we collected alert ratings from 33 users over 29 days. We used the data to design and verify the accuracy of the filtering algorithm and provide insights into alert prediction.
16584682
You are what you say: privacy risks of public mentions
In today's data-rich networked world, people express many aspects of their lives online. It is common to segregate different aspects in different places: you might write opinionated rants about movies in your blog under a pseudonym while participating in a forum or web site for scholarly discussion of medical ethics under your real name. However, it may be possible to link these separate identities, because the movies, journal articles, or authors you mention are from a sparse relation space whose properties (e.g., many items related to by only a few users) allow re-identification. This re-identification violates people's intentions to separate aspects of their life and can have negative consequences; it also may allow other privacy violations, such as obtaining a stronger identifier like name and address.This paper examines this general problem in a specific setting: re-identification of users from a public web movie forum in a private movie ratings dataset. We present three major results. First, we develop algorithms that can re-identify a large proportion of public users in a sparse relation space. Second, we evaluate whether private dataset owners can protect user privacy by hiding data; we show that this requires extensive and undesirable changes to the dataset, making it impractical. Third, we evaluate two methods for users in a public forum to protect their own privacy, suppression and misdirection. Suppression doesn't work here either. However, we show that a simple misdirection strategy works well: mention a few popular items that you haven't rated.
207161263
tagging, communities, vocabulary, evolution
A tagging community's vocabulary of tags forms the basis for social navigation and shared expression.We present a user-centric model of vocabulary evolution in tagging communities based on community influence and personal tendency. We evaluate our model in an emergent tagging system by introducing tagging features into the MovieLens recommender system.We explore four tag selection algorithms for displaying tags applied by other community members. We analyze the algorithms 'effect on vocabulary evolution, tag utility, tag adoption, and user satisfaction.
16723670
PLEASE: A Prototype Learning System Using Genetic Algorithms
Prototypes have been proposed as representation of concepts that are used eeec-tively by humans. Developing computational schemes for generating prototypes from examples , however, has proved to be a dii-cult problem. We present a novel genetic algorithm based prototype learning system, PLEASE, for constructing appropriate prototypes from classiied training instances. After constructing a set of prototypes for each of the possible classes, the class of a new input instance is determined by the nearest prototype to this instance. Attributes are assumed to be ordinal in nature and prototypes are represented as sets of feature-value pairs. A genetic algorithm is used to evolve the number of prototypes per class and their positions on the input space. We present experimental results on a series of artiicial problems of varying complexity. PLEASE performs competitively with several nearest neighbor clas-siication algorithms on the problem set. An analysis of the strengths and weaknesses of the initial version of our system motivates the need for additional operators. The inclusion of these operators substantially improves the performance of the system on particularly diicult problems.
9417710
Using real-valued genetic algorithms to evolve rule sets for classification
In this paper, we use a genetic algorithm to evolve a set of classification rules with real-valued attributes. We show how real-valued attribute ranges could be encoded with real-valued genes and present a new uniform method for representing don't cares in the rules. We view supervised classification as an optimization problem, and evolve rule sets that maximize the number of correct classifications of input instances. We use a variant of the Pitt approach to genetic-based machine learning system with a novel conflict resolution mechanism between competing rules within the same rule set. Experimental results demonstrate the effectiveness of our proposed approach on a benchmark wine classifier system.<<ETX>>
9655275
Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems
We describe a deterministic parallel algorithm for linear programming in fixed dimension d that takes poly(log log n) time in the common concurrent read concurrent write (CRCW) PRAM model and does optimal O(n) work. In the exclusive read exclusive write (EREW) model, the algorithm runs in O(log n · log logd-1 n) time. Our algorithm is based on multidimensional search and effective use of approximation algorithms to speed up the basic search in the CRCW model. Our method also yields very fast poly(log log n) algorithms for smallest enclosing sphere and approximate ham-sandwich cuts and an O(log n) time work-optimal algorithm for exact ham-sandwich cuts of separable point sets. For these problems, in particular for fixed-dimensional linear programming, o(log n) time efficient deterministic PRAM algorithms were not known until very recently.
35225520
Some Observations on Skip-Lists
The Skip-list data-structure was proposed by Pugh as an alternate to balanced binary search trees. This remarkably simple data-structure uses randomization and Pugh proved that the expected performance is comparable to the balanced trees. In this note we prove that the performance can be further guaranteed in the following sense: the probability of the search time or space complexity exceeding their expected values, approaches 0 rapidly as the number of keys increases.
3529746
Effects of misconception on reciprocative agents
In open systems, agents act to serve their self-interests instead of working towards group goals. We investigate the choice of interaction strategies and environmental characteristics that will make the best self-interested actions to be cooperative in nature. In our previous work, we have presented a probabilistic reciprocity mechanism that produces stable, cooperative behavior among a group of self-interested agents. The resultant system was found to exhibit close to optimal throughput with a fair distribution of the workload among the participating agents. In this paper, we test the robustness of this scheme by changing some of the assumptions used before. In particular, we evaluate the performance of reciprocative agents when an agent receiving help from another agent underestimates the cost incurred by the helping agent. This kind of misconceptions can derail cooperative processes leading to disintegration of stable groups. Results from experiments with several kinds of misconceptions , however, testify to the robustness of the reciprocative strategy. 1 Introduction Researchers involved in the design of intelligent agents that will interact with other agents in an open, distributed system are faced with the challenge of modeling other agents and their behavior 5]. If one can can assume that all agents will be cooperative in nature, eecient mechanisms can be developed to take advantage of mutual cooperation. But, in an open system, assumptions about cooperative agents or system-wide common goals are hard to justify. More often, we will nd diierent agents have diierent goals and motivations and no real inclination to help another agent achieve its objectives. We assume agents to be self-motivated in their interactions with other agents, and that interacting agents are uniquely identiiable. An agent may help others in performing tasks. We develop a criteria for an agent to decide to help or not to help another agent when the latter requests for help. The decision criteria should be such that it al