Models of collaborative tagging
Encyclopedia
Many have argued that social tagging or collaborative tagging systems can provide navigational cues or “way-finders” for other users to explore information. The notion is that, given that social tags are labels that users create to represent topics extracted from Web documents, interpretation of these tags should allow other users to predict contents of different documents efficiently. Social tags are arguably more important in exploratory search
, in which the users may engage in iterative cycles of goal refinement and exploration of new information (as opposed to simple fact-retrievals), and interpretation of information contents by others will provide useful cues for people to discover topics that are relevant.
One significant challenge that arises in social tagging systems is the rapid increase in the number and diversity of the tags. As opposed to structured annotation systems, tags provide users an unstructured, open-ended mechanism to annotate and organize web-content. As users are free to create any tag to describe any resource, it leads to what is referred to as the vocabulary problem. Because users may use different words to describe the same document or extract different topics from the same document based on their own background knowledge, the lack of a top-down mediation may lead to an increase in the use of incoherent tags to represent the information resources in the system. In other words, the inherent "unstructuredness" of social tags may hinder their potential as navigational cues for searchers because the diversities of users and motivation may lead to diminishing tag-topic relations as the system grows.
Another way to look at the data is to think about Mutual Information, which is a measure of independence between the two variables. Full independence is reached when I(D;T) = 0. Chi and Mytkowicz research on delicious social tagging data show that as a measure of usefulness of the tags and their encoding, there is a worsening trend in the ability of users to specify and find tags and documents when they are engaged in simple fact retrieval. This suggests that we need to build search and recommendation systems that help users sift through resources in social tagging systems, especially when we are engaged in more than simple fact retrieval as characterized by the information theory. In fact, although the number of documents associated with any given tag is increasing, there are many ways contextual information can help users to look for relevant information. This is in fact one of the major weakness of the simple information theory in explaining usefulness of tags—it ignores the fact that humans can extract meanings from a set of tags assigned to a document, and this semantic extraction process is exactly the reason why humans are able to communicate efficiently even though the size of our vocabulary is increasing ever since language was developed. For example, the work by Cattuto et al. (2007), published in PNAS, show that while the number of tags are increasing, the general growth pattern is scale-free—the general distribution of tag-tag co-occurrences follows a power-law. Cattuto also finds that the characteristics of this scale-free distribution are dependent on the semantics of the tag—tags that are semantically general (e.g., blogs) tend to co-occur with many tags, while semantically narrow tags (e.g., Ajax) tend to co-occur with few number of tags across a wide set of documents in a social tagging system. What this means is that the assumption of the information theory approach is too simple—when the semantics of the set of tags assigned to documents are taken into account, the predictive value of tags on contents of documents are relatively stable. This finding is important for development of recommender systems—discovering these higher level semantic patterns is important in helping people to find relevant information (also see semantic imitation model below).
One explanation for the stability was that there was an inherent propensity for users to ”imitate" word use of others as they create tags. This propensity may act as a form of social cohesion that fosters the coherence of tag-topic relations in the system, and leads to stability in the system. Golder and Huberman showed that the stochastic urn model by Eggenberger and Polya was useful in explaining how simple imitation behavior at the individual level could explain the converging usage patterns of tags. Specifically, convergence of tag choices was simulated by a process in which a colored ball was randomly selected from an urn and was replaced in the urn along with an additional ball of the same color, simulating the probabilistic nature of tag reuse. The simple model, however, does not explain why certain tags would to be “imitated” more often than others, and therefore cannot provide a realistic mechanism for tag choices and how social tags could be utilized as navigational cues during exploratory search, not to mention the obviously over-simplified representation of individual users by balls in an urn.
, has shown that collaborative tagging systems exhibit a form of complex system
s (or self-organizing
) dynamics. Furthermore, although there is no central controlled vocabulary to constrain the actions of individual users, the distributions of tags that describe different resources has been shown to converge over time to a stable power law
distributions. Once such stable distributions form, examining the correlation
s between different tags can be used to construct simple folksonomy graphs, which can be efficiently partitioned to obtain a form of community or shared vocabularies. Such vocabularies can be seen as emerging from the decentralised actions of many users, as a form of crowdsourcing
.
Rather than imitating other users at the word level, one possible explanation for this kind of social cohesion could be grounded on the natural tendency for people to process tags at the semantic level, and it was at this level of processing that most imitation occurred. This explanation was supported by research in the area of reading comprehension, which showed that people tended to be influenced by meanings of words, rather than the words themselves during comprehension. Assuming that background knowledge of people in the same culture tend to have shared structures (e.g., using similar vocabularies and their corresponding meanings in order to conform and communicate with each), users of the same social tagging system may also share similar semantic representations of words and concepts, even when the use of tags may vary across individuals at the word level. In other words, we argued that part of the reason for the stability of social tagging systems can be attributed to the shared semantic representations among the users, such that users may have relatively stable and coherent interpretation of information contents and tags as they interact with the system. Based on this assumption, the semantic imitation model
predicts how different semantic representations may lead to differences in individual tag choices and eventually different emergent properties at the aggregate behavioral level. The model also predicts that the folksonomies (i.e., knowledge structures) in the system reflect the shared semantic representations of the users.
Semantic imitation has important implication to the general vocabulary problem (see work by, e.g., Susan Dumais
) in information retrieval and human-computer interaction—the creation of large number of diverse tags to describe the same set of information resource. The finding that semantic imitation occurs implies that the unit of communication among users is more likely at the semantic level, not at the word level. Thus, although there may not be strong coherence in the choice of words in describing a resource, at the semantic level there seems to be a stronger coherence force that guides the convergence of descriptive indices. This is in sharp contrast to conclusions derived based on a purely information-theoretical approach, which assumes that humans search and evaluation information at the word level. Instead, the process of semantic imitation in social tagging implies that the information-theoretic approach is at most incomplete, as it does not take into account the basic unit of human information processing. Similar to the fact that human communication occurs at the semantic level, the fact that people may use different words or syntax does not impact the effectiveness of communication, so long as the underlying "common ground" between the two persons is the same. In the social tagging case, so long as users share similar understanding of the contents of the information resources, the fact that the information value of tag-document decreases (that humans have more words in their languages) do not imply that it will always be harder to find relevant information (similarly, the fact that there are more words in our languages does not mean that our communication becomes less effective). However, it does point to the notion that one needs to effectively present these semantic structures in the information system so that people can effectively interpret the semantics of the tagged documents. Intelligent techniques based on statistical models of language such as Latent semantic analysis
, probabilistic topics model, etc. are promising aspects that will overcome this vocabulary problem.
Exploratory search
Exploratory search is a specialization of information exploration which represents the activities carried out by searchers who are either:[1]* a) unfamiliar with the domain of their goal * b) unsure about the ways to achieve their goals * c) or even unsure about their...
, in which the users may engage in iterative cycles of goal refinement and exploration of new information (as opposed to simple fact-retrievals), and interpretation of information contents by others will provide useful cues for people to discover topics that are relevant.
One significant challenge that arises in social tagging systems is the rapid increase in the number and diversity of the tags. As opposed to structured annotation systems, tags provide users an unstructured, open-ended mechanism to annotate and organize web-content. As users are free to create any tag to describe any resource, it leads to what is referred to as the vocabulary problem. Because users may use different words to describe the same document or extract different topics from the same document based on their own background knowledge, the lack of a top-down mediation may lead to an increase in the use of incoherent tags to represent the information resources in the system. In other words, the inherent "unstructuredness" of social tags may hinder their potential as navigational cues for searchers because the diversities of users and motivation may lead to diminishing tag-topic relations as the system grows.
The distinction between descriptive and predictive models
Just like any social phenomena, behavioral patterns in social tagging systems can be characterized by either a descriptive or predictive model. While descriptive models ask the question of "what", predictive models go deeper to also ask the question of "why" by attempting to provide explanations to the aggregate behavioral patterns While there may be no general agreement on what an acceptable explanation should be like, many believe that a good explanation should have certain level of predictive accuracy. Descriptive models of social tagging typically are not concerned with explaining the actions of single individuals but describing the patterns that emerge as individual behavior is aggregated in a large social information system. Predictive models, however, attempts to explain aggregate patterns by analyzing how individuals interact and link to each other in ways that bring about similar or different emergent patterns of social behavior. In particular, a mechanism-based predictive model assumes a certain set of rule that individuals interact with each other, and understand how these interactions could produce aggregate patterns as observed and characterized by descriptive models. Predictive models can therefore provide explanations to why different system characteristics may lead to different aggregate patterns, and can therefore potentially provide information on how systems should be designed to achieve different social purposes.Information Theory Models
For most tagging systems the total number of tags in the collective vocabulary is much less than the total number of objects being tagged. Given this multiplicity of tags to documents, a question remains: how effective are the tags at isolating any single document? Naively, if we specify a single tag in this system we would uniquely identify lots of documents — thus the answer to our question is “not very well!”. However this method carries a faulty assumption; not every document is equal. Some documents are more popular and important than others, and this importance is conveyed by the number bookmarks per document. Thus, we can reformulate the above question to be: how well does the mapping of tags to documents retain about the distribution of the documents? Information theory provides a natural framework to understand the amount of shared information between two random variables. The conditional entropy measures the amount of entropy remaining in one random variable when we know the value of a second random variable. Work done by Chi and Mytkowicz show that the entropy of documents conditional on tags, H(D|T), is increasing rapidly. What this means is that, even after knowing completely the value of a tag, the entropy of the set of documents is increasing over time. Conditional Entropy asks the question: “Given that I know a set of tags, how much uncertainty regarding the document set that I was referencing with those tags remains?” The fact that this curve is strictly increasing suggests that the specificity of any given tag is decreasing. That is to say, as a navigation aid, tags are becoming harder and harder to use. We are moving closer and closer to the proverbial “needle in a haystack” where any single tag references too many documents to be considered useful.Another way to look at the data is to think about Mutual Information, which is a measure of independence between the two variables. Full independence is reached when I(D;T) = 0. Chi and Mytkowicz research on delicious social tagging data show that as a measure of usefulness of the tags and their encoding, there is a worsening trend in the ability of users to specify and find tags and documents when they are engaged in simple fact retrieval. This suggests that we need to build search and recommendation systems that help users sift through resources in social tagging systems, especially when we are engaged in more than simple fact retrieval as characterized by the information theory. In fact, although the number of documents associated with any given tag is increasing, there are many ways contextual information can help users to look for relevant information. This is in fact one of the major weakness of the simple information theory in explaining usefulness of tags—it ignores the fact that humans can extract meanings from a set of tags assigned to a document, and this semantic extraction process is exactly the reason why humans are able to communicate efficiently even though the size of our vocabulary is increasing ever since language was developed. For example, the work by Cattuto et al. (2007), published in PNAS, show that while the number of tags are increasing, the general growth pattern is scale-free—the general distribution of tag-tag co-occurrences follows a power-law. Cattuto also finds that the characteristics of this scale-free distribution are dependent on the semantics of the tag—tags that are semantically general (e.g., blogs) tend to co-occur with many tags, while semantically narrow tags (e.g., Ajax) tend to co-occur with few number of tags across a wide set of documents in a social tagging system. What this means is that the assumption of the information theory approach is too simple—when the semantics of the set of tags assigned to documents are taken into account, the predictive value of tags on contents of documents are relatively stable. This finding is important for development of recommender systems—discovering these higher level semantic patterns is important in helping people to find relevant information (also see semantic imitation model below).
Tag convergence
Despite this potential vocabulary problem, recent research has found that at the aggregate level, tagging behavior seemed relatively stable and that the tag choice proportions seemed to be converging rather than diverging. While these observations provided evidence against the proposed vocabulary problem, they also triggered a series of research investigating how and why tag proportions tended to converge over time.One explanation for the stability was that there was an inherent propensity for users to ”imitate" word use of others as they create tags. This propensity may act as a form of social cohesion that fosters the coherence of tag-topic relations in the system, and leads to stability in the system. Golder and Huberman showed that the stochastic urn model by Eggenberger and Polya was useful in explaining how simple imitation behavior at the individual level could explain the converging usage patterns of tags. Specifically, convergence of tag choices was simulated by a process in which a colored ball was randomly selected from an urn and was replaced in the urn along with an additional ball of the same color, simulating the probabilistic nature of tag reuse. The simple model, however, does not explain why certain tags would to be “imitated” more often than others, and therefore cannot provide a realistic mechanism for tag choices and how social tags could be utilized as navigational cues during exploratory search, not to mention the obviously over-simplified representation of individual users by balls in an urn.
Complex systems dynamics and emergent vocabularies
Other research, using data from the social bookmarking website Del.icio.usDel.icio.us
Delicious is a social bookmarking web service for storing, sharing, and discovering web bookmarks. The site was founded by Joshua Schachter in 2003 and acquired by Yahoo! in 2005, and by the end of 2008, the service claimed more than 5.3 million users and 180 million unique bookmarked URLs...
, has shown that collaborative tagging systems exhibit a form of complex system
Complex system
A complex system is a system composed of interconnected parts that as a whole exhibit one or more properties not obvious from the properties of the individual parts....
s (or self-organizing
Self-organization
Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning...
) dynamics. Furthermore, although there is no central controlled vocabulary to constrain the actions of individual users, the distributions of tags that describe different resources has been shown to converge over time to a stable power law
Power law
A power law is a special kind of mathematical relationship between two quantities. When the frequency of an event varies as a power of some attribute of that event , the frequency is said to follow a power law. For instance, the number of cities having a certain population size is found to vary...
distributions. Once such stable distributions form, examining the correlation
Correlation
In statistics, dependence refers to any statistical relationship between two random variables or two sets of data. Correlation refers to any of a broad class of statistical relationships involving dependence....
s between different tags can be used to construct simple folksonomy graphs, which can be efficiently partitioned to obtain a form of community or shared vocabularies. Such vocabularies can be seen as emerging from the decentralised actions of many users, as a form of crowdsourcing
Crowdsourcing
Crowdsourcing is the act of sourcing tasks traditionally performed by specific individuals to a group of people or community through an open call....
.
Tag choice by stochastic process
The memory-based Yule-Simon (MBYS) model of Cattuto attempted to explain tag choices by a stochastic process. They found that the temporal order of tag assignment has an impact on users’ tag choices. Similar to the stochastic urn model, the MBYS model assumed that at each time step a tag would be randomly sampled: with probability p the sampled tag was new, and with probability 1-p the sampled tag was copied from existing tags. When copying, the probability of selecting a tag was assumed to decay with time, and this decay function was found to follow a power law distribution. Thus, tags that were recently used had a higher probability of being reused than those used in the past. One major finding by Cattuto et al. was that semantically general tags (e.g., “blog”) tended to co-occur more frequently with other tags than semantically narrower tags (e.g., “ajax”), and this difference could be captured by the decay function of tag reuse in their model. Specifically, they found that a slower decay parameter (when the tag is reused more often) could explain the phenomenon that semantically general tags tended to co-occur with a larger set of tags. In other words, they argued that the “semantic breadth” of a tag could be modeled by a memory decay function, which could lead to different emergent behavioral patterns in a tagging system.Semantic Imitation Model of Social Tag Choices
Descriptive models mentioned above were based on analyses of word-word relations as revealed by the various statistical structures in the organization of tags (e.g., how likely one tag would co-occur with other tags or how likely each tag was reused over time). These models are therefore descriptive models at the aggregate level, and have little to offer about predictions at the level of interface interactions and cognitive processes of individual.Rather than imitating other users at the word level, one possible explanation for this kind of social cohesion could be grounded on the natural tendency for people to process tags at the semantic level, and it was at this level of processing that most imitation occurred. This explanation was supported by research in the area of reading comprehension, which showed that people tended to be influenced by meanings of words, rather than the words themselves during comprehension. Assuming that background knowledge of people in the same culture tend to have shared structures (e.g., using similar vocabularies and their corresponding meanings in order to conform and communicate with each), users of the same social tagging system may also share similar semantic representations of words and concepts, even when the use of tags may vary across individuals at the word level. In other words, we argued that part of the reason for the stability of social tagging systems can be attributed to the shared semantic representations among the users, such that users may have relatively stable and coherent interpretation of information contents and tags as they interact with the system. Based on this assumption, the semantic imitation model
predicts how different semantic representations may lead to differences in individual tag choices and eventually different emergent properties at the aggregate behavioral level. The model also predicts that the folksonomies (i.e., knowledge structures) in the system reflect the shared semantic representations of the users.
Semantic imitation has important implication to the general vocabulary problem (see work by, e.g., Susan Dumais
Susan Dumais
Susan Dumais is a Principal Researcher in the Context, Learning, and User Experience for Search Group of Microsoft Research and an Affiliate Professor at the University of Washington Information School....
) in information retrieval and human-computer interaction—the creation of large number of diverse tags to describe the same set of information resource. The finding that semantic imitation occurs implies that the unit of communication among users is more likely at the semantic level, not at the word level. Thus, although there may not be strong coherence in the choice of words in describing a resource, at the semantic level there seems to be a stronger coherence force that guides the convergence of descriptive indices. This is in sharp contrast to conclusions derived based on a purely information-theoretical approach, which assumes that humans search and evaluation information at the word level. Instead, the process of semantic imitation in social tagging implies that the information-theoretic approach is at most incomplete, as it does not take into account the basic unit of human information processing. Similar to the fact that human communication occurs at the semantic level, the fact that people may use different words or syntax does not impact the effectiveness of communication, so long as the underlying "common ground" between the two persons is the same. In the social tagging case, so long as users share similar understanding of the contents of the information resources, the fact that the information value of tag-document decreases (that humans have more words in their languages) do not imply that it will always be harder to find relevant information (similarly, the fact that there are more words in our languages does not mean that our communication becomes less effective). However, it does point to the notion that one needs to effectively present these semantic structures in the information system so that people can effectively interpret the semantics of the tagged documents. Intelligent techniques based on statistical models of language such as Latent semantic analysis
Latent semantic analysis
Latent semantic analysis is a technique in natural language processing, in particular in vectorial semantics, of analyzing relationships between a set of documents and the terms they contain by producing a set of concepts related to the documents and terms. LSA assumes that words that are close...
, probabilistic topics model, etc. are promising aspects that will overcome this vocabulary problem.
See also
- Collaborative filteringCollaborative filteringCollaborative filtering is the process of filtering for information or patterns using techniques involving collaboration among multiple agents, viewpoints, data sources, etc. Applications of collaborative filtering typically involve very large data sets...
- Collaborative tagging
- Knowledge tagging
- Social tagging
- Social collaborationSocial collaborationSocial collaboration refers to processes that help multiple people interact, share information to achieve any common goal. Such processes find their 'natural' environment on the internet, where collaboration and social dissemination of information are made easier by current innovations.Sharing...