Abstract:
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.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application arises from provisional application No. 61/843,709 filed on Jul. 8, 2013 and claims the benefit thereof. 
     
    
     BACKGROUND OF THE INVENTION 
       [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. 
       BRIEF SUMMARY OF THE INVENTION 
       [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. 
     
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
         [0019]      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. 
           [0020]      FIG. 2  is a block diagram of some of the primary components of an exemplary operating environment for implementation of the methods and processes disclosed herein; 
           [0021]      FIG. 3  is a block diagram of an embodiment wherein a passage selection module receives in step  102  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  104  the processor accesses the passage index to retrieve in step  106  the set of passages T constituted by pages that are similar to the passage S. In step  108  it assigns to each of the passages in T the class L. Finally in step  110  the new passage classifications are stored. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [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. 
       Exemplary Operating Environment 
       [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.