Sentiment detection as a ranking signal for reviewable entities

A method, a system and a computer program product for ranking reviewable entities based on sentiment expressed about the entities. A plurality of review texts are identified wherein each review text references an entity. A plurality of sentiment scores associated with the plurality of review texts are generated, wherein each sentiment score for a review text indicates a sentiment directed to the entity referenced by the review text. A plurality of ranking scores for the plurality of entities are generated wherein each ranking score is based at least in part on one or more sentiment scores associated with one or more review texts referencing the entity. A plurality of search results associated with the plurality of entities are displayed based at least in part on the ranking scores.

CROSS-REFERENCE TO RELATED APPLICATIONS

The present application is related to U.S. patent application Ser. No. 11/844,222 “Domain-Specific Sentiment Classification” filed Aug. 23, 2007, the disclosure of which is incorporated herein by reference.

BACKGROUND

This invention pertains in general to natural language processing and in particular to automated sentiment classification to provide rankings of documents.

2. Description of the Related Art

Determining indicators of search result relevance and ranking the search results according to these indicators is an integral function of web search engines. Common indicators of search result relevance include indicators of popularity such as number of links to a web page or number of page hits a day. Other indicators of popularity may be collected through monitoring user-interaction with search results. Monitoring user-interaction with search results produces metrics which indicate search result relevance such as user click through rates or average time spent by the user at a web page associated with a search result.

Often searches are performed for entities about which public opinion is expressed such as movies, restaurants and hotels. This opinion or sentiment is also a valuable indicator of the relevance of search results. For instance, if a user searches for French restaurants, it is most likely that a user would like to know of the restaurants that are the most favorably reviewed. Similarly, most users who search for a listing of hotels in a geographic area wish to see results containing the hotels with the best reviews. Users may be interested in search results for reviewable entities such as books and films for which strong public opinion is expressed, whether or not the opinion is favorable or unfavorable.

Attempts to use sentiment as a ranking signal for search results have commonly used structured reviews. In structured reviews, the reviewer selects a rating in addition to providing a textual review of the entity. Structured reviews can be conveniently used in ranking systems as most structured reviews use a numeric rating (e.g. a 5 star system or a scale of 1 to 10) that can easily be used to rank results. Results are ranked by their average numeric rating from the structured review. However, in instances where an entity has mixed reviews valuable information may be lost due to the averaging.

Another limitation of solely using ratings from structured reviews as indicators of search result relevance is that valuable information in the textual review regarding the sentiment or public opinion about the reviewable entities is discarded. In textual reviews sentiment is expressed through statement, allowing a finer level of precision or “granularity” than rankings and the ability to express different types of sentiment within a review (e.g. “food great, service bad”).

Textual reviews may also help correct for inconsistencies in ranking system normalization. For instance, a restaurant consistently rated at two stars by restaurant reviewers may be favorably reviewed by its patrons due to differences in ranking system scales. Incorporating the sentiment expressed within the textual reviews that accompany the ratings from both reviewers and patrons can help correct for these inconsistencies. Additionally, there are many other textual sources of sentiment outside of structured reviews such as blogs or personal web pages that may not be integrated into search result rankings based solely on structured ratings.

BRIEF SUMMARY OF THE INVENTION

The described embodiments provide a method, system and computer program product that generate ranking scores used to rank a plurality of reviewable entities.

One aspect provides a computer-implemented method of ranking reviewable entities. A plurality of review texts is identified, wherein each review text references an entity. A plurality of sentiment scores associated with the plurality of review texts are generated, wherein each sentiment score for a review text indicates a sentiment directed to the entity referenced by the review text. A plurality of ranking scores for the plurality of entities are generated wherein each ranking score is based at least in part on one or more sentiment scores associated with one or more review texts referencing the entity. The plurality of ranking scores are then stored.

In another aspect, the described embodiments provide a system for ranking reviewable entities. The system comprises a text selection module adapted to identify a plurality of review texts, wherein each review text references an entity. The system further comprises a sentiment score module adapted to generate a plurality of sentiment scores associated with the plurality of review texts, wherein each sentiment score for a review text indicates a sentiment directed to the entity referenced by the review text. The system further comprises a rank learning model adapted to generate a plurality of ranking scores for the plurality of entities wherein each ranking score is based at least in part on one or more sentiment scores associated with one or more review texts referencing the entity and store the plurality of ranking scores in a ranking database.

Another aspect is embodied as a computer-readable storage medium on which is encoded computer program code for ranking reviewable entities according to the above described method.

DETAILED DESCRIPTION

FIG. 1is a high-level block diagram of a computing environment100according to one embodiment.FIG. 1illustrates an Entity Ranking Data Repository140, and a Ranking Analysis Engine130connected to a Network114. AlthoughFIG. 1illustrates the Ranking Analysis Engine130as a single engine, in some embodiments the Ranking Analysis Engine130can have multiple engines. Likewise, there can be multiple Entity Ranking Data Repositories140on the Network114. Only one of each entity is illustrated in order to simplify and clarify the present description. There can be other entities on the Network114as well. In some embodiments, the Ranking Analysis Engine130and Entity Ranking Data Repository140are combined into a single entity.

The Ranking Analysis Engine130supports ranking of documents associated with reviewable entities. The Ranking Analysis Engine130uses the reviews stored in the Entity Sentiment Database142to identify text regarding entities. The Ranking Analysis Engine130is adapted to generate sentiment scores based on sentiment in the text regarding the entities. The Ranking Analysis Engine stores entity rankings generated based on sentiment scores in the Entity Ranking Database146. The Ranking Analysis Engine130also functions to modify the rankings in the Entity Ranking Database146based on the Entity Rating Database144. The Ranking Analysis Engine130is further adapted to modify the rankings in the Entity Ranking Database146based on a User Interaction Database148. In one embodiment, the Ranking Analysis Engine130learns and stores weights used to modify the rankings as a mixture model132.

The Entity Ranking Data Repository140stores structured reviews, unstructured reviews and other data used to rank search results for Reviewable Entities315. Reviewable Entities315include any person, place or thing about which opinion is likely to be expressed such as restaurants, hotels, consumer products such as electronics, films, books and live performances.

Structured reviews are known reviews of the Reviewable Entity315which adhere to a specific format including a defined rating of the reviewable entity and/or a textual review of the Reviewable Entity315. A structured review will typically have the following format, “0 stars; The pizza was horrible. Never going there again.”. In this instance, “0 stars” corresponds to the rating and “The pizza was horrible. Never going there again” corresponds to the Textual Review310. Structured reviews are collected through the Network114from known review web sites such as Google Maps, TripAdvisor, Citysearch or Yelp. Structured reviews can also be collected from other types of textual documents such as the text of books, newspapers and magazines.

Unstructured reviews are textual documents which reference the Reviewable Entity315that have a high likelihood of containing an opinion about the Reviewable Entity315. Unstructured reviews contain a Textual Review310but not a rating. Unstructured reviews usually contain sentiment expressed in documents with less structured formats than review websites such as newsgroups or blogs. Unstructured reviews are obtained through the Network114from sources of textual information which reference the entities including, but not limited to, web pages and/or portions of web pages, blogs, emails, newsgroup postings, and/or other electronic messages, etc. In some embodiments, unstructured reviews are analyzed to produce values which indicate the likelihood that the unstructured review pertains to the Reviewable Entity315and the unstructured review contains a sentiment or opinion about the Reviewable Entity315

In one embodiment, the Entity Ranking Data Repository140stores textual reviews from structured and unstructured reviews of the Reviewable Entity315in the Entity Sentiment Database142and ratings of the entity from structured reviews in the Entity Ratings Database144. In alternate embodiments, the textual reviews from structured and unstructured reviews of the reviewable entity and entity ratings may be stored in one corpus. According to the embodiment, the Entity Sentiment Database142may store a value which indicates the likelihood that an unstructured textual review contains an opinion or sentiment about the reviewable entity. In some embodiments, the Entity Sentiment Database142also contains a value which indicates the likelihood that the unstructured review pertains to the entity. In some embodiments, the ratings in the Entity Ratings Database144are normalized to a specified value.

The Entity Ranking Data Repository140further stores a User Interaction Database148. The User Interaction Database148stores user interaction metrics generated from monitoring user interactions with search results associated with entities.

The Entity Ranking Data Repository140further stores an Entity Ranking Database146. The Entity Ranking Database146combines and stores information from the Entity Sentiment Database142, the Entity Rating Database144and the User Interaction Database148used to rank the reviewable entities.

The Network114represents the communication pathways among the Ranking Analysis Engine130, the Entity Ranking Data Repository140, and any other entities connected to the Network114. In one embodiment, the Network114is the Internet. The Network114can also utilize dedicated or private communications links that are not necessarily part of the Internet. In one embodiment, the Network114uses standard communications technologies and/or protocols. Thus, the Network114can include links using technologies such as Ethernet, 802.11, integrated services digital network (ISDN), digital subscriber line (DSL), asynchronous transfer mode (ATM), etc. Similarly, the networking protocols used on the Network114can include multiprotocol label switching (MPLS), the transmission control protocol/Internet protocol (TCP/IP), the hypertext transport protocol (HTTP), the simple mail transfer protocol (SMTP), the file transfer protocol (FTP), the short message service (SMS) protocol, etc. The data exchanged over the Network114can be represented using technologies and/or formats including the HTML, the extensible markup language (XML), the Extensible Hypertext markup Language (XHTML), the compact HTML (cHTML), etc. In addition, all or some of links can be encrypted using conventional encryption technologies such as the secure sockets layer (SSL), HTTP over SSL (HTTPS), and/or virtual private networks (VPNs). In other embodiments, the Sentiment Analysis Engine110and Sentiment Analysis Data Repository112use custom and/or dedicated data communications technologies instead of, or in addition to, the ones described above.

FIG. 2is a high-level block diagram illustrating a functional view of a typical computer200for use as the Ranking Analysis Engine130and/or Entity Ranking Data Repository140illustrated in the environment100ofFIG. 1according to one embodiment. Illustrated are at least one processor202coupled to a bus204. Also coupled to the bus204are a memory206, a storage device208, a keyboard210, a graphics adapter212, a pointing device214, and a network adapter216. A display218is coupled to the graphics adapter212.

The processor202may be any general-purpose processor such as an INTEL x86 compatible-CPU. The storage device208is, in one embodiment, a hard disk drive but can also be any other device capable of storing data, such as a writeable compact disk (CD) or DVD, or a solid-state memory device. The memory206may be, for example, firmware, read-only memory (ROM), non-volatile random access memory (NVRAM), and/or RAM, and holds instructions and data used by the processor202. The pointing device214may be a mouse, track ball, or other type of pointing device, and is used in combination with the keyboard210to input data into the computer system200. The graphics adapter212displays images and other information on the display218. The network adapter216couples the computer200to the Network114.

As is known in the art, the computer200is adapted to execute computer program modules. As used herein, the term “module” refers to computer program logic and/or data for providing the specified functionality. A module can be implemented in hardware, firmware, and/or software. In one embodiment, the modules are stored on the storage device208, loaded into the memory206, and executed by the processor202.

The types of computers200used by the entities ofFIG. 1can vary depending upon the embodiment and the processing power required by the entity. The Ranking Analysis Engine130can include one or more distributed physical or logical computers operating together to provide the functionalities described herein. Likewise, the data repository can be provided by a storage area network (SAN), database management system (DBMS), or another storage system. The computers200can lack some of the components described above, such as keyboards210, graphics adapters212, and displays218.

FIG. 3Aillustrates the storage in memory of sentiment data associated with textual reviews of a Reviewable Entity315in the Entity Sentiment Database142according to one embodiment. Each Reviewable Entity315is represented by a tuple in the Entity Sentiment Database142. A tuple consists of an Entity ID302, an Entity Type300and one or more Reviews313. Each Review313consists of a Review ID204, a P(entity) value306, a P(sentiment) value308, and one or more Entity Review Texts318. Each Entity Review Text318contains an Entity Text ID314, Entity Text316and a Sentiment Score312. The Entity ID302be any kind of unique identifier that uniquely identifies (e.g., a primary key in the Entity Sentiment Database142) the Reviewable Entity315, such as an alphanumeric string, bit string, or a combination of data associated with the Reviewable Entity315such as name, location or owner of the Reviewable Entity315.

Entity Type300is a categorical variable used to define the type of the Reviewable Entity315in order to facilitate Entity Type300specific search and specify the domain to be used in Domain-Specific Sentiment Analysis. The Entity Type300can represent any type of Reviewable Entity315such as a place, service or consumer product. Example Entity Types300may include hotels, films, restaurants and cameras. In alternate embodiments, there may be more than one Event Type300associated with each Reviewable Entity315.

The Review ID304can be any unique identifier which uniquely identifies the Review313(e.g. a primary key in the Entity Sentiment Database142). The Review ID304may include any combination of information which uniquely identifies the Review313including the author of the Review313, the source from which the Review313was obtained and the date of the Review313.

The P(entity) value306represents the likelihood that the Review313is about the Entity315. For Reviews313including Textural Reviews310from unstructured reviews, the P(entity) value306can be a function of any information regarding the Review313such as the source of the Review313or the author of the Review313. The P(entity) value306can also be determined based on any metric generated from the analysis of the Textual Review310, such as the number of times the entity is mentioned in the Textual Review310or a title of the Textual Review310. According to the embodiment, the P(entity) value306may be a categorical (high, medium, low) or a numeric value. For Reviews313obtained from high quality or structured reviews, the P(entity) value306may be set to the corresponding numeric or categorical value which denotes the highest likelihood that the Review313pertains to the Entity315.

The P(sentiment) value308represents the likelihood that the Review313contains a sentiment about the Entity315. For Reviews313including Textual Reviews310from unstructured reviews, the P(sentiment) value306can be a function of any information regarding the entity such as the source of the Review313or the author of the Review313. The P(sentiment) value308can also be determined based on any metric generated from the analysis of the Textual Review310, such as the number of tokens representing adjectives in the Textual Review310. According to the embodiment, the P(sentiment) value306may be a categorical (e.g. high, medium, low) or a numeric value. For Reviews313including Textural Reviews310from high quality or structured reviews, the P(sentiment) value may be set to the corresponding numeric or categorical values which denotes the highest likelihood that the Review313pertains to the Reviewable Entity315. For example, a P(sentiment) value from an Review313obtained from a review website such as Yelp or TripAdvisor would be given a P(sentiment) value of 1 or 100%, indicating the highest likelihood that the Review313contained sentiment about the entity.

The Textual Review310includes the body of text that has been identified as a Review313of the Entity315. In one embodiment, the Textual Review310is tokenized to produce a set of tokens and each token is subject to part of speech (POS) tagging to associate parts of speech with the tokens. In some embodiments, the tokens comprising the Textural Review310are processed using a variety of natural language processing (NLP) techniques such as stemming, word sense disambiguation and compound recognition. Other applicable techniques will be apparent to those skilled in the art of natural language processing (NLP).

The Ranking Analysis Engine130processes each Textual Review310to create one or more Entity Review Texts318. Each Entity Review Text318comprises an Entity Text ID314, an Entity Text316and a Sentiment Score312. The Entity Text ID314is a unique identifier used to identify the Entity Review Text318. The Entity Text316is the portion of the Textual Review310which contains sentiment about the Reviewable Entity315. The Ranking Analysis Engine130identifies one or more Entity Texts316from the Textual Review310. The identification of Entity Review Texts318is discussed in detail below with respect to the Text Selection Module502inFIG. 5.

The Ranking Analysis Engine130generates Sentiment Scores312for each Entity Text316. Sentiment Scores312are used to represent the type of sentiment contained in the Entity Texts316and the magnitude or strength of the type of sentiment in the Entity Texts316. The type of sentiment represents any kind of characterization of a sentiment that can associated with heuristics used to score the sentiment according to the characterization such as: polarity of the sentiment, the type of attitude expressed in the sentiment, confidence in the sentiment, identity of the source/author, overall amount of sentiment-laden text identified, and relative importance of features about which sentiment is expressed.

Polarity of a sentiment defines whether it is a positive or negative sentiment. Heuristics used to score sentiments based on polarity are based on the sentiment containing synonyms of words that indicate polarity such as “good” or “bad”. In one embodiment, the generated Sentiment Scores312partition sentiments into two categories according to the polarity (i.e. positive or negative) of the sentiment.

Magnitude of sentiment is expressed as a value on a scale of 1 to 5 and represents the strength of the associated type of sentiment. In embodiments, where Sentiment Scores312are generated based on polarity, magnitude of sentiment and polarity of sentiment are combined to create a scale in which −5 represents the strongest negative sentiment; −1 represents the weakest negative sentiment; +1 represents the weakest positive sentiment and +5 represents the strongest positive sentiment.

In alternate embodiments, separate Sentiment Scores312are generated to represent type of sentiment and polarity of sentiment. Other representations of type of sentiment and magnitude of sentiment will be well known to those skilled in the art. For example, other representations may further partition sentiment into multiple types of sentiment or use different scales or categorical variables to represent magnitude.

FIG. 3Billustrates the storage of rating data from structured reviews of an entity in the Entity Rating Database144according to one embodiment. Each Rated Entity325is represented by a tuple in the Entity Rating Database144. The Rated Entity325tuple consists of an Entity ID302, an Entity Type300and one or more Ratings323. Each Rating232consists of a Review ID304, a Review Rating320and a Normalized Rating322.

The Review Rating320is the rating assigned in a structured review. The Review Rating320includes both the rating scale and the numeric value of the rating. The rating scale can be a set of ordered categorical variables (e.g. A+ through F) or a numeric scale (5 start system, scale of 1-10). Some rating scales include negative values. Ratings323with multiple different rating scales are normalized to create Normalized Ratings322in which the Ratings323have the same numeric scale. In one embodiment, simple linear normalization is performed by representing all the ratings on a specified scale. Other methods of normalization will be apparent to those skilled in the art in light of this disclosure.

FIG. 4illustrates the storage of the ranking data generated by the Ranking Analysis Engine130. Each Ranked Entity415is represented by a tuple in the Entity Ranking Database (X). Each tuple contains the Entity Type300, Entity ID302, Entity Ranking404, User Interaction Score406, User Interaction Score Weight408, Consensus Sentiment Score410, Sentiment Score Weight412, Consensus Normalized Rating414and Normalized Rating Weight416. In some embodiments, Ranked Entities415are organized by Entity Type200to facilitate search result retrieval for queries preformed for an Entity Type200.

The Ranked Entities415in the Entity Ranking Database144are displayed responsive to search queries which reference the Entity Type302. The Entity Rankings404are used as signals to rank the set of Ranked Entities415when displaying the Ranked Entities415as search results. For example, a user who enters “sushi” as a search query will receive an ordered list of Ranked Entities415of Entity Type415“sushi restaurant” ranked according to Entity Ranking404. According to the embodiment, the Entity Ranking404can be combined with other signals to rank the set of Ranked Entities415such as signals based on the number of times the Ranked Entity415is mentioned on an index of web pages or the geographic location of the Ranked Entities415relative to a geographic location of a user performing a search.

The User Interaction Score406is generated using user interaction metrics such as user click through and time spent at web pages associated with Ranked Entities415presented in search results. The Ranking Analysis Engine130monitors user interaction with results to generate user interaction metrics which are stored in the User Interaction Database148. This process is discussed in detail below with respect to step712inFIG. 7. The User Interaction Score Weight408is the weight assigned to the User Interaction Score406in calculating the Entity Ranking404.

The Consensus Sentiment Score410of a Ranked Entity415is a representative sentiment score which combines the values of all calculated Sentiment Scores312associated with an Entity315. Sentiment Scores312associated with a Ranked Entity315may be combined in any way to generate a Consensus Sentiment Score410. Consensus Sentiment Scores410can be generated by averaging the Sentiment Scores312associated with a Reviewable Entity315, selecting the median Sentiment Score312of the Sentiment Scores312associated with a Reviewable Entity315or selecting the Sentiment Score312which is most frequently associated with a Reviewable Entity315. The Sentiment Scores312of Reviews313with Textual Reviews310from unstructured reviews may be weighted using the P(entity) value306and the P(sentiment) value308. Other methods of generating a Consensus Sentiment Score410from a plurality of Sentiment Scores312associated with a Reviewable Entity315will be apparent to those skilled in the art. The Sentiment Score Weight412is the weight assigned to the Consensus Sentiment Score410in calculating the Entity Ranking404.

The Consensus Normalized Rating414is a representative rating which combines the values of all calculated Normalized Ratings322associated with a Ranked Entity325. Normalized Ratings322associated with a Ranked Entity325may be combined in any way to generate a Consensus Normalized Rating414. Consensus Normalized Ratings414can be generated by averaging the Normalized Ratings322associated with a Ranked Entity325, selecting the median Normalized Rating322associated with a Ranked Entity325or selecting the Normalized Rating322which is most frequently associated with a Ranked Entity325. Other methods of generating a Consensus Normalized Rating414from a plurality of Normalized Ratings322associated with a Ranked Entity325will be apparent to those skilled in the art. The Normalized Rating Weight416is the weight assigned to the Consensus Normalized Rating414for generating the Entity Ranking404.

FIG. 5is a high-level block diagram illustrating modules within the Ranking Analysis Engine130according to one embodiment.

A Text Selection Module502is used to identify one or more Reviewable Entity Texts318from the Textual Review310and store the Reviewable Entity Texts318in the Entity Sentiment Database142. In one embodiment, the Text Selection Module502runs as a batch program whenever new Reviews313are added to the Entity Sentiment Database142.

The Sentiment Score Module512generates Sentiment Scores312for each Entity Text316. In one embodiment, the Sentiment Score Module512is run as a batch program in association with the Text Selection Module502whenever new Reviews313are added to the Entity Sentiment Database142.

The User Interaction Module532functions to monitor user interactions with ranked search results for an Entity Type300. The User Interaction Module532further stores monitoring information in the User Interaction Database148. Monitoring user interaction with ranked search results is discussed in detail below with respect to step712inFIG. 7.

The Rank Learning Module542functions to learn weights for generating Entity Rankings404based on user-interaction metrics stored in the User Interaction Database148. In one embodiment, the Rank Learning Module542iteratively learns and stores a mixture model132to generate weights for generating Entity Rankings404.

FIG. 6is a flowchart illustrating a more detailed view of steps performed by an embodiment of the Ranking Analysis Engine130in generating Sentiment Scores312and initial Entity Rankings404based on the generated Sentiment Scores312. Other embodiments perform additional and/or different steps that the ones described in the figure. In addition, other embodiments perform the steps in different orders and/or perform multiple steps concurrently.

In an alternate embodiment, the set of tokens in each Entity Text316will be proportional to one or both of the P(entity)306value and the P(sentiment)308value. For instance, if the P(entity) value306or the P(sentiment) value308is low indicating a low likelihood that the Textual Review310is regarding the entity or contains sentiment about the entity, the set of tokens in the Entity Text316will be a smaller number of tokens than the set of tokens in the Entity Text316associated with a Textual Review310with a high P(entity) value306or P(sentiment) value308.

The Sentiment Score Module512generates616Sentiment Scores312representing the polarity and magnitude of sentiment in each of the Entity Review Texts318. The Sentiment Score Module512generates domain specific Sentiment Scores312based on the Entity Texts316and the Entity Types300which specify the domain of the entity. Suitable methods of generating domain-specific Sentiment Scores312are discussed below in reference toFIGS. 8-12.

The Rank Learning Module532generates618Entity Rankings404based on the Sentiment Scores312. The Rank Learning Module542combines the Sentiment Scores312associated with each Reviewable Entity315to generate618the Consensus Sentiment Score410used to generate618the Entity Ranking404. Entity ID302is used to create a correspondence between the Ranked Entities415, the Rated Entities425and the Reviewable Entities315. In one embodiment, the User Interaction Score Weight408and the Normalized Rating Score Weight416are set to zero, meaning that the Entity Ranking404is generated618based solely on the Consensus Sentiment Score410. This weighting is also used to initialize the Entity Ranking Database146in embodiments which monitor user interactions to iteratively learn the User Interaction Score Weights408, Normalized Rating Score Weights416and the Sentiment Score Weights412.

In an alternate embodiment, the Entity Ranking404is generated618based on both the Consensus Sentiment Score410and the Consensus Normalized Rating414with the corresponding Sentiment Score Weight412and Normalized Rating Weight416both set to values greater than zero. The values of the Sentiment Score Weight412and the Normalized Rating Weight can be user-specified. Alternately, these values may be learned based on information in the User Interaction Database148.

According to the embodiment, the Entity Ranking404may be based on any combination of the polarity and magnitude of the Consensus Sentiment Scores312associated with the Ranked Entities315. In one embodiment, the Ranked Entities315with the strongest positive Consensus Sentiment Scores410will have the highest Entity Rankings404and the Ranked Entities415with the strongest negative Consensus Sentiment Scores410will have the lowest Entity Rankings404. In another embodiment, the Ranked Entities315with the strongest negative Consensus Sentiment Scores410will have the highest Entity Rankings404and the Ranked Entities415with the strongest positive Consensus Sentiment Scores410will have the lowest Entity Rankings404. In another embodiment, the Entity Rankings404may be based solely on the magnitude of the Sentiment Scores312, wherein Ranked Entities415with the strongest positive and negative Consensus Sentiment Scores410are assigned the highest Entity Rankings404and the Ranked Entities415with the weakest positive and negative Consensus Sentiment Scores410are assigned the lowest Entity Rankings404.

FIG. 7is a flowchart illustrating a more detailed view of steps performed by an embodiment of the Ranking Analysis Engine130in learning weights for generating Entity Rankings404. Other embodiments perform additional and/or different steps that the ones described in the figure. In addition, other embodiments perform the steps in different orders and/or perform multiple steps concurrently. In some embodiments, the steps described in the figure are iteratively repeated710.

The User Interaction Module532monitors712user interactions with search results associated with the Ranked Entities415to generate and store user interaction metrics in the User Interaction Database148. Search results associated with Ranked Entities415are typically presented as web pages for the Ranked Entities415but can also consist of directory listings for the Ranked Entity415or other documents which contain information about the Ranked Entity415. The User Interaction Module532is adapted to communicate with a search engine program on a server through the Network114. The User Interaction Module532monitors user interaction to generate user click through rates for each search result associated with a Ranked Entity415. The user click through rate represents the number of times a search result associated with a Ranked Entity415was clicked by a user, divided by the number of times that result was presented to a user.

The User Interaction Module532also monitors712user interactions to generate metrics representing the time spent at search result associated with a Ranked Entity415. The User Interaction Module532monitors712and records the amount of time the user spends at a search result associated with a Ranked Entity415before returning to the web page displaying the ranked search results associated with the Ranked Entities415. In some embodiments, the User Interaction Module532monitors712other metrics of user interaction. Other suitable user-interaction metrics will be apparent to those skilled in the art of web search engines. The user interaction metrics are stored in the User Interaction Database148and may be combined in any way to generate the User Interaction Score408stored in the Entity Ranking Database146.

The Rank Learning Module542generates716the values of the Sentiment Score Weight412and Normalized Rating Weight416based on the User Interaction Score148. In one embodiment, the Sentiment Score Weight412and Normalized Rating Weight416are determined based on generating a correlation coefficient between both the Consensus Sentiment Score410and the Consensus Normalized Rating414and the User Interaction Score406. Each of the generated correlation coefficients is then divided by the sum of the two correlation coefficients to generate the Sentiment Score Weight412and the Normalized Rating Weight.

In other embodiments, the Sentiment Score Weight412and Normalized Rating Weight416are determined by generating a mixture model132to approximate the weight of influence of the Consensus Sentiment Score410and the Consensus Normalized Rating414on the User Interaction Score406. Suitable mixture models132to determine the weight of the Consensus Sentiment Score410and the Consensus Normalized Rating414on the User Interaction Score406include expectation maximization (EM) models, Markov Chain Monte Carlo models and Spectral models. In an alternate embodiment, the mixture model132may also incorporate the User Interaction Score406to determine an optimal User Interaction Score Weight408. Alternate embodiments may use predictive models such as classifiers to determine the values of the Sentiment Score Weight412and Normalized Rating Weight. Other methods of determining the Sentiment Score Weight412and Normalized Rating Weight416will be readily apparent to those skilled in the art.

The Rank Learning Module542generates716the Entity Rankings404based on the learned Sentiment Score Weights412and Normalized Rating Weights416. In one embodiment, the Rank Learning Module542generates the Entity Ranking404based on a linear combination of each score and its corresponding weight. That is, the Entity Ranking404is the sum of the Consensus Sentiment Score410multiplied by the Sentiment Score Weight412, the Consensus Normalized Rating414multiplied by the Normalized Rating Weight416, and the User Interaction Score406multiplied by the User Interaction Score Weight408. Alternate methods of combining the weights and scores to produce a single Entity Ranking404will be apparent to those skilled in the art.

FIG. 8is a high-level block diagram of a computing environment800for generating Sentiment Scores312according to one embodiment.FIG. 8illustrates an analysis engine810and a data repository812connected to a network814. AlthoughFIG. 8illustrates only a single analysis engine810, embodiments can have multiple engines. Likewise, there can be multiple data repositories on the network814. Only one of each entity is illustrated in order to simplify and clarify the present description. There can be other entities on the network814as well. In some embodiments, the analysis engine810and data repository812are combined into a single entity.

The analysis engine810supports domain-specific sentiment classification for documents stored in the repository812and/or other locations. In one embodiment, the analysis engine810uses the documents in the repository812to identify a domain-specific sentiment lexicon822of n-grams. In addition, the analysis engine810uses the n-grams in the domain-specific sentiment lexicon822as features in a model in order to build a highly-accurate domain-specific sentiment classifier816. The analysis engine810uses the classifier816to classify the sentiment of documents stored in the repository812and/or on the network814. In one embodiment, the analysis engine810is controlled by an administrator or other user who uses it to build the classifier and/or perform automated sentiment classification of documents.

The data repository812stores documents and other data utilized by the analysis engine810to build a domain-specific sentiment classifier816. In one embodiment, the data repository stores sets of documents organized into various corpora. The corpora include a domain-specific corpus818holding domain-specific documents and a domain-independent corpus820holding domain-independent (i.e., non-specific) documents. In one embodiment, the domain-specific corpus818contains enough documents to constitute a representative sample of how sentiment is expressed in the domain. Likewise, the domain-independent corpus820contains enough documents to constitute a representative sample of how sentiment is expressed generally, exclusive of any specific domain.

As used herein, the term “domain” refers to a particular sphere of activity, concern or function, such as restaurants, electronic devices, international business, and movies. The term “domain” does not necessarily refer to Internet domain names, although certain web sites at certain Internet domains might include documents related to a particular sphere of activity, concern or function.

In one embodiment, both corpora hold documents obtained via the network814. The documents include web pages and/or portions of web pages, the text of books, newspapers, and magazines, emails, newsgroup postings, and/or other electronic messages, etc. For example, the documents in the domain-specific corpus818can include documents related to restaurants, such as portions of web pages retrieved from web sites specializing in discussions about restaurants. Likewise, the domain-specific documents in the corpus818can include web pages retrieved from web sites that include reviews and/or discussion related to portable electronic devices, such as mobile telephones and music players. In contrast, the documents in the domain-independent corpus820can include documents associated with a variety of different domains, so that no single domain predominates. In addition, the documents in the domain-independent corpus820can be drawn from sources unrelated to any particular source, such as general interest magazines or other periodicals.

In some embodiments, the corpora hold documents obtained from sources other than the network. Moreover, in some embodiments the corpora are virtual in the sense that they are not stored at a single location. For example, the domain-specific corpus can be defined as the contents of one or more web sites devoted to restaurant reviews or other topics.

In one embodiment, the data repository812also includes the domain-specific sentiment lexicon822and a domain-independent sentiment lexicon826. The domain-specific sentiment lexicon822contains a set of n-grams (i.e., words and/or phrases) that express sentiment in a particular domain. The domain-independent sentiment lexicon826, in contrast, contains a set of n-grams that express sentiment in a general or non-specific domain. In one embodiment, each n-gram in the lexicons822,826has an associated score indicating the polarity (i.e., positive or negative) and magnitude of the sentiment it expresses.

In one embodiment, the domain-independent sentiment lexicon826is based on a lexical database, such as the WordNet electronic lexical database available from Princeton University of Princeton, N.J. The lexical database describes mappings between related words. That is, the database describes synonym, antonym, and other types of relationships among the words. In one embodiment, the administrator selects initial terms for the domain-independent sentiment lexicon826by reviewing the lexical database and manually selecting and scoring words expressing high sentiment. The administrator initially selects about 360 such words in one embodiment although the number of words can vary in other embodiments. This initial set of words is expanded through an automated process to include synonyms and antonyms referenced in the lexical database. The expanded set of words constitutes the domain-independent sentiment lexicon826.

An embodiment of the data repository812also includes a training corpus824. In one embodiment, the training corpus824includes domain-specific documents labeled with corresponding sentiment scores. In some embodiments the domain-specific documents are manually labeled with sentiment scores. For example, in one embodiment the documents in the training corpus824are drawn from popular product review web sites such as Amazon, CitySearch, and Cnet. These sites include textual product reviews that are manually labeled by the review submitters with corresponding numeric or alphabetic scores (e.g., 4 out of 5 stars or a grade of “B−”). Further, in some embodiments the domain-specific documents are automatically labeled with sentiment scores. For example, in one embodiment the documents in the training corpus824include high-sentiment documents from the domain specific corpus818that are labeled with sentiment scores through an automated process as described below.

The network814represents the communication pathways among the analysis engine810, the data repository812, and any other entities connected to the network. In one embodiment, the network814is the Internet. The network814can also utilize dedicated or private communications links that are not necessarily part of the Internet. In one embodiment, the network814uses standard communications technologies and/or protocols. Thus, the network814can include links using technologies such as Ethernet, 802.11, integrated services digital network (ISDN), digital subscriber line (DSL), asynchronous transfer mode (ATM), etc. Similarly, the networking protocols used on the network814can include multiprotocol label switching (MPLS), the transmission control protocol/Internet protocol (TCP/IP), the hypertext transport protocol (HTTP), the simple mail transfer protocol (SMTP), the file transfer protocol (FTP), the short message service (SMS) protocol, etc. The data exchanged over the network814can be represented using technologies and/or formats including the HTML, the extensible markup language (XML), the Extensible Hypertext markup Language (XHTML), the compact HTML (cHTML), etc. In addition, all or some of links can be encrypted using conventional encryption technologies such as the secure sockets layer (SSL), HTTP over SSL (HTTPS), and/or virtual private networks (VPNs). In other embodiments, the analysis engine810and data repository812use custom and/or dedicated data communications technologies instead of, or in addition to, the ones described above.

FIG. 9is a high-level block diagram illustrating modules within the analysis engine810according to one embodiment. Other embodiments have different and/or additional modules than the ones shown inFIG. 9. Moreover, other embodiments distribute the functionalities among the modules in a different manner.

A document scoring module910scores documents to determine the magnitude and polarity of the sentiment they express. In one embodiment, the document scoring module910includes one or more classifiers. These classifiers include a lexicon-based classifier912and the domain-specific classifier816created by the analysis engine810.

An embodiment of the lexicon-based classifier912uses the domain-independent sentiment lexicon826to calculate sentiment scores for documents in the domain-specific corpus818. The scoring performed by the lexicon-based classifier912essentially looks for n-grams from the domain-independent lexicon826that occur in the documents of the corpus818. For each n-gram that is found, the classifier912determines a score for that n-gram based on the techniques/factors described below. The sentiment score for the document is the sum of the scores of the n-grams occurring within it.

Embodiments of the lexicon-based classifier912use one or more of the following techniques/factors to determine the score for an n-gram found in a document:the n-gram score in the lexicon: An n-gram in the lexicon826has an associated score representing the polarity and magnitude of the sentiment it expresses. For example, “hate” and “dislike” both have negative polarities, and “hate” has a greater magnitude than “dislike;”part-of-speech tagging: The part of speech that an n-gram represents is classified and a score is assigned based on the classification. For example, the word “model” can be an adjective, noun or verb. When used as an adjective, “model” has a positive polarity (e.g., “he was a model student”). In contrast, when “model” is used as a noun or verb, the word is neutral with respect to sentiment.negation detection: An n-gram that normally connotes one type of sentiment can be used in a negative manner. For example, the phrase “This meal was not good” inverts the normally-positive sentiment connoted by “good.”location in document: A score is influenced by where the n-gram occurs in the document. In one embodiment, n-grams are scored higher if they occur near the beginning or end of a document because these portions are more likely to contain summaries that concisely describe the sentiment described by the remainder of the document.stemming: Reverse conjugation of a word in an n-gram is performed in order to identify its root word. A score is assigned to the word based on its root.

A document analysis module914analyzes documents scored by the document scoring module910. In one embodiment, the document analysis module914analyzes the documents scored by the lexicon-based classifier912and isolates the highest-scoring documents. An embodiment of the module914uses two scoring thresholds to partition the documents into a set of documents that express very negative sentiment and a set of documents that express very positive sentiment. Thus, documents that have a sentiment score lower than the negative sentiment threshold are placed in the “very negative sentiment” set while documents that have a sentiment score higher than the positive sentiment threshold are placed in the “very positive sentiment” set. Documents falling in the middle range are ignored for purposes of this analysis.

A lexicon generation module916creates the domain-specific lexicon822based on the sets of high-sentiment documents isolated by the document analysis module914. The lexicon generation module916identifies all n-grams up to a predetermined value of ‘n’ that occur in the documents in each set. “N” is five in one embodiment. Further, the lexicon generation module916identifies the most frequently occurring n-grams in each of the high-sentiment document sets (i.e., the most frequently occurring n-grams from the very negative sentiment document set and the most frequently occurring n-grams from the very positive sentiment document set).

A lexicon filtering module918filters the n-grams produced by the lexicon generation module916to produce a set of domain-specific sentiment-expressing n-grams. In one embodiment, the filtering module918removes extremely common n-grams (i.e., stop words) from the very negative and very positive sets. This filtering removes words and phrases like “the,” “or,” “he,” and “she” that are unlikely to express sentiment. The n-grams that remain after filtering constitute the domain-specific sentiment lexicon822.

A classifier building module920builds the domain-specific classifier816used by the document scoring module910. In one embodiment, the classifier building module920assigns a score to each n-gram in the domain-specific sentiment lexicon822that represents the polarity and magnitude of the sentiment it expresses. The domain-specific classifier816uses the n-gram scores in the domain-specific sentiment lexicon822, along with the techniques and factors described above with respect to the lexicon-based classifier912, to classify the sentiment expressed by domain-specific documents.

To assign the scores to the n-grams in the domain-specific sentiment lexicon822, the classifier building module920uses the n-grams as feature in a model, such as a maximum entropy model, and trains the model on documents. Other models used in some embodiments to assign sentiment scores to the n-grams are based on support vector machines, Naïve Bayes, perceptron, Winnow, and LASSO (Least Absolute Shrinkage and Selection Operator) instead of, or in addition to, maximum entropy.

In one embodiment, the classifier building module920trains the model on the labeled documents in the training corpus824. Recall that in one embodiment the documents in the training corpus824include documents with manually-labeled sentiment scores. In other embodiments, the documents in the training corpus824include the set of high-sentiment documents having the scores assigned by the document scoring module910and isolated by the document analysis module914via the automated process described above. The set of high-sentiment documents can be used, for example, if obtaining the manually-labeled documents is too expensive or difficult, or if there are not enough manually-labeled documents available. Some embodiments train on both manually- and automatically-labeled documents. The training assigns accurate sentiment scores to the n-grams in the domain-specific lexicon822.

A reporting module922reports results of operations performed by the analysis engine810. The reports can include generating a presentation on the display of a computer, storing data in a log file describing the operations performed, storing data resulting from the operations performed by the analysis engine in the repository812or elsewhere, and the like. For example, the reporting module922can save the output of the lexicon filtering module918in the repository812as the domain-specific sentiment lexicon822. Likewise, the reporting module922can store the sentiment scores for the n-grams in the filtered high-sentiment n-gram set generated by the classifier building module920, and sentiment scores for documents generated by the domain-specific classifier816, in the data repository812or elsewhere.

FIG. 10is a flowchart illustrating steps performed by the analysis engine810to build the domain-specific classifier816and apply the classifier to a set of domain-specific documents according to one embodiment. Other embodiments perform additional and/or different steps that the ones described in the figure. In addition, other embodiments perform the steps in different orders and/or perform multiple steps concurrently. Certain embodiments perform only some of the steps, such as only the steps directed to building the classifier816.

The analysis engine810creates1010a domain-specific lexicon822and saves it in the data repository812. The analysis engine810uses the training corpus824to associate1012sentiment scores with the n-grams in the lexicon822. The n-grams and associated scores are used by the domain-specific classifier816. In one embodiment, the analysis engine810uses the domain-specific classifier816to classify1014sentiment in domain-specific documents. The analysis engine810reports1016the results of the classifications. The report can be used to track the sentiment of an entity within the specific domain, to influence rankings of search results, and/or for other purposes.

FIG. 11is a flowchart illustrating a more detailed view of steps performed by an embodiment of the analysis engine810in creating the domain-specific sentiment lexicon as illustrated in step1010ofFIG. 10. Other embodiments perform additional and/or different steps that the ones described in the figure. In addition, other embodiments perform the steps in different orders and/or perform multiple steps concurrently.

The analysis engine810establishes1110a domain-independent sentiment lexicon826. As described above, in one embodiment this lexicon826is created by manually selecting words having high sentiment from a lexical database and identifying antonyms and synonyms of the selected words. The selected words, antonyms, and synonyms are included in the domain-independent sentiment lexicon826. Other embodiments use a pre-defined domain-independent sentiment lexicon or use other techniques to create the lexicon.

The analysis engine810uses the domain-independent sentiment lexicon826to score1112sentiment of documents in a domain-specific corpus818. Then, the analysis engine810isolates the high-sentiment documents and partitions1114those documents into a set of very negative sentiment documents and a set of very positive sentiment documents. The analysis engine810extracts n-grams from the negative- and positive-sentiment documents. These n-grams are filtered1116to remove extremely common words and phrases. The remaining n-grams are saved1118as a domain-specific sentiment lexicon822.

FIG. 12is a flowchart illustrating a more detailed view of steps performed by an embodiment of the analysis engine810in assigning sentiment scores to n-grams in the domain-specific sentiment lexicon822as illustrated in step1012ofFIG. 10. Other embodiments perform additional and/or different steps that the ones described in the figure. In addition, other embodiments perform the steps in different orders and/or perform multiple steps concurrently.

The analysis engine810establishes1210a training corpus824of labeled documents. As described above, in some embodiments the training corpus824is established by collecting domain-specific documents that are manually labeled with sentiment scores while in other embodiments the training corpus824is established using the automatically-labeled set of high-sentiment documents isolated by the document analysis module914. The analysis engine810builds1212a model, such as a maximum entropy model, having the n-grams of the domain-specific sentiment lexicon822as features. The model is trained1214on the labeled documents in the training corpus824to determine sentiment scores for the n-grams. These scores are saved1216in the domain-specific sentiment lexicon822.

Those of skill in the art will recognize that the techniques described herein can be used to build multiple sentiment classifiers for documents in different domains. To this end, some embodiments have multiple domain-specific lexicons, domain-specific corpora, and training corpora. This description refers to a single domain-specific classifier816and domain for purposes of clarity.