{'fraction_non_alphanumeric': 0.02967278023028262, 'fraction_numerical': 0.01074045419378328, 'mean_word_length': 4.959858963927312, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Matching sets of parse trees for answering multi-sentence questions

The problem of answering multi-sentence questions is addressed in a number of products and services-related domains. A candidate set of answers, obtained by a keyword search, is re-ranked by matching the set of parse trees of an answer with that of the question. To do that, a graph representation and learning technique for parse structures for paragraphs of text have been developed. Parse Thicket (PT) as a set of syntactic parse trees augmented by a number of arcs for inter-sentence word-word relations such as co-reference and taxonomic relations is introduced. These arcs are also derived from other sources, including Speech Act and Rhetoric Structure theories. The proposed approach is subject to evaluation in the product search and recommendation domain, where search queries include multiple sentences. An open source plugin for SOLR is developed so that the proposed technology can be easily integrated with industrial search engines.


Introduction
Modern search engines are not very good at tackling queries consisting of multiple sentences. They either find very similar documents, if they are available, or very dissimilar ones, so that search results are not very useful to the user. This is due to the fact that for multi-sentences queries it is rather hard to learn ranking based on user clicks, since the number of longer queries is practically unlimited. Hence we need a linguistic technology, which would rank candidate answers based on structural similarity between the question and the answer. In this study we build a graph-based representation for a paragraph of text so that we can track the structural difference between these paragraphs, taking into account not only parse trees, but the whole discourse as well.
Paragraphs of text as queries appear in the search-based recommendation domains (Montaner et al., 2003;Bhasker and Srikumar 2010;Thorsten, 2012). Recommendation agents track user chats, user postings on blogs and forums, user comments on shopping sites, and suggest web documents and their snippets, relevant to a purchase decisions. To do that, these recommendation agents need to take portions of text, produce a search engine query, run it against a search engine API such as Bing or Yahoo, and filter out the search results which are determined to be irrelevant to a purchase decision. The last step is critical for a sensible functionality of a recommendation agent, and poor relevance would lead to a lost trust in the recommendation engine. Hence an accurate assessment of similarity between two portions of text is critical to a successful use of recommendation agents.
Parse trees have become a standard form of representing the syntactic structures of sentences (Abney, 1991;Punyakanok et al., 2005;Domingos and Poon, 2009). In this study we will attempt to represent a linguistic structure of a paragraph of text based on parse trees for each sentence of this paragraph. We will refer to the set of parse trees plus a number of arcs for intersentence relations between nodes for words as Parse Thicket (PT). A PT is a graph, which includes parse trees for each sentence, as well as additional arcs for inter-sentence relationship between parse tree nodes for words.
We define the operation of generalization of text paragraphs via generalization of respective PTs to assess similarity between them. The use of generalization for similarity assessment is inspired by structural approaches to machine learning (Mill, 1843;Mitchell, 1997;Furukawa 1998;Finn, 1999) versus statistical alternatives where similarity is measured by a distance in feature space (Fukunaga, 1990;Manning and Schütze, 1999;Byun and Lee, 2002;Jurafsky and Martin, 2008). Our intention is to extend the operation of least general generalization (e.g., the antiunification of logical formulas (Robinson, 1965;Plotkin, 1970)) towards structural representations of paragraph of texts to compute similarity between multi-sentence questions and answers. Hence we define the operation of generalization on a pair of PT as finding the maximal common sub-thickets based on generalizing phrases from two paragraphs of text.
Generalization of text paragraphs is based on the operation of generalization of two sentences, explored in a few studies (Galitsky et al., 2008;Galitsky, 2012). In addition to learning generalizations of individual sentences, we learn how the links between words in sentences other than syntactic ones can be used to compute similarity between texts. We rely on our formalizations of the theories of textual discourse such as Rhetoric Structure Theory (Mann et al., 1992) to improve the ranking of paragraph-based question answering.
Whereas machine learning of syntactic parse trees for individual sentences is an established area of research, the contribution of this paper is a structural approach to learning syntactic information at the level of paragraphs. A number of studies applied machine learning techniques to syntactic parse trees (Collins and Duffy, 2002), convolution kernels (Haussler, 1999) being the most popular approach (Lodhi et al., 2002;Moschitti, 2006;, Sun et al., 2010.

Parse Thickets for matching questions and answers
Once we have a sequence of parse trees for a question, and that of an answer, how can we match these sequences? A number of studies compute pair-wise similarity between parse trees (Collins and Duffy, 2002;Punyakanok et al., 2003;Moschitti, 2006). However, to rely upon discourse structure of paragraphs, and to avoid dependence of how content is distributed through sentences, we represent the whole paragraphs of questions and answers as a single graph and call it Parse Thicket (PT). To determine how good is an answer for a question, we match their respective PTs. We extend the syntactic relations between the nodes of the syntactic dependency parse trees towards more general text discourse relations.
Once we have such relations as "the same entity", "sub-entity", "super-entity" and anaphora, we can extend the notion of phrase to be matched between texts. In case of single sentences, we match noun, verb, and other types of phrases in questions and answers. In case of multiple sentences in each, we extend the notion of phrases so that they are independent of how information being communicated is split into sentences. Relations between the nodes of parse trees (which are other than syntactic) can merge phrases from different sentences or from a single sentence, which are not syntactically connected. We will refer to such extended phrases as thicket phrases.
We will consider two cases for text indexing, where establishing proper coreferences inside and between sentences connects entities in an index for proper match with a question: Text for indexing 1: … Tuberculosis is usually a lung disease. It is cured by doctors specializing in pulmonology.
Text for indexing 2: … Tuberculosis is a lung disease… Pulmonology specialist Jones was awarded a prize for curing a special form of disease.
Question: Which specialist doctor should treat my tuberculosis?
In the first case, establishing coreference link Tuberculosis → disease → is cured by doctors pulmonologists helps to match these entities with the ones from the question. In the second case this portion of text does not serve as a relevant answer to the question, although it includes keywords from this question. Hence at indexing time, keywords should be chained not just by their occurrence in individual sentences, but additionally on the basis of coreferences. If words X and Y are connected by a coreference relation, an index needs to include the chain of words X 0 , X 1 …X, Y 0 ,Y 1 … Y, where chains X 0 , X 1 …X and Y 0 ,Y 1 … Y are already indexed (phrases including X and Y). Hence establishing coreferences is important to extend index in a way to improve search recall. Usually, keywords from different sentences can only be matched with query keywords with a low score (high score is delivered by inter-sentence match). If we have two parse trees 1 P and 2 P of text 1 T , and an arc for a relation 12 : jj r P P  between the nodes 1 j P and 2 j P , we can now match 1 2 1 1 1 2 2 1 2 2 , , , , , , , phrase of a single sentence or a merged phrases of multiple sentences from 2 T .

Finding similarity between a question and an answer
We will compare the following approaches to assessing the similarity of questions and answers as paragraphs:  Baseline: bag-of-words approach, which computes the set of common keywords/ngrams and their frequencies.
 Pair-wise matching: we will apply syntactic generalization to each pair of sentences, and sum up the resultant commonalities. This technique has been developed by Galitsky (2013).
The first approach is most typical for industrial NLP applications today, and the second one was used in . The kernel-based approach to parse tree similarities , as well as tree sequence kernel (Sun et al., 2011), being tuned to parse trees of individual sentences, also belongs to the second approach.
We intend to demonstrate the richness of the approach being proposed, and in the consecutive sections we will provide a step-by-step explanation. We will introduce a pair of short texts (articles) and compare the above three approaches. The first paragraph can be viewed as a search query, and the second paragraph can be viewed as a candidate answer. A relevant answer should be a closely related text, which is not a piece of duplicate information.
"Iran refuses to accept the UN proposal to end the dispute over work on nuclear weapons", "UN nuclear watchdog passes a resolution condemning Iran for developing a second uranium enrichment site in secret", "A recent IAEA report presented diagrams that suggested Iran was secretly working on nuclear weapons", "Iran envoy says its nuclear development is for peaceful purpose, and the material evidence against it has been fabricated by the US", ^ "UN passes a resolution condemning the work of Iran on nuclear weapons, in spite of Iran claims that its nuclear research is for peaceful purpose", "Envoy of Iran to IAEA proceeds with the dispute over its nuclear program and develops an enrichment site in secret", "Iran confirms that the evidence of its nuclear weapons program is fabricated by the US and proceeds with the second uranium enrichment site" The list of common keywords gives a hint that both documents are on nuclear program of Iran, however it is hard to get more specific details. Iran, UN, proposal, dispute, nuclear, weapons, passes, resolution, developing, enrichment, site, secret, condemning, second, uranium Pair-wise generalization gives a more accurate account on what is common between these texts. "  " in the following example and through all the paper means generalization operation. Describing parse trees we use standard notation for constituency trees: […] represents subphraze, NN, JJ, NP etc. denote parts-of-speech and types of subphrases, * is used to denote random tree node.
One can feel that PT-based generalization almost as complete as human would do in terms of similarity between texts. To obtain these results, we need to be capable of maintaining connections between sentences such as coreferences, and also of apply the relationships between entities to our analysis (entities, subentities, super-entities) obtained from WordNet or via web mining (Galitsky et al 2013). We also need to be able to identify communicative actions and generalize them together with their subjects according to the specific patterns of speech act theory, if a text describes an interaction between people. Moreover, we need to maintain rhetoric structure relationship between sentences, to generalize at a higher level above sentences irrespectively of how information is distributed through sentences. We define Parse Thicket as a set of parse trees for sentences with arcs for links between the words of different sentences. These arcs are for coreferences, entity-entity and rhetoric relations, and communicative actions.
The focus of this paper is to apply parse thickets and their generalization to search relevance where a query is a paragraph of text.

From phrase to paragraph-level generalization
Although the generalization is defined as the set of maximal common sub-graphs, its computation in this study is based on matching phrases. To generalize a pair of sentences, we perform chunking and extract all noun, verb, prepositional and other types of phrases from each sentence. Then we perform generalization for each type of phrases, attempting to find a maximal common sub-phrase for each pair of phrases of the same type. The resultant phraselevel generalization can then be interpreted as a set of paths in resultant common sub-trees . Thicket phrases are the regular phrases extended by the words from other sentences linked by inter-sentence arcs. The algorithm of forming thicket phrases is as follows. Most types of thicket arcs will be illustrated below. Please refer to

Arcs of parse thicket based on theories of discourse
We treat computationally the following approaches to textual discourse:  Rhetoric structure theory (RST) (Mann et al., 1992);  Speech Act theory or shortly SpActT (Searle, 1969). Although both these theories have psychological observation as foundations and are mostly of a non-computational nature, a specific computational framework need to be built for them (Galitsky et al., 2010;2013a). We use these sources to find links between sentences to enhance indexing for search. For RST, we attempt to extract an RST relation and form a thicket phrase around it, including a placeholder for RST relation itself. For SpActT, we use a vocabulary of communicative actions to find their subjects (Galitsky and Kuznetsov, 2008), add respective arcs to PT and form the respective set of thicket phrases. Fig.1 shows the generalization instance based on RST relation "RCT-evidence" (Marcu, 1997).

This relation occurs between the phrases evidence-for-what [Iran's nuclear weapon program] and what-happens-with-evidence [Fabricated by USA] and evidence-for-what [against Iran's nuclear development] and what-happens-with-evidence [Fabricated by the USA].
Notice that in the latter case we need to merge (perform anaphora substitution) the phrase ' its nuclear development' with 'evidence against it' to obtain 'evidence against its nuclear development'. Notice the arc it -development, according to which this anaphora substitution occurred. Evidence is removed from the phrase because it is the indicator of RST relation, and we form the subject of this relation to match. Furthermore, we need another anaphora substitution its -Iran to obtain the final phrase.
As a result of generalizations of two RST relations of the same sort (evidence) we obtain Iran nuclear NNP -RST-evidencefabricate by USA. Notice that we could not obtain this similarity expression by using sentence-level generalization.

Communicative actions example
Communicative actions are used by text authors to indicate the structure of a dialogue or a conflict (Searle, 1969). Hence analyzing the communicative actions' arcs of PT, one can find implicit similarities between texts. We can generalize:  one communicative actions with its subject from 1 T against another communicative action with its subject from 2 T (communicative action arc is not used) ;  a pair of communicative actions with their subjects from 1 T against another pair of communicative actions from 2 T (communicative action arcs are used).
In our example, we have the same communicative actions with subjects with low similarity:

condemn ['Iran for developing second enrichment site in secret'] vs condemn ['the work of Iran on nuclear weapon']
or different communicative actions with similar subjects.
The two distinct communicative actions dispute and condemn have rather similar subjects: 'work on nuclear weapon'. Generalizing two communicative actions with their subjects follows the rule: generalize communicative actions themselves, and 'attach' the result to generalization of their subjects as regular sub-tree generalization. Two communicative actions can always be generalized, which is not the case for their subjects: if their generalization result is empty, the generalization result of communicative actions with these subjects is empty too. The generalization result here for the case 1 above is: condemn^dispute [ work-Iran-on-nuclearweapon].
Generalizing two different communicative actions is based on their attributes and is presented in (Galitsky et al., 2013).
Notice that generalization gives zero result because the arguments of condemn from 1 T and 2 T are not very similar. Hence we generalize the subjects of communicative actions first before we generalize communicative actions themselves.  Groups of vertices with the same shape and dark-gray border show the maximum common sub-thickets, where the number of vertexes serves as a score for similarity between a question and answer.

Evaluation of multi-sentence question answering
We proceed to evaluation of how generalization of PTs can improve multi-sentence search, where one needs to compare a query as a paragraph of text against a candidate answer as a paragraph of text (search result snippet).
Evaluation is based on a re-ranking search results obtained by Bing search engine API, relying on the PT similarity score. The similarity score is defined as a total number of vertexes in a common maximum subgraph. We approximate this estimate by calculating the number of words in maximal common sub-phrases, taking into account weight for parts of speech .
Evaluation results are shown in Table 1. Three domains are used in evaluation:  Product recommendation, where an agent reads chats about products and finds relevant information on the web about a particular product.
 Travel recommendation, where an agent reads chats about travel and finds relevant information on the travel websites about a hotel or an activity.
 Facebook recommendation, where an agent reads wall postings and chats, and finds a piece of relevant information for friends on the web.
In each of these domains we selected a portion of text on the web to form a query, and then filtered search results delivered by Bing search engine API. One can observe that unfiltered precision is 58.2%, whereas improvement by pair-wise sentence generalization is 11%, thicket phrases/snippetsadditional 6%, and thicket phrases for original sentences in the documentsadditional 1.5%.
One can also see that the higher the complexity of sentence, the higher the contribution of generalization technology, from sentence level to thicket phrases.

Algorithms and scalability of the approach
The generalization operation on parse trees for sentences and parse thickets for paragraphs is defined as finding a set of maximum common sub-trees and sub parse thickets respectively. Although for the trees this problem is O(n), for the general case of graphs finding maximal common sub-graphs is NP-complete (Kann, 1992).
To estimate the complexity of generalization of two PT, let us consider an average case with five sentences in each paragraph and 15 words in each sentence. Such thickets have on average 10 phrases per sentence, 10 inter-sentence arcs, which give us up to 40 thicket phrases each. Hence for such parse thickets we have to generalize up to 50 linguistic phrases and 40 thicket phrases of the first thicket against the set of similar size for the second thicket. Taking into account a separate generalization of noun and verb phrases, this average case consists of 2* 45*45 generalizations, followed by the subsumption checks. Each phrase generalization is based on up to 12 string comparisons, taking an average size of phrase as 5 words. Hence on average the PT generalization includes 2*45*45*12*5 operations. Since a string comparison takes a few microseconds, thicket generalization takes on average 100 milliseconds without use of index. However, in an industrial search application where phrases are stored in an inverse index, the generalization operation can be completed in constant time, irrespectively of the size of index (Lin, 2013).

Conclusions
In this work we build the framework for generalizing PTs as sets of phrases to re-rank search results obtained via keyword search.
The operation of generalization to learn from parse trees for a pair of sentences turned out to be important for text relevance tasks. Once we extended it to learning parse thickets for two paragraphs, we observed that the relevance is further increased compared to the baseline (Bing search engine API), which relies on keyword statistics in the case of multi-sentence query.
We considered the following sources of relations between words in sentences: coreferences, taxonomic relations such as subentity, partial case, predicate for subject etc., rhetoric structure relation and speech acts. We demonstrated that search relevance can be improved if search results are subject to confirmation by parse thicket generalization, when answers occur in multiple sentences.
The system architecture serves as a basis of OpenNLPsimilarity component, which is a separate Apache Software foundation project, accepting input from either OpenNLP or Stanford NLP. Code and libraries described here are available at http://code.google.com/p/relevance-based-onparse-trees and http://svn.apache.org/repos/asf/opennlp/sandbox/ opennlp-similarity/.
The system is ready to be plugged into Lucene library to improve search relevance. Also, a SOLR request handler is provided so that search engineers can switch to a PT-based multisentence search to quickly verify if relevance is improved. The system is designed for search engineers not familiar with linguistic technologies, who can plug in the richness of linguistic features of OpenNLP and Stanford NLP to work for them in a search application.