Unsupervised text segmentation by topic

A processor may generate a plurality of vectors from an original text by processing the original text with at least one unsupervised learning algorithm. Each of the plurality of vectors may correspond to a separate portion of a plurality of portions of the original text. The processor may determine respective segments to which respective vectors belong. The processor may minimize a distance between at least one vector belonging to the segment and a known vector from among one or more known vectors and applying a label of the known vector to the segment.

BACKGROUND OF THE DISCLOSURE

Text segmentation is the process of dividing written text into meaningful units, such as words, sentences, or topics. This is a fundamental task in natural language processing (NLP) that can improve text understanding, summarization, retrieval, and more. Text segmentation often relies on supervised processing methods where a very large corpus of text is manually analyzed and labeled by human readers and then used to train a machine learning (ML) NLP system. The training can be costly and error prone, and it can be difficult to obtain a large enough corpus to train a useful model.

DETAILED DESCRIPTION OF SEVERAL EMBODIMENTS

Embodiments described herein may use an unsupervised ML approach to identify topics within text and/or to segment portions of text into constituent topic subsets. Embodiments may perform such processing based on the intuition that, with high probability, it may be expected that sequential sentences or other portions of a text should “agree” with one another and may therefore belong to the same segment. Given two distributions, the probability that consecutive portions may be assigned to the same segment is given by their inner product (which is the probability that they are both assigned to the first segment added to the probability they are both assigned to the second segment, and so on). For example, consider a transcript of a call made to a call center (e.g., a help hotline for a software product). The transcript may include a record of a conversation between two parties, a caller and a call center employee. The conversation may include several segments, such as an introduction, a caller authentication, a problem description, a problem understanding, a solution, a resolution, an ending, other segments, and/or a subset of these segments. In the call center example, segmentation of the transcript may allow the segments of the transcript to be analyzed separately, for example to assess employee performance and/or to assess customer satisfaction. Because the disclosed embodiments use unsupervised ML, the segmentation and subsequent analysis may be performed without a large body of past conversations that have been segmented (e.g., by an expert human reader).

FIG. 1shows an unsupervised text segmentation system100according to an embodiment of the present disclosure. System100may receive text101and identify one or more segments102of the received text101using an unsupervised ML approach. Some embodiments of system100may function as follows.

System100may generate a plurality of vectors by processing original text with at least one unsupervised learning algorithm, where each of the plurality of vectors corresponds to a separate portion of the original text. As noted above, a conversation spans several segments (e.g., introduction, authentication, problem description, problem understanding, solution, resolution, ending). Because there is no training data corpus used with unsupervised analysis, a label that assigns the correct segment to any two consecutive utterances may not exist. However, if on average a segment changes every X utterances (for instance, after 10 utterances), then with high probability (e.g., 1−1/X, which is much higher than 50%) two consecutive utterances belong to the same segment. Therefore, system100may feed the utterances one by one to deep learning processing110(which may operate one or more unsupervised deep learning models) and receive a distribution of the topics (e.g., the utterance “Thank you for calling Intuit, how may I help you?” may receive a score of 95% likely to belong to the introduction segment, and 5% to belong to the solution segment). In the absence of label data, it may not be immediately certain whether this distribution is correct. However, with high probability, it may be expected that the next utterance should “agree” with this distribution and to belong to the same segment. Given two distributions, the probability that they assign both utterances to the same segment is given by their inner product, which may yield the chances these two predictions agree with each other. Given a conversation with N utterances, the algorithm may produce N distributions.

System100may perform inner product processing120on the output of deep learning processing110. In so doing, for each of the plurality of vectors, system100may determine a segment to which the vector belongs by performing inner product processing on the vector and at least one additional vector of the plurality of vectors. For example, some embodiments may maximize the inner product between the N−1 consecutive utterances. This objective alone will converge to a naive solution where all utterances belong to the same segment (which will maximize the inner product). Therefore, system100may also apply negative sampling. For each utterance, system100may sample random utterances (that have to be distant enough from the base utterance). The probability of having an utterance and a random one in the same segment may be low. Therefore, the negative sampling may minimize the sum of the inner products between the base utterance and each of the random ones. Computing the log of the inner products (rather than just the inner products) may further improve results.

The previously-described processing may divide the conversation into meaningful segments, but not necessarily to interpretable ones. That is, elements contained in a given segment may be highly related to one another, but it may not be readily apparent how each segment should be labeled, or what the “label” of the segment should be. As a result, the generated segment list may not align with a desired segment list (e.g., introduction, authentication, etc.). Therefore, system100may perform pattern alignment processing130to find one or more patterns per each desired segment (e.g., the string “how can I help you” may be deterministically assigned to the introduction segment). This may produce the alignment between the generated segments and the desired ones. For example, system100may label each of the plurality of segments by minimizing a distance between at least one vector belonging to the segment and a known vector having a label. Then, system100may apply the label of the minimum-distance known vector to the segment.

Once segments are identified and labeled, the output may be labeled segments102of the original text101. This may include new data created automatically by system100as a result of the processing described above. This new data may be stored in memory, displayed to a user, and/or fed to additional automated processes and/or systems. For example, system100may generate a new text comprising at least one of the portions of the original text, the at least one of the portions of the original text being included in the new text on the basis of the label of the segment to which the at least one vector, corresponding to the at least one of the portions of the original text, belongs.

FIG. 2shows deep learning processing110in greater detail according to an embodiment of the present disclosure. As described above, system100may perform deep learning processing110to generate a distribution of topics in the text. In some embodiments, deep learning processing110may include some or all of the processing shown inFIG. 2. Deep learning processing110is described herein as being applied to a plurality of portions, and in various embodiments system100may perform deep learning processing110sequentially or in parallel on each of the plurality of portions.

At202, system100may divide the text into a plurality of portions. For example, in a text that contains multiple sentences, each sentence may be a separate portion which system100may identify based on punctuation. In a text that contains a transcript of a conversation, each utterance by a party to the conversation may be a separate portion which system100may identify based on speaker identification, punctuation, and/or document formatting. In a text that contains a list, each list item may be a separate portion which system100may identify based on bullet points, numbers, lines, etc.

At204, system100may generate vectors for each of the plurality of portions. For example, unsupervised learning processing applied to each of the plurality of portions may include applying word embedding (e.g., Word2Vec or similar algorithm(s))) to obtain a separate respective vector for each portion. In some embodiments this may include, for example, processing each word using the word embedding algorithm and forming a vector from the combination of vectors of each individual word in a given sentence (i.e., portion). In other embodiments, sentences (or other portions) of the text may be processed by the word embedding algorithm to obtain total vectors for the sentences directly.

At206, system100may find a probabilistic distribution for each of the plurality of vectors. For example, system100may process each vector separately with at least one unsupervised learning algorithm to determine a probabilistic distribution of the vector relative to a plurality of vectors. Each vector may be passed to deep learning processing, for example by encoding the output of the word embedding using convolutional neural networks (CNN), recurrent neural networks (RNN), long short term memory (LSTM), or other unsupervised algorithm(s), thereby obtaining a respective probabilistic distribution for each vector. The probabilistic distribution may give a probability that a portion represented by the vector corresponds to a given segment. For example, a first sentence may belong to a first segment with 80% probability, to a second segment with 20% probability, to a third segment with 0% probability, and to a fourth segment with 0% probability. A second sentence may belong to the first segment with 70% probability, to the second segment with 10% probability, to the third segment with 20% probability, and to the fourth segment with 0% probability. In various embodiments, any number of portions may be analyzed against any number of possible segments, and may have any distribution of probabilities as long as the probabilities for a given portion add up to 100% (or1).

At208, system100may concatenate metadata to each vector. The metadata may describe the portion of the text that corresponds to the vector (e.g., for a given vector, the portion of the text that was input into Word2Vec to generate that vector). For example, in the case of a conversation transcript, the metadata may include speaker ID (e.g., caller or call recipient), sentence ID (e.g., first sentence in conversation, second sentence in conversation, etc.), and/or other metadata. At this point, system100may have a plurality of enriched vectors that have been processed by deep learning (giving probability distributions) and metadata (giving vector descriptive information).

At210, system100may pass each vector through one or more fully connected layers (e.g., of a CNN). There may be the same number of layers (K) as number of vectors in the entire corpus of vectors produced by processing at204, for example. After passing through the fully connected layers, each resulting vector may be a vector of size K. Accordingly, processing at210may normalize the vectors such that each vector may be normalized to have a same length as all other vectors (e.g., length K).

At212, system100may get probability distributions for the normalized vectors. For example, system100may pass vectors of size K through the softmax function to produce K probabilities in a probability distribution. Each of the K values may get a nonnegative probability, and the probabilities all may sum up to 1. So, for example, if there are 100 sentences, there are 100 probability distributions.

At this stage, system100may have generated probability distributions relating the vectors (and, therefore, the original portions) to one another, but further processing such as that described below with respect toFIG. 3may improve the accuracy of the probabilities.

FIG. 3shows inner product processing120according to an embodiment of the present disclosure. Inner product processing120may be performed to improve the accuracy of the probability distributions generated by deep learning processing110. Inner product processing120is described herein as being applied to a plurality of vectors, and in various embodiments system100may perform inner product processing120sequentially or in parallel on each of the plurality of vectors.

At302, system100may maximize the inner product between the K−1 consecutive vector pairs. For each pair of vectors, system100may maximize an inner product between them. However, as noted above, maximization alone may converge to a naive solution where all consecutive vectors belong to the same segment (which will maximize the inner product).

At304, to address the problem of convergence, system100may minimize inner products of random pairs of vectors. For each vector, system100may sample random vectors (that may be selected to be more distant from some threshold distance away from the base vector). The probability of having randomly selected pairs of vectors in the same segment may be low. Therefore, the negative sampling may minimize the sum of the inner products between the base vector and the random vector for each base vector. Computing the log of the inner products (rather than just the inner products) may further increase accuracy in some embodiments.

At this stage, system100may have generated accurate probability distributions relating the vectors (and, therefore, the original portions) to one another, but there may be no information explaining what the distributions mean. For example, it may be possible to state that a first sentence has a 90% chance of belonging to segment 1 and a 10% chance of belonging to segment 2, but there may be no information about which portions of the text segments1and2are (e.g., it may be unclear whether a given segment is the intro, problem statement, problem solution, etc.). Accordingly, system100may perform further processing, such as that described below with respect toFIG. 4.

FIG. 4shows pattern alignment processing130according to an embodiment of the present disclosure. By performing pattern alignment processing130, system100may find one or more patterns per each desired segment (e.g., vectors may be deterministically assigned to labeled segments). Pattern alignment processing130is described herein as being applied to a plurality of vectors, and in various embodiments system100may perform pattern alignment processing130sequentially or in parallel on each of the plurality of vectors.

At402, system100may select representative vectors from each segment. For example, if there are X segments within the probability distributions generated as described above, a representative vector may be selected from each of the X segments. System100may also obtain example known vectors. For example, a model text may be divided into a plurality of known segments (e.g., X known segments). In a specific example, the model text may be a conversation divided into segments such as an introduction, a caller authentication, a problem description, a problem understanding, a solution, a resolution, an ending, other segments, and/or a subset of these segments. A sentence or portion of each such segment may be vectorized similarly to the processing described above (e.g., according to the processing ofFIG. 2) or by some other process, but the resulting vector may be definitively associated with a segment from the model text (e.g., introduction). In some embodiments, processing at402may including selecting an appropriate model text based on a type of text being processed (e.g., selecting a set of known conversation vectors for a conversation under analysis, a set of known contract vectors for a contract under analysis, etc.).

At404, system100may minimize distances between representative vectors and known vectors. For example, system100may apply a distance minimization algorithm to a representative vector and each known vector to find which of the known vectors has a shortest distance to the representative vector. Minimization algorithms may include Kullback-Leibler divergence (KL divergence), Jensen-Shannon divergence, Wasserstein distance, etc.

At406, system100may label representative vectors according to the closest known vectors. For example, a first representative vector (from a first segment) may be matched with a particular known segment (e.g., problem description) by the processing of404. Accordingly, system100may label the first representative vector as belonging to the particular known segment (e.g., the first representative vector from the conversation transcript text under analysis represents an utterance that was part of a problem description portion of a conversation).

At408, based on the labeling of406, system100may label all other vectors in respective same segments of labeled representative vectors. For example, each vector in a first segment may receive the label for the representative vector from the first segment, each vector in a second segment may receive the label for the representative vector from the second segment, and so on. Continuing the example of406, each vector in the first segment of the conversation transcript text under analysis may be labeled as representing an utterance that was part of the problem description portion of the conversation. The labeled vectors may be used to label the segments which they represent. Accordingly, after performing pattern alignment processing130of all representative vectors, system100may output labeled segments102, where each segment of an input text101is labeled with the label of the portion to which it belongs.

The aforementioned system100and the processing it performs may be applied to any type of text. For example, texts may be analyzed and/or displayed in an enhanced fashion after being processed by system100.FIG. 5shows a text analysis computing environment500that may leverage system100according to an embodiment of the present disclosure. The computing environment may include one or more devices in communication with one another through a network502. Network502may include any public and/or private network, such as the Internet. The devices may include unsupervised text segmentation system100, a text source system504, an evaluation system506, and/or a display system508. These systems are illustrated as separate components connected by network502in the example ofFIG. 5, but in some embodiments, each system (or some of the systems) may collectively be elements of a single device and/or may be coupled to one another by direct connections rather than by network502. Likewise, in some embodiments, each system (or some of the systems) may be distributed among multiple devices. An example computing device that may provide some or all elements ofFIG. 5is described below with respect toFIG. 6.

In the example ofFIG. 5, text that is analyzed by unsupervised text segmentation system100may be supplied by text source system504. For example, text source system504may be an aggregator of articles, or a medical database, or an individual user's computer (e.g., with which the user writes emails or word processor documents or the like), or any other device that generates and/or stores text. In a specific example for ease of explanation, text source system504may be a device that records and/or collects transcripts of phone conversations between callers and call center employees.

Text source system504may provide text (e.g., transcripts)101to unsupervised text segmentation system100(e.g., through network502). Unsupervised text segmentation system100may process the text as described above (e.g., with respect toFIGS. 2-4). The output of such processing may include a plurality of labeled segments102of the input text101.

Labeled segments102may be used for any purpose. The environment500ofFIG. 5provides two example systems which may use the labeled segments. For example, evaluation system506may take the labeled segments102(in some cases, in addition to the input text101) as input and perform further processing that benefits from the labeling. For example, when the text is a transcript of a conversation between a caller and an employee, evaluation system506may be used to perform quality control on the call center experience. The labels may allow the evaluation system506to analyze portions of the conversation independently using different metrics (e.g., friendliness may be important for an introduction, while effectiveness may be important for a problem solution) and/or to characterize the conversation (e.g., break down amounts of time spent in each portion of the conversation, generate a summary of the discussion, etc.). Such evaluation may be an automatic process in some examples.

In another example, display system508may take the labeled segments102(in some cases, in addition to the input text101) as input and perform further processing that benefits from the labeling. For example, display system508, evaluation system506, and/or text source system504may be elements of a same computing device (and/or may be used by a same user), and may allow the user to evaluate her own writing. The user may be able to input a text sample and receive a breakdown of how it is constructed relative to one of a variety of templates (e.g., where the templates are sources of known vectors as described above) through a user interface presented by display system508.

FIG. 6shows a computing device600according to an embodiment of the present disclosure. For example, computing device600may function as unsupervised text segmentation system100and/or as text source system504, evaluation system506, display system508, any combinations thereof, or any portions thereof. Computing device600may be implemented on any electronic device that runs software applications derived from compiled instructions, including without limitation personal computers, servers, smart phones, media players, electronic tablets, game consoles, email devices, etc. In some implementations, computing device600may include one or more processors602, one or more input devices604, one or more display devices606, one or more network interfaces608, and one or more computer-readable mediums610. Each of these components may be coupled by bus612, and in some embodiments, these components may be distributed among multiple physical locations and coupled by a network.

Display device606may be any known display technology, including but not limited to display devices using Liquid Crystal Display (LCD) or Light Emitting Diode (LED) technology. Processor(s)602may use any known processor technology, including but not limited to graphics processors and multi-core processors. Input device604may be any known input device technology, including but not limited to a keyboard (including a virtual keyboard), mouse, track ball, and touch-sensitive pad or display. Bus612may be any known internal or external bus technology, including but not limited to ISA, EISA, PCI, PCI Express, NuBus, USB, Serial ATA or FireWire. In some embodiments, some or all devices shown as coupled by bus612may not be coupled to one another by a physical bus, but by a network connection, for example. Computer-readable medium610may be any medium that participates in providing instructions to processor(s)602for execution, including without limitation, non-volatile storage media (e.g., optical disks, magnetic disks, flash drives, etc.), or volatile media (e.g., SDRAM, ROM, etc.).

Computer-readable medium610may include various instructions614for implementing an operating system (e.g., Mac OS®, Windows®, Linux). The operating system may be multi-user, multiprocessing, multitasking, multithreading, real-time, and the like. The operating system may perform basic tasks, including but not limited to: recognizing input from input device604; sending output to display device606; keeping track of files and directories on computer-readable medium610; controlling peripheral devices (e.g., disk drives, printers, etc.) which can be controlled directly or through an I/O controller; and managing traffic on bus612. Network communications instructions616may establish and maintain network connections (e.g., software for implementing communication protocols, such as TCP/IP, HTTP, Ethernet, telephony, etc.).

Unsupervised text segmentation instructions618may include instructions that enable computing device600to perform unsupervised text segmentation system100functionality as described herein. Application(s)620may be an application that uses or implements the processes described herein and/or other processes, for example applications used to provide the functionality of text source system504, evaluation system506, and/or display system508. The processes may also be implemented in operating system614.

To provide for interaction with a user, the features may be implemented on a computer having a display device such as an LED or LCD monitor for displaying information to the user and a keyboard and a pointing device such as a mouse or a trackball by which the user can provide input to the computer.