Human-based evolutionary computation
Encyclopedia
Human-based evolutionary computation (HBEC) is a set of evolutionary computation
techniques that rely on human innovation. Human-based evolutionary computation techniques can be classified into three more specific classes analogous to ones in evolutionary computation. There are three basic types of innovation: initialization, mutation, and recombination. Here is a table illustrating which type of human innovation are supported in different classes of HBEC:
All these three classes also have to implement selection, performed either by humans or by computers.
Because the concept seems too simple, most of the websites implementing the idea can't avoid the common pitfall: informational cascade
in soliciting human preference. For example, digg
-style implementations, pervasive on the web, heavily bias subsequent human evaluations by prior ones by showing how many votes the items already have. This makes the aggregated evaluation depend on a very small initial sample of rarely independent evaluations. This encourages many people to game the system that might add to digg's popularity but detract from the quality of the featured results. It is too easy to submit evaluation in digg-style system based only on the content title, without reading the actual content supposed to be evaluated.
A better example of a human-based selection system is Stumbleupon
. In Stumbleupon, users first experience the content (stumble upon it), and can then submit their preference by pressing a thumb-up or thumb-down button. Because the user doesn't see the number of votes given to the site by previous users, Stumbleupon can collect a relatively unbiased set of user preferences, and thus evaluate content much more precisely.
has three operators: initialization, mutation, and selection. In the case of Wikipedia, the initialization operator is page creation, the mutation operator is incremental page editing. The selection operator is less salient. It is provided by the revision history and the ability to select among all previous revisions via a revert operation. If the page is vandalised and no longer a good fit to its title, a reader can easily go to the revision history and select one of the previous revisions that fits best (hopefully, the previous one). This selection feature is crucial to the success of the Wikipedia.
An interesting fact is that the original wiki software was created in 1995, but it took at least another six years for large wiki-based collaborative projects to appear. Why did it take so long? One explanation is that the original wiki software lacked a selection operation and hence couldn't effectively support content evolution. The addition of revision history and the rise of large wiki-supported communities coincide in time. From an evolutionary computation point of view, this is not surprising: without a selection operation the content would undergo an aimless genetic drift
and would unlikely to be useful to anyone. That is what many people expected from Wikipedia at its inception. However, with a selection operation, the utility of content has a tendency to improve over time as beneficial changes accumulate. This is what actually happens on a large scale in Wikipedia.
s). Recombination operator brings together highly fit parts of different solutions that evolved independently. This makes the evolutionary process more efficient. The HBGA methodology was derived in 1999-2000 from the analysis of Free Knowledge Exchange project that was launched in summer 1998 in Russia. Currently, several other projects implement the same model, the most popular is Yahoo! Answers
launched in December 2005.
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
techniques that rely on human innovation. Human-based evolutionary computation techniques can be classified into three more specific classes analogous to ones in evolutionary computation. There are three basic types of innovation: initialization, mutation, and recombination. Here is a table illustrating which type of human innovation are supported in different classes of HBEC:
| Initialization | Mutation | Recombination | |
| Human-based selection strategy | X | ||
|---|---|---|---|
| Human-based evolution strategy | X | X | |
| Human-based genetic algorithm | X | X | X |
All these three classes also have to implement selection, performed either by humans or by computers.
Human-based selection strategy
Human-based selection strategy is a simplest human-based evolutionary computation procedure. It is used heavily today by websites outsourcing collection and selection of the content to humans (user-contributed content). Viewed as evolutionary computation, their mechanism supports two operations: initialization (when a user adds a new item) and selection (when a user expresses preference among items). The website software aggregates the preferences to compute the fitness of items so that it can promote the fittest items and discard the worst ones. Several methods of human-based selection were analytically compared in (Kosorukoff, 2000; Gentry, 2005).Because the concept seems too simple, most of the websites implementing the idea can't avoid the common pitfall: informational cascade
Informational cascade
An information cascade occurs when people observe the actions of others and then make the same choice that the others have made, independently of their own private information signals...
in soliciting human preference. For example, digg
Digg
Digg is a social news website. Prior to Digg v4, its cornerstone function consisted of letting people vote stories up or down, called digging and burying, respectively. Digg's popularity prompted the creation of copycat social networking sites with story submission and voting systems...
-style implementations, pervasive on the web, heavily bias subsequent human evaluations by prior ones by showing how many votes the items already have. This makes the aggregated evaluation depend on a very small initial sample of rarely independent evaluations. This encourages many people to game the system that might add to digg's popularity but detract from the quality of the featured results. It is too easy to submit evaluation in digg-style system based only on the content title, without reading the actual content supposed to be evaluated.
A better example of a human-based selection system is Stumbleupon
StumbleUpon
StumbleUpon is a discovery engine that finds and recommends web content to its users. Its features allow users to discover and rate Web pages, photos, and videos that are personalized to their tastes and interests using peer-sourcing and social-networking principles.Toolbar versions exist for...
. In Stumbleupon, users first experience the content (stumble upon it), and can then submit their preference by pressing a thumb-up or thumb-down button. Because the user doesn't see the number of votes given to the site by previous users, Stumbleupon can collect a relatively unbiased set of user preferences, and thus evaluate content much more precisely.
Human-based evolution strategy
In this context and maybe generally, the Wikipedia software is the best illustration of a working human-based evolution strategy wherein the (targeted) evolution of any given page comprises the fine tuning of the knowledge base of such information that relates to that page. Traditional evolution strategyEvolution strategy
In computer science, evolution strategy is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.-History:...
has three operators: initialization, mutation, and selection. In the case of Wikipedia, the initialization operator is page creation, the mutation operator is incremental page editing. The selection operator is less salient. It is provided by the revision history and the ability to select among all previous revisions via a revert operation. If the page is vandalised and no longer a good fit to its title, a reader can easily go to the revision history and select one of the previous revisions that fits best (hopefully, the previous one). This selection feature is crucial to the success of the Wikipedia.
An interesting fact is that the original wiki software was created in 1995, but it took at least another six years for large wiki-based collaborative projects to appear. Why did it take so long? One explanation is that the original wiki software lacked a selection operation and hence couldn't effectively support content evolution. The addition of revision history and the rise of large wiki-supported communities coincide in time. From an evolutionary computation point of view, this is not surprising: without a selection operation the content would undergo an aimless genetic drift
Genetic drift
Genetic drift or allelic drift is the change in the frequency of a gene variant in a population due to random sampling.The alleles in the offspring are a sample of those in the parents, and chance has a role in determining whether a given individual survives and reproduces...
and would unlikely to be useful to anyone. That is what many people expected from Wikipedia at its inception. However, with a selection operation, the utility of content has a tendency to improve over time as beneficial changes accumulate. This is what actually happens on a large scale in Wikipedia.
Human-based genetic algorithm
Human-based genetic algorithm (HBGA) provides means for human-based recombination operation (a distinctive feature of genetic algorithmGenetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s). Recombination operator brings together highly fit parts of different solutions that evolved independently. This makes the evolutionary process more efficient. The HBGA methodology was derived in 1999-2000 from the analysis of Free Knowledge Exchange project that was launched in summer 1998 in Russia. Currently, several other projects implement the same model, the most popular is Yahoo! Answers
Yahoo! Answers
Yahoo! Answers is a community-driven question-and-answer site or a knowledge market launched by Yahoo! on June 28, 2005 that allows users to both submit questions to be answered and answer questions asked by other users...
launched in December 2005.