System and method for classifying text sentiment classes based on past examples

[0001] This application arises from provisional application No. 61/843,709 filed on Jul. 8, 2013 and claims the benefit thereof.

[0002] The present disclosure relates to natural language processing and classification of textual documents and more specifically to assigning a score that reflects the polarity and magnitude of the sentiment expressed

[0003] Good automatic classification is challenging: it comes at a high cost (of speed and resources) and often leads to poor results. Human classification by an expert produces much better results, but is often too expensive and slow.

[0004] In some applications many of the passages exhibit similarities. For example in a collection of short user posts (such as Tweets or Facebook comments), an original post may lead to very many repetitions with only minor modifications. In this case it is reasonable to use an expensive method of classification (a human, or a high-accuracy automatic process) to classify one of the posts and use a fast automatic method to find all similar posts and classify them automatically, obtaining a compromise in accuracy, speed and cost.

[0005] A passage of text may be a few words, a sentence, a paragraph or an entire document. Passages of text are common in the Internet, for example as Tweets, Facebook posts, blog posts or blog comments, etc. There are many reasons to classify passages of text. For example, one may be interested in classifying passages by their topic, as spam or not spam, or by semantic properties of the sentence such as its sentiment or polarity (whether its tone is positive or negative, for example).

[0006] Sentiment classification is a method helpful when tracking the overall perception of brands, companies or products. Sentiment classification can be used on the Internet to obtain a measure of the reception of a brand or product on the Internet, for example. Business analytics applications could use sentiment classification over a plethora of textual sources, such as reviews, blogs posts, and information present in Social media online sites such as Facebook or Twitter, in order to quantify the perception of brands.

[0007] Sentiment classification pertains to assigning a class between either a discrete set of values (positive, neutral or negative) or a real valued normalized score, where the higher bound represents positive sentiment, and the lower bound negative sentiment. Typically, sentiment classifiers make use of the words in a document to classify a piece of text, in which some words are assumed to convey a particular sentiment value. In order to determine which words are indicative of a particular sentiment class or value, some pieces of text are usually classified by a human, which assigns a label to the text. Further, the label of the piece of text are propagated to the words in the text, and these labels are assigned a real valued weight, derived from the information conveyed by the labels of the whole collection of passages or documents. These weights are further computed using methods derived from statistical learning theory (machine learning).

[0008] However, the manual process of assigning the labels to the pieces of text is time consuming and expensive, as it is being dependent on human intervention.

[0009] A method to perform automatic sentiment class so is described here, whereby the invention makes use of a nearest-neighbor classifier to locate all the similar passages to a passage of known class.

[0010] Nearest neighbor search (NNS), also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q∈M, find the closest point in S to q. In many cases, M is taken to be d-dimensional Euclidean space and distance is measured by Euclidean distance or Manhattan distance, but other spaces and distances can be used. For example in the case of points representing text passages one may use a string metric such as Hamming distance or Levenshtein distance.

[0011] There exist a number of methods to perform NNS on a given collection of points and a given metric. Common methods include: linear search, space partitioning, locality sensitive hashing, or methods based on compression or clustering of the points.

[0012] Opinion mining and sentiment analysis. Bo Pang and Lillian Lee. Foundations and Trends® in Information Retrieval 2(1-2), pp. 1-135, Now Publishers Inc, 2008, presents and overview of recent sentiment classification methods, with an emphasis on classification features based on combinations of words in the document.

[0013] U.S. Publication Number US 2009/0125371 A1, filing date Aug. 23, 2007 (Tyler J. Neylon et al.) describes a domain-specific sentiment classifier that can be used to score the polarity and magnitude of sentiment expressed by domain-specific documents.

[0014] U.S. Publication Number US 2010/0150393 A1, filing date Dec. 16, 2008 (Xiaochuan Ni et al.) disclose a system to classify textual data according to their sentiment using domain data.

[0015] U.S. Publication Number US 2008/0249764 A1, filing date Dec. 5, 2007 (Shen Huan et al.) describes a system that classifies text according to their sentiment, using complex features such as expressions, negation patterns, sentiment specific sections of a product review and so on.

[0016] U.S. Pat. No. 7,788,087, issue date Aug. 31, 2010 (Simon H. Corston-Oliver et al.) describes a system for identifying, extracting, clustering and analyzing sentiment-bearing text.

[0017] U.S. Publication Number US 2011/0137906 A1 describes a method for analyzing sentiment, comprising of collecting an object from a external content repository; the collected objects forming a content database and extracting a snippet related to the subject from the content database.

[0018] A passage sentiment classifier that can be used to assign a score that indicates the polarity and magnitude of sentiment expressed by a piece of text using information about similar passages. A passage of text may be a few words, a sentence, a paragraph or an entire document. The invention described classifies automatically passages by first looking up the most similarly classified passage in a storage system, which contains passages that have been classified manually by a human.

[0022] FIG. 1 is a block diagram of an embodiment wherein a passage in the passage index 104 is selected by the passage selection module component 106 (this selected passage is from now on referred to as the S passage), and the S passage is assigned a label by a human analyst or a processing system (this label is referred to as C from now on). In this embodiment a similarity classifier 110 retrieves a set of similar passages to the S passage from the passage index (these similar passages are from now on referred as the T passage set) and classifies them by assigning to each one of them the class C. In this embodiment, the correction process module 114 allows a human analyst or a processing system to correct the class assignments, before they are stored in the passage index.

[0023] FIG. 3 is a block diagram of an embodiment wherein a passage selection module 106 receives in step 202 a new passage labeling. A textual passage is a string of text such as a paragraph, a document section, a blog post, a comment in a glob post, a micro-blog post such as a Tweet or a Facebook post. A passage labeling is obtained when a human analyst or an automatic process assigns a label L to a passage S. In step 204 the processor accesses the passage index to retrieve in step 206 the set of passages T constituted by pages that are similar to the passage S. In step 208 it assigns to each of the passages in T the class L. Finally in step 210 the new passage classifications are stored.

[0024] Similar passages can be determined in step 206 by comparing the passage S to each passage in the passage index 104 and computing a similarity score between each passage in the index and the passage S. In one embodiment, similarity scores are computed by preprocessing the passage S and preprocessing each passage in T. Preprocessing a passage can be done by applying a sequence of text transformation rules. Text transformation rules can remove a predetermined set of string matching patterns from the passages. For example a text transformation rule that removes the prefix “FW:” from the beginning of a passage would make all the titles of replied emails equal to the title of the original mail. As another example, removing URLs from text could be achieved with another text transformation rule.

[0025] In one embodiment similarity between preprocessed passages is computed by a string distance metrics. For example, the similarity between two passages can be computed using the Levenshtein distance, the Hamming distance, and other string distances. In another embodiment the similarity score between two passages is computed as the Euclidean distance of the feature vector of each passage. The features are derived from the passages using the tokens in the preprocessed passages. In another embodiment the features are derived form the passages using sequences of tokens in the passages. The sequences of tokens in the passages are all the fixed length subsequence of tokens in the passages, often referred to as n-grams. In this embodiment features used to represent passages as feature vectors. Feature vectors are weighted by the frequency of the feature in the passage. In another embodiment the feature vector is weighted by the TF-IDF score of the corresponding feature. The TF-IDF score is computed as the frequency of the feature multiplied by the log of the inverse document frequency of the feature, where the document frequency of the feature is defined as the number of passages containing the feature in a collection of passages.

[0026] Application programs using the methods disclosed herein may be loaded and executed on a variety of computer systems comprising a variety of hardware components. An exemplary computer system and exemplary operating environment for practicing the methods disclosed herein is described below.

[0027] FIG. 2 illustrates an example of a suitable computing system environment 100 on which the methods disclosed herein may be implemented. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the methods disclosed herein. Neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100.

[0028] The methods disclosed herein are operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with the methods disclosed herein include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

[0029] The methods and processes disclosed herein may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The methods and processes disclosed herein may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

[0030] With reference to FIG. 2, an exemplary system for implementing the methods and processes disclosed herein includes a general purpose computing device in the form of a computer 110. Components of computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including, but not limited to, system memory 130 to processing unit 120. System bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

[0031] Computer 110 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium, which can be used to store the desired information and which can be accessed by computer 110. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of the any of the above should also be included within the scope of computer readable media as used herein.

[0032] System memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS) containing the basic routines that help to transfer information between elements within computer 110, such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120. By way of example, and not limitation, FIG. 2 illustrates operating system 134, application programs 135, other program modules 136, and program data 137.

[0033] Computer 110 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, FIG. 2 illustrates a hard disk drive 140 that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive 151 that reads from or writes to a removable, nonvolatile magnetic disk 152, and an optical disk drive 155 that reads from or writes to a removable, nonvolatile optical disk 156 such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. Hard disk drive 141 is typically connected to system bus 121 through a non-removable memory interface such as interface 140, and magnetic disk drive 151 and optical disk drive 155 are typically connected to system bus 121 by a removable memory interface, such as interface 150.

[0034] The drives and their associated computer storage media discussed above and illustrated in FIG. 2 provide storage of computer readable instructions, data structures, program modules and other data for computer 110. In FIG. 2, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146, and program data 147. Note that these components can either be the same as or different from operating system 134, application programs 135, other program modules 136, and program data 137. Operating system 144, application programs 145, other program modules 146, and program data 147 are given different numbers here to illustrate that, at a minimum, they are different copies.

[0035] A user may enter commands and information into computer 110 through input devices such as a keyboard 162 and pointing device 161, commonly referred to as a mouse, trackball or touch pad. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to processing unit 120 through a user input interface 160 that is coupled to system bus 121, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor 191 or other type of display device is also connected to system bus 121 via an interface, such as a video interface 190. In addition to monitor 191, computer 110 may also include other peripheral output devices such as speakers 197 and printer 196, which may be connected through an output peripheral interface 195.

[0036] Computer 110 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. Remote computer 180 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to computer 110, although only a memory storage device 181 has been illustrated in FIG. 2. The logical connections depicted in FIG. 2 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

[0037] When used in a LAN networking environment, computer 110 is connected to LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, computer 110 typically includes a modem 172 or other means for establishing communications over WAN 173, such as the Internet. Modem 172, which may be internal or external, may be connected to system bus 121 via user input interface 160, or other appropriate mechanism. In a networked environment, program modules depicted relative to computer 110, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 2 illustrates remote application programs 185 as residing on memory device 181. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

[0038] Methods and processes disclosed herein may be implemented using one or more application programs including, but not limited to, a server system software application (e.g., WINDOWS SERVER SYSTEM™ software application), a search ranking application, and an application for generating, maintaining and storing usage data of documents within a network space (e.g., WINDOWS® SHAREPOINT® Services application), any one of which could be one of numerous application programs designated as application programs 135, application programs 145 and remote application programs 185 in exemplary system 100.

[0039] As mentioned above, those skilled in the art will appreciate that the disclosed methods of assigning a score that reflects the polarity and magnitude of the sentiment expressed may be implemented in other computer system configurations, including hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, networked personal computers, minicomputers, mainframe computers, and the like. The disclosed methods of assigning a score that reflects the polarity and magnitude of the sentiment expressed may also be practiced in distributed computing environments, where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.