only for private and academic purposes. This volume is published and copyrighted by its editors. Recently, a new field has emerged taking benefit of both domains: Data Mining (DM) and Natural Language Processing (NLP). Indeed, statistical and machine learning methods hold a predominant position in NLP research1, advanced methods such as recurrent neural networks, Bayesian networks and kernel based methods are extensively researched, and ”may have been too successful (. . . ) as there is no longer much room for anything else”2. They have proved their e↵ectiveness for some tasks but one major drawback is that they do not provide human readable models. By contrast, symbolic machine learning methods are known to provide more human-readable model that could be an end in itself (e.g., for stylistics) or improve, by combination, further methods including numerical ones. Research in Data Mining has progressed significantly in the last decades, through the development of advanced algorithms and techniques to extract knowledge from data in di↵erent forms. In particular, for two decades Pattern
DMNLP’15, held on September 7, 2015 in Porto. DMNLP’15 (Workshop on Interactions between Data Mining and Natural Language Processing) is the second edition of a workshop dedicated to Data Mining and Natural Language Processing crossfertilization, i.e a workshop where NLP brings new challenges to DM, and where DM gives future prospects to NLP. It is well-known that texts provide a very challenging context to both NLP and DM with a huge volume of low-structured, complex, domain-dependent and task-dependent data. The objective of DMNLP is thus to provide a forum to discuss how Data Mining can be interesting for NLP tasks, providing symbolic knowledge, but also how NLP can enhance data mining approaches by providing richer and/or more complex information to mine and by integrating linguistic knowledge directly in the mining process.
Organization Program Chairs
Program Commitee
Mining Comparative Sentences from Social Medias . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Fab´ıola S. F. Pereira 1 3 5
Annotated sux tree similarity measure for text summarization
Maxim Yakovlev and Ekaterina Chernyak National Research University – Higher School of Economics
Moscow, Russia myakovlev,echernyak@hse.ru Abstract. The paper describes an attempt to improve the TextRank algorithm. TextRank is an algorithm for unsupervised text summarisation.
It has two main stages: first stage is representing a text as a weighted
directed graph, where nodes stand for single sentences, and edges are
weighted with sentence similarity and connect sequential sentences. The
second stage is applying the PageRank algorithm [
The nodes that get the highest ranks form the summary of the text.
We focus on the first stage, especially on measuring the sentence
similarity. Mihalcea and Tarau [
Our idea is to replace this scheme by using the annotated sux trees
(AST) [
More specifically we develop an algorithm for common subtree construction and annotation. The common subtrees are used to score the similarity between two sentences. Using this algorithm allows us to achieve slight improvements according to cosine baseline on our own collection of Russian newspaper texts. The AST measure gained around 0.05 points of precision more than the cosine measure. This is a great figure for natural language processing task, taking into account how low the baseline precision of the cosine measure is. The fact that the precision is so low can be explained by some lack of consistency in the constructed collection: the authors of the articles use di↵erent strategies to highlight the important sentences. The text collection is heterogeneous: in some articles there are 10 or more sentences highlighted, in some only the first one.
Unfortunately, there is no other test collection for text summarisation in Russian. For further experiments we might need to exclude some articles, so that the size of summary would be more stable. Another issue of our test collection is the selection of sentences that form summaries. When the test collections are constructed manually, summaries are chosen to common principles. But we can not be sure that the sentences are not highlighted randomly.
Although the AST technique is rather slow, it is not a big issue for the text summarisation problem. The summarisation problem is not that In: P. Cellier, T. Charnois, A. Hotho, S. Matwin, M.-F. Moens, Y. Toussaint (Eds.): Proceedings of DMNLP, Workshop at ECML/PKDD, Porto, Portugal, 2015.
Copyright c by the paper’s authors. Copying only for private and academic purposes.
kind of problems where on-line algorithms are required. Hence the precision plays more significant part than time characteristics.
There are several directions of future work. First of all, we have to
conduct experiments on the standard DUC (Document Understanding
Conference [
Keywords: TextRank, annotated sux tree
Narrative Generation from Extracted Associations Pierre-Luc Vaudry and Guy Lapalme
Université de Montréal, Montréal, Canada {vaudrypl,lapalme}@iro.umontreal.ca
In [
Our experiment applies association rules discovery techniques in [
The generation of a report from the ADL data for a given period follows a pipeline architecture. The first stage is data interpretation, which consists of finding instances of the previously selected association rules in the input. For each of those, one or more semantic relations are introduced as part of a hypothetic interpretation of the input data. Next those relations are used to plan the document as a whole in the document planning stage. The output is a rhetorical structure which is then pruned to keep only the most important events and relations. Follows a microplanning stage that plans the phrases and lexical units expressing the events and rhetorical relations. This produces a lexico-syntactic specification that is realised as natural language text in the last stage: surface realisation.
After analysing the results, the extracted relations seem to be useful to locally link activities with explicit rhetorical relations. However, further work is needed to better exploit them for improving coherence at the global level.
Some Thoughts on Using Annotated Sux Trees for Natural Language Processing
Ekaterina Chernyak National Research University – Higher School of Economics
Moscow, Russia echernyak@hse.ru Abstract. The paper defines an annotated sux tree (AST) - a data structure used to calculate and store the frequencies of all the fragments of the given string or a collection of strings. The AST is associated with a string to text scoring, which takes all fuzzy matches into account. We show how the AST and the AST scoring can be used for Natural Language Processing tasks.
Keywords: text representation, annotated sux tree, text summarization, text categorization 1
Introduction
Natural Language Processing tasks require a text being represented by a sort
of a formal structure to be processed by a computer. The most popular text
representation is the Vector Space Model (VSM), designed by Salton [
In this paper we are going to concentrate on the so-called annotated sux
tree (AST), introduced in [
The project is being developed by the “Methods of web corpus collection, analysis and visualisation” research and study group under guidance of prof. B. Mirkin (grant 15 - 05 - 0041 of Academic Fund Program). 2
Annotated sux tree
The sux tree is a data structure used for storing of and searching for strings of
characters and their fragments [
An annotated sux tree (see Figure 1)[
AST construction
Our algorithm for constructing an AST is a modification of the well-known
algorithm for constructing sux trees [
Psuffix score(match(suf f ix, ast)) = |string| where |string| is the length of the string.
Note, that “score” is found by applying a scaling function to convert a match
score into the relevance evaluation. There are three useful scaling functions,
according to experiments in [
x 1
x (x) = log = log x log(1 x) – Root function (x) = p x The identity scaling stands for the conditional probability of characters averaged over matching fragments (CPAMF).
Consider an example to illustrate the described method. Let us construct an the for the string “mining”. This string has six suxes: “mining”, “ining”, “ning”, “ing”, “ng”, and “g’ . We start with the first sux and add it to the empty AST as a chain of nodes with the frequencies equal to unity. To add the next sux, we need to check whether there is any match, i.e. whether there is such a path in the AST starting at its root that encodes / reads a prefix of “ining”. Since there is no match between existing nodes and the second sux, we add it to the root as a chain of nodes with the frequencies equal to unity. We repeat this step until a match is found: a prefix of the fourth sux “ing” matches the second sux “ining”: two first letters, “in”, coincide. Hence we add 1 to the frequency of each of these nodes and add a new child node “g” to the leaf node “n” (see Figure 1). The next sux “ng” matches the third sux and we repeat the same actions: increase the frequency of the matched nodes and add a new child node that does not match. The last sux does not match any path in the AST, so again we add it to the AST’s root as a single node with its frequency equal to unity. Now let us calculate the relevance score for string “dining” using the AST in Figure 1. There are six suxes of the string “dining”: ‘dining”, “ining”, “ning”, “ing”, “ng”, and “g’ . Each of them is aligned with an AST path starting from the root. The scorings of the suxes are presented in Table 1.
We have used the identity scaling function to score all 6 suxes of the string “dining”. Now, to get the final CPAMF relevance value we sum and average relevance(dining, mining) =
In spite of the fact that “dining” di↵ers from “mining” by just one character, the total score, 0.44, is less than unity. This is not only because the trivial sux “dining” contributes 0 to the sum, but also because conditional probabilities get smaller for the shorter suxes. 3
Spam filtering
The definition of the AST presented above was for first time introduced by
Pampapathi, Mirkin and Levene in [
Research paper categorization The problem of text categorization is formulated as follows. Given a collection of documents and a domain taxonomy, annotate a document with relevant taxonomy topics. A taxonomy is a rooted tree, such that every node corresponds to a (taxonomy) topic of the domain. The taxonomy generalizes the relation “is – a” or “is a part of”.
There are two basic approaches to the problem of text categorization:
supervised and unsupervised. Supervised approaches give high precision values
when applied to web document categorization [12], but may fail when applied
to research paper categorization, since the research taxonomies, such as ACM
Computing Classification System [13], are seldom revised and the supervised
techniques may overfit [14]. The unsupervised approaches to text categorization
are based on information retrieval – like idea: given the set of taxonomy topics,
let us find those research papers that are relevant to every topic. The question
for researcher is the following: what kind of the relevance model and measure
to choose? In [15] we experimentally compared cosine relevance function, which
measures the cosine between tf idf vectors in Vector Space Model [
Taxonomy refinement Taxonomies are widely used to represent, maintain and store domain knowledge, see, for example SNOMED [18] or ACM CCS [13]. Domain taxonomy construction is a dicult task and a number of researchers have come out with idea of taxonomy refinement. The idea of taxonomy refinement is the following: having one taxonomy or upper levers of taxonomy refine it with topics extracted from additional sources such as other taxonomies, web search or Wikipedia. We followed this strategy and developed a two-step approach to taxonomy refinement, presented in more details in [21]. We concentrated on taxonomies of probability theory and mathematical statistics (PTMS) and numerical mathematics (NM), both in Russian. On a first step an expert sets manually the upper layers of taxonomy. On the second step these upper layers are refined by Wikipedia category tree and the articles, belonging to this tree, from the same domain. In this study the AST scoring is used several times: – To clear the Wikipedia data from noise; – To assign the remaining Wikipedia categories to the taxonomy topics; – To form the intermediate layers of the taxonomy by using Wikipedia subcategories; – To use Wikipedia articles in each of the added category nodes as its leaves. The Wikipedia data is rather noisy: there some articles that are stubs or irrelevant to parental categories (the categories, they belong to) and the more so there are subcategories (of a category) that are irrelevant to the parental categories. For example, we found the article “ROC curve” be irrelevant to the category “Regression analysis” and the category “Accidentally killed” to the category “Randomness”. To define what article is irrelevant we exploit the AST scoring twice: – We scored the title of the article to the text of the article to detect stubs; – We scored the title of the parental category to the text of the article to detect irrelevant category.
If the value of the scoring function is less than a threshold we decided that the article is irrelevant. Usually we set the threshold at 0.2. To assign the remaining Wikipedia categories to the taxonomy topics we score the taxonomy topics to all the articles in the category merged into one text. Next we found the maximum value of the scoring function and assigned the category to the corresponding 7 11 taxonomy topic. Finally, we score the title of parental categories to the articles of the subcategories, merged into one. If the subcategory to category scoring is higher than the subcategory to taxonomy topic, the subcategory remains on the intermediate layer of the refined taxonomy tree under its parental category. Finally, the articles left after clearing from noise became leaves in the refined taxonomy tree. The quality of achieved PTMS and NM taxonomies is dicult to evaluate computationally, so the design of the user study is an open question. 6
Text summarization Automatic text summarisation is one of the key tasks in natural language processing. There are two main approaches to text summarisation, called abstractive and extractive approaches [22].
According to the abstractive approach, the summary of a text is another text, but much shorter, generated automatically to make the semantic representation of the text. According to extractive approach, the summary of a text is nothing else, but some important parts of the given text, such as a set of important sentences.
The extractive summarisation problem can be formulated in the following way. Given a text T that is a sequence of sentences S that consists of words V , select a subset of the sentences S⇤ that are important in T . Therefore we need to define: – what importance of a sentence is; – how to measure importance of the sentence; Hence we need to introduce a function, importance(s), which measures the importance of a sentence. The higher importance is, the better. Next step is to build the summary. Let us rank all the sentences according the values of importance. Suppose we look for the summary that consists of five sentence. Hence we take the five sentences with the highest values of importance and call them top-5 sentences according to importance. Generally, the summary of the text are the top-N sentences according to importance and N is set manually.
The best results for this statement of the problem are achieved by Mihalcea and Tarau [23], where importance(s) is introduced as PageRank type function [24] without any kind of additional grammar, syntax or semantic information. The main idea of the suggested TextRank algorithm is to represent a text as a directed graph, where nodes stand for sentences and edges connect sequential sentences. The edges are weighted with sentence similarity. When PageRank is applied to this graph, every node receives its rank that is to be interpreted as the importance of the sentence, so that importance(s) = P ageRank(snode), where snode is the node corresponding to sentence s.
To measure similarity of the sentences the authors of TextRank algorithm suggest to use the basic VSM (Vector Space Model) scheme. First every sentence is represented as a vector in space of words or stems. Next cosine similarity between those vectors is computed. We can use the AST scoring as well for scoring the similarity between two sentences. To do this we have to introduce the common tree technique. 6.1
Constructing common subtree for two ASTs To estimate the similarity between two sentences we find the common subtree of the corresponding ASTs. We do the depth-first search for the common chains of nodes that start from the root of the both ASTs. After the common subtree is constructed we need to annotate and score it. We annotate every node of the common subtree with the averaged frequency of the corresponding nodes in initial ASTs. Consider for example two ASTs for strings “mining” and “dinner” (see Fig. 1 and Fig. 2, correspondingly). There are two common chains: “I N” and “N”, the first one consists of two nodes, the second one consists of a single node. Both this chains form the common subtree. Let us annotate it. The frequency of the node “I” is equal to 2 in the first AST and to 1 in the second. Hence, the frequency of this node in the common subtree equals to 2+1 = 1.5. In the same 2 way we annotate the node “N” that follows after the node “I” with 2+1 = 1.5 2 and the node “N” on the first level with 2+2 = 2. The root is annotated with 2 the sum of the frequencies of the first level nodes that is 1.5 + 2 = 3.5. 6.2
Scoring common subtree The score of the subtree is the sum of scores of every chain of nodes. The score of the path is the averaged sum of the conditional probabilities of the nodes, where conditional probability of the node is the frequency of the node divided by the frequency of its parent. For example, the conditional probability of the node “G:1” on the third level of the AST on Fig. 1 is 1/2. Let us continue with the example of “mining” and “dinner”. There are two chains in their common subtree: “I N” and “N”. The score of “I N” chain is (1.5/1.5 + 1.5/3.5)/2 = 0.71, since there are 2 nodes in the chain. The score of one node chain “N” is 1.5/3.5 = 0.42. The score of the whole subtree is (0.71 + 0.42) = 1.13.
The collection for experiments was made of 400 articles from Russian news portal called Gazeta.ru. The articles were marked up in a special way, so that some of sentences were highlighted because of being more important. This highlighting was done either by the author of the article or by the editor on the basis of their own ideas. In our experiments we considered those sentences as the summary of the article. We tried to reproduce these summaries using TextRank with cosine similarity measure and AST scoring.
Using this algorithm allowed us to gain around 0.05 points of precision according to cosine baseline on our own collection of Russian newspaper texts. This is a great figure for Natural Language Processing task, taking into account that the baseline precision of the cosine measure was very low. The fact that the precision is so low can be explained by some lack of consistency in the constructed collection: the authors of the articles use di↵erent strategies to highlight the important sentences. The text collection is heterogeneous: in some articles 1, 2, and 3, respectively. Moreover, all type 3 expressions were identified by the Concrete-Abstract algorithm as literal leading to the F-measure of zero. The most likely reason for that is that our dataset rarely contains expressions where the noun is an abstract noun (e.g., the noun “thoughts” in the expression “dark thoughts” is an abstract noun) and most metaphoric expressions contain concrete nouns (e.g., the noun “heart” in the expression “broken heart” is a concrete noun). Since Conc-Abs relies on a single feature, which is the noun’s abstractness level, it cannot detect a metaphor in these cases. However, CCO outperformed MIL, especially in type 2 and type 3 expressions. Unlike MIL, which is a supervised learning approach, CCO is a rule-based method, requiring for each new language and domain a significant amount of manual expert labor along with multiple high-quality knowledge resources, which are unavailable for most human languages. The F-measure results reported by (Tsvetkov, et al., 2014) for type 2 and type 3 expressions (76%) are also better than the results reached by MIL, but their system is dependent upon a massive knowledge resource –WordNet.
Table 5 shows the list of features and the classifier selected by the Wrapper method of (Kohavi & John, 1997) for each expression type. We can conclude from the selected feature list that the feature First k Documents is a general feature, since it has been selected in all three expression types. The following features have been selected for two expression types out of three: Domain Corpus Frequency (Types 1 and 3), Cosinesimilarity Variance (Types 1 and 3), and Cosine-similarity Average (Types 2 and 3). These results imply that for detecting conceptual mapping between two words in a given expression, it can be useful to consider the semantic neighborhood of each word as well as its frequency in the domain corpus.
Semantic Relation First k Documents Domain Corpus Frequency Abstract Scale Average Cosine-similarity Variance Abstract Scale First k Documents First k Words Semantic Relation Average Cosine-similarity Average Cosine-similarity First k Documents Abstract Scale difference Documents’ Jaccard Similarity Domain Corpus Frequency Domain Corpus Frequency Difference Cosine-similarity Average Cosine-similarity Variance
Selected Classifier Random Forest AdaBoost Base with
Naïve AdaBoost with VFI 5
Conclusion In this paper, we have presented a novel supervised learning approach for automatic metaphor identification in three syntactic structure types. We have extended the single feature set used by Turney, et al. (2011) with a large amount of statistical features. We have shown a significant improvement vs. a learning-based algorithm (Concrete-Abstract). However, MIL was outperformed by a rule-based algorithm (CCO), which applies a set of rules to a candidate expression in order to determine if it is a literal or not. In CCO, the rules are generated separately for each of the three expression types, and if a candidate expression satisfies all of them, it is labelled as literal. Otherwise, it is labeled as a metaphor. Although CCO outperformed MIL, it has some major disadvantages. One of the major disadvantages is that the rules are based on a relatively large amount of linguistic resources, including COCA (Corpus of Contemporary American English http://www.ngrams.info/), ConceptNet (http://conceptnet5.media.mit.edu/), WordNet (https://wordnet.princeton.edu/), and Wiktionary (https://en.wiktionary.org/wiki/English).
Future research on using statistical features for metaphor detection may include experimentation with additional predictive features, domains, and languages. Transfer learning across different domains may also be explored.
A Peculiarity-based Exploration of Syntactical Patterns: a Computational Study of Stylistics
Mohamed-Amine Boukhaled, Francesca Frontini, Jean-Gabriel Ganascia LIP6 (Laboratoire d’Informatique de Paris 6), Université Pierre et Marie Curie and CNRS (UMR7606), ACASA Team, 4, place Jussieu,
75252-PARIS Cedex 05 (France) {mohamed.boukhaled, francesca.frontini, jean
gabriel.ganascia}@lip6.fr Abstract. In this contribution, we present a computational stylistic study and comparison of classic French literary texts based on a datadriven approach where discovering interesting linguistic patterns is done without any prior knowledge. We propose an objective measure capable of capturing and extracting meaningful stylistic syntactic patterns from a given author’s work. Our hypothesis is based on the fact that the most relevant syntactic patterns should significantly reflect the author’s stylistic choice and thus they should exhibit some kind of peculiar overrepresentation behavior controlled by the author’s purpose with respect to a linguistic norm. The analyzed results show the effectiveness in extracting interesting syntactic patterns from novels, and seem particularly promising for the analysis of such particular texts. 1
Introduction Computational stylistics is a subdomain of computational linguistics located at the intersection of several research areas such as natural language processing, literary analysis and data mining. The goal of computational stylistics is to extract style patterns characterizing a particular type of texts using computational and automatic methods (Craig 2004). When investigating the writing style of a particular author, the task will automatically explore linguistic forms of his style, which is not only distinguishing features, but also the deliberate overuse of certain structures by the author compared to a linguistic norm (Mahlberg 2012). However, the notion of style in the context of computational stylistics appears to be wide enough, and is manifested on several linguistic levels: lexicon, syntax, semantics and pragmatics. Each level has its own markers of styles and its own linguistic units that characterize it. Many works have been done in the literature to analyze the stylistic traits on these different linguistic levels ( Biber 2006, Biber & Conrad 2009, Ramsay 2011, Frontini et al. 2014; see Siemens & Schreibman, 2013 for a discussion and overview ). In this contribution, syntactic style will be targeted. In their study Quiniou et al. (2012) have shown the interest of using sequential data mining methods for the stylistic analysis of large texts. They have shown that relevant and understandable patterns that are characteristic of a specific type of text can be extracted using sequential data mining techniques such as sequential pattern mining.
However, the process of extracting textual patterns is known by its property of producing a large amount of patterns, even from a relatively small sample of text. Thus, a measure of interest is to be applied to identify the most important and relevant patterns for the characterization of the text’s style in question.
In this paper, we present a computational stylistic study of classic texts of French literature based on a data-driven approach where the discovery of interesting linguistic forms is done without any prior knowledge. Specifically, the proposed method is based on the assessment of the peculiar overrepresentation of syntactic patterns extracted using sequential data mining technique from texts with respect to a norm corpus. This method is intended to quantitatively support a textual analysis by focusing on the verification of the degree of importance of each syntactic pattern (syntagmatic segments with potential gaps), and by extracting the syntactic patterns that characterize the syntactical style of a work by a particular author. 2
Approach for extracting relevant syntactic patterns Our method consists of two steps. First, a sequential pattern mining algorithm is applied to the texts in order to extract recurrent syntactic patterns. Second, a peculiarity-based interestingness measure that evaluates of the overrepresentation (in terms of frequency of occurrence with respect to a norm corpus) is applied to the set of extracted syntactic patterns. Thus, each syntactic pattern will be assigned an interestingness value indicating its importance and its relevance for the characterization of text’s syntactic style. In what follows, we present in section 2.1 the corpus used in our experience, and its dividing protocol into two parts: text to analyze and text used as norm. Then, section 2.2 introduces some elements necessary to understand the process of extracting sequential syntactic patterns. Finally, the formulation and the statistical details of the proposed interestingness measure are presented in Section 2.3. 2.1 In our study, we used four novels, belonging to the same genre and the same literary time span, written by four famous classic French authors: Balzac’s “Eugenie Grandet”, Flaubert's “Madame Bovary”, Hugo’s “Notre Dame de Paris” and Zola’s “Le ventre de Paris”. This choice is motivated by our particular interest in studying the style of the classical French literature of the 19th century. At the time of the analysis of the syntactic patterns, each text written by one of the four authors is contrasted with texts written by the three other authors. That is to say that these three texts will be considered as norm corpus from which we will evaluate the hypothesis of the overrepresentation of syntactic patterns in the fourth remaining text, as explained later in this section. 2.2
Extraction of syntactic patterns In our study we consider a syntagmatic approach. The text is first segmented into a set of sentences, each sentence is then represented by a sequence of syntactic labels (POS-tag)1 corresponding to the words of the sentence using Treetagger (Schmid 1994). This produces at the end a set of syntactic sequences for each text. For exemple, the sentence “Le silence profond régnait nuit et jour dans la maison.” Will be represented by the sequence: < "#$ , '() , *"+ , ,#- , '() , .(' , '() , /-/ , "#$ , '() , 0#'$ > Then, sequential patterns of a certain length with their supports (a number indicating how many sentences contain the pattern) are extracted from this syntactic sequential database using a sequential pattern extraction algorithm (Viger et al. 2014). Syntactic pattern consists of a sequential syntagmatic segment (with possible gaps) present in the syntactic sequences. It can be considered as a kind of generalization of the notion of n-gram widely used in the field of automatic language processing. Examples of syntactic patterns present in the sequence of the example above: • < "#$ >< '() >< *"+ > • < '() >< *"+ >< ,#- >< '() > • < .(' >< '() > <∗ 2 > < "#$ >< '() >
To avoid the effect of statistical fluctuations on the analysis of patterns with low supports, we considered a support’s threshold of 1%. That is to say that we focus only on patterns that are present in at least 1% of the sentences of the analyzed text. However, as sequential pattern mining is known to produce a large quantity of patterns even from relatively small samples of texts, 1 Frech treetagger tagset:
http://www.cis.unimuenchen.de/~schmid/tools/TreeTagger/data/french-tagset.html 2 <*> denotes a gap that can be filled with any POS tag an interestingness measure should be applied on these patterns in order to identify the most important ones. This interestingness measure is explained in the next section. 2.3
Evaluation of the relevance of syntactic patterns Our hypothesis to evaluate the relevance of a syntactic pattern is based on the fact that the most relevant ones should significantly reflect the stylistic choice of the author and should thus be characterized by a significant peculiar quantitative behavior, this peculiar behavior translate into a support’s overrepresentation in his texts.
However, to capture this overrepresentation one cannot refer only to the absolute frequency of occurrence (support) Indeed, more frequent use of a syntactic pattern by an author (which translates into a relatively high support) does not necessarily indicate a stylistic choice since it can be very well a property imposed by the grammar of the language or by syntactic features that are characteristic of text’s genre.
Thus, to assess the over-representation of a pattern, we use an empirical approach based on the comparison of the support of a syntactic pattern in a text to that found in a norm corpus. A ratio 4 between these two quantities is calculated as follow: 4 = frequency of a pattern in the norm corpus
frequency pattern in the text In our experiments we found empirically that the distribution of the ratio 4 exhibits a Gaussian behavior. Indeed, the values of the 4 ratio are normally distributed around a central value (see Fig. 1). This is due to the fact that the frequency of occurrence of a syntactic pattern in a text is highly correlated with the frequency of occurrence in the norm corpus with a few exceptional special cases or outliers (see Fig. 2). These outliers represent the patterns of special interest for our study because they represent a certain linguistic deviation that is specific to the author's style compared to what one would expect to see in the norm corpus.
Fig. 1. Gaussian behaviour of the ratio 4 in Balzac’s “Eugénie Grandet” novel
Results and Discussion
In this section, we present some examples of relevant syntactic patterns extracted from our corpus. Using the proposed method, the extracted patterns seem to have a strong relevance to characterize the style of the authors of our corpus but also to the novels’ content and the literary genre in which it operates. In the Flaubert's Madame Bovary, several extracted patterns well represent the rhythmic rather than functional role of punctuation that is peculiar to the style of Flaubert (Mangiapane 2012). For example pattern (1) captures instances of a comma preceding the conjunction, followed by a parenthetical clause.
Pattern (1) <PUN> < KON>< PUN> <PRP>, with support= 113, sample instances of the pattern in the text: • , et , à • , mais , avant • ; et , à In le Ventre de Paris of Zola, and in the same direction, the syntactic patterns extracted as relevant clearly represent the use of nested clauses to describe situations or attitudes in the novel such as in the pattern (2), or to describe public places and objects in displays in long lists as in the pattern (3):
Pattern (2) : <PUN> <PRP> <PRP> <NOM>, support= 104, sample instances of the pattern in the text (bold text): « Florent se heurtait à mille obstacles , à des porteurs qui se chargeaient , à des marchandes qui discutaient de leurs voix rudes ; il glissait sur le lit épais d' épluchures et de trognons qui couvrait la chaussée , il étouffait dans l' odeur puissante des feuilles écrasées .»
Pattern (3): <NOM> <PUN> <PRP> <NOM> <ADJ>, support= 68, sample instances of the pattern in the text (bold text): • angles , à fenêtres étroites • très-jolies , des légendes miraculeuses • écrevisses , des nappes mouvantes
In Eugénie Grandet of Balzac, other different communicative functions are performed by the syntactic patterns and their textual instances, for example:
Pattern (4): <PUN> <VER> <NAM> <PRP>, support= 49, which is used as post-introducer of direct speech. This rather formulaic way of specifying (in a parenthetical form) the utterer of a reported speech is common to all, but seems to be strongly preferred by Balzac, while the other authors have shown a more varied style in introducing dialogues. Sample instances of the pattern in the novel: • , dit Grandet en • , reprit Charles en • , dit Cruchot en
Pattern (5): <NUM> <NUM> <NOM>, support= 54, is a pattern used to refer to money, which is typical for the novel scenario where money plays a very important role. Sample instances of the pattern in the novel: • vingt mille francs • deux mille louis • sept mille livres
Pattern (6) : <ADV> <VER> <PRO> <ADV>, support= 59, is used to express negative questions : • n' avait -il pas • ne disait -on pas • ne serait -il pas
Pattern (7) : <PUN> <NOM> <PUN> <VER>, support= 44, represent the punctuation extensively used to mimic spoken intonation and even to reproduce performance phenomena such as stutter. : • , messieurs , cria • , madame , répondit • , mademoiselle , disait
The few analyzed examples indicate that the presented technique is effective in extracting interesting syntactic patterns from a single text, and this seems particularly promising for the analyses of such classic literary texts. On the other hand, this technique, as well as other similar ones, prompts the question of what is really captured by significant patterns. Some structures may be significant because they are typical of an author’s style, its fingerprint - as we may say borrowing a metaphor often used in attribution studies, or they may be dictated by functional needs, due to the particular topic of the novel, or to the conventions of the chosen genre. This is particularly true for syntactic analysis, where the functional constraints on the authorial freedom are more evident. Much further works have to be carried out concerning this issue. 4
conclusion In this paper, we have presented an objective interestingness measure to extract meaningful stylistic syntactic patterns from a given author’s work. Our hypothesis is based on the fact that the most relevant syntactic patterns should significantly reflect the author’s stylistic choice and thus they should exhibit some kind of peculiar overrepresentation behavior controlled by the author’s purpose. To evaluate the effectiveness of the proposed method, we conducted an experiment on a classic French Corpus. The analyzed results show the effectiveness in extracting interesting syntactic patterns from this type of text.
Based on the current study, we have identified several future research directions such as exploring other statistical measures to assess the interestingness of a given syntactic pattern, and expanding the analysis to include morphosyntactic patterns (form and lemma words). Finally, we intend to experiment with other languages and text sizes using standard corpora employed in the field of computational stylistics at large.
Frontini, F., Boukhaled, M.A. & Ganascia, J., Linguistic Pattern Extraction and
Analysis for Classic French Plays.
Mahlberg, M., 2012. Corpus stylistics and Dickens’s fiction, Routledge.
Mangiapane, S., 2012. Ponctuation et mise en page dans Madame Bovary: les interventions de Flaubert sur le manuscrit du copiste. Flaubert. Revue critique et génétique, (8).
Quiniou, S. et al., 2012. What about sequential data mining techniques to identify linguistic patterns for stylistics? In Computational Linguistics and Intelligent Text Processing. Springer, pp. 166–177.
Ramsay, S., 2011. Reading machines: Toward an algorithmic criticism, University of
Illinois Press.
Schmid, H., 1994. Probabilistic part-of-speech tagging using decision trees. In Proceedings of the international conference on new methods in language processing. pp. 44–49.
Mining Comparative Sentences from Social Media Text
Fabíola S. F. Pereira
Faculty of Computer Science Federal University of Uberlândia (UFU)
Uberlândia, Minas Gerais, Brazil
fabfernandes@comp.ufu.br Abstract. Comparative opinions represent a way of users express their preferences about two or more entities. In this paper we address the problem of comparative sentences mining focused on social medias. We propose a genetic algorithm able to mine comparative sentences from short sentences based on sequential patterns classification. A comparison among classifiers regarding comparative sentences analysis is also presented. Our results indicate better accuracy for the proposed technique against literature baseline approaches, reaching accuracy levels of 73%.
Keywords: opinion mining, comparative sentences, genetic algorithm, social media mining 1 Comparative opinions represent a way of users express their preferences about two or more entities. Mining comparative sentences from texts can be useful in several applications. For instance, a company might be interested in social media rumors of a new product release among consumers. Or, what are the best and worst features of the new product from consumers viewpoint? Nowadays, social medias are great source of this kind of information and mining comparative opinions from them seems to be a very promising direction to unveil valuable knowledge.
Many researches have been done in the field of regular opinion and sentiment
classification [
In [
The main contributions of this paper are: (1) a publicly available dataset crawled from Twitter. We manually labeled 1,500 tweets as comparative or noncomparative; (2) the genetic algorithm GA-CSR to aggregate to the problem of mining comparative sentences; and (3) a set of experiments comparing our approach with state-of-the-art techniques.
This paper is organized as follows: in Section 2 we introduce the problem of mining comparative sentences, highlighting social medias texts. In Section 3 we discuss techniques proposed in related work and present our proposal. In Section 4 the experimental results are showed. Finally, Section 5 concludes the paper. 2
The Problem of Mining Comparative Sentences
In the context of our study, comparative opinions are opinions that express a
relation based on similarities or differences between two or more entities.
According to [
Definition 1 (Comparative Opinion [
Example 1. Let us consider the following comparative sentence: “@stephthelamekid tbh wii u games do have better graphics than ps4 and xbox 1 games”, posted by user Dinotia_4 in 12/06/2014. The comparative opinion extracted is: ({Wii U games}, {PS4 games, XBox One games}, {graphics}, {Wii U games}, Dinotia_4, 12/06/2014)
One challenge on the problem of comparative sentences is that not all
sentences with POS tags JJR, RBR, JJS and RBS (comparative and superlative
POS tags) are comparative. For example, “faster is better.” Moreover, some
expressions are comparative, but just can be identified through context, e.g “PS4
is expensive, but Wii-U is cheap.”
3
To the best of our knowledge, the most representative technique in literature
that addresses the problem of comparative sentences is [
N-grams Classification
The technique of document representation through term vector is the most
common in the sentiment analysis field and can be used as our baseline. In this
approach, each sentence in the corpus is a document, terms are the most
relevant words and we use TF-IDF matrix [
In this work, just unigrams have been considered. We did three pre-processing
steps: (1) stop words removal, (2) stemming and (3) 1000 features extraction
based on information gain index [
According to [
After defined the task of mining class sequential rules, then we deploy the
algorithm to our problem. However a sentence cannot be handle simply from raw
words, as we did on n-grams classification approach (Subsec. 3.1). To find
sequential POS tags patterns in sentences and, then, build an input dataset of
sentences to be classified (supervised learning) as comparative or non-comparative
the following steps are needed:
1. Sentences with pivot keywords. Many words in English language
indicate comparisons, for example beat, exceed, outperform etc. Moreover, those
ending with -est and -er are naturally comparative or superlative adverbs
and adjectives. Thus, a set of comparative keywords is considered. The idea
is to identity sentences with at least one keyword and use the words that are
within the radius of 3 of each keyword in the sentence as a sequence in our
data.
2. Replacing with POS tags. For each sequence of max length of 7 obtained
in previous phase, replace all words with their corresponding POS tags.
3. Labeling sequences. For each sequence, we have to label it as comparative
or non-comparative. This is the same label that originated the sequence.
4. Generating CSR. In this phase we have to mine sequential patterns. The
algorithm PrefixSpan [
Example 2. In order to illustrate steps 1 to 4, let us consider the sentence: “this/DT game/NN is/VBZ significantly/RB more/JJR fun/NN with/IN Kinect/NN than/IN without/IN it/PRP." It has the keyword more and the generated CSR is:
<{NN}{VBZ}{RB}{moreJJR}{NN}{IN}{NN}> ! comparative
In this paper we propose a genetic algorithm for mining comparative sentences.
The idea is to mine class sequential rules (CSR) from [
Each chromosome represents a CSR. Chromosomes have fixed length of 8 genes, where the first 7 are the sequential patterns with itemsets of length 1 (default gene) and the last one is the class with value comparative or noncomparative (class gene). Each default gene is an itemset and can assume POS tags domain values. Moreover, for each default gene we have the additional bit ’1’ or ’0’ representing whether or not it is part of sequential pattern. The example chromosome coding and its meaning is described in Figure 1. In the following we detail GA-CSR features.
Fig. 1: Chromossome coding – Fitness. The rules fitness (F itness) in the population is calculated based on a function containing two terms, namely Specificity (Sp) and Sensitivity (Se), where Sp = T N/(T N + F P ), Se = T P/(T P + F N ) and F itness = Se ⇤ Sp. The variables T P , T N , F P and F N correspond to true positives, true negatives, false positives and false negatives, respectively. – Population creator. The population is randomly generated. – Selection and crossover. Two best chromosomes are selected by applying roulette wheel selection method and two point crossover method is applied over them to generate new children chromosomes. The class gene is not considered. – Mutation. The mutation process changes the value of an attribute to another random value selected from the same domain. It can occurs in any gene type and does not consider the flag bit of each gene. – Insertion and removal operator. Insertion and removal operators control the size of a rule. Insertion operator activates the gene by setting its flag bit and removal operator deactivates a gene by resetting the flag bit with a varying probability Pi and Pr, respectively. – Survivor selection. GA-CSR uses fitness-based selection where individuals are selected from the set composed by parents and offspring. The top Tp fitness individuals are selected, where Tp is the population size.
In the end, we have a set of class sequential rules and just those greater than minimum support and confidence are considered for test and model validation. 4 In this section we report our experiments. We aim to compare best classification accuracies. Section 4.1 describes the datasets used to train and test the models. It also presents our experiments set-up and parameter setting. Finally, we expose our results in terms of success rate of the classifiers in Section 4.2. 4.1
Datasets and Parameterization We tested our algorithms over two datasets: Amazon product reviews and Twitter texts. Our goal is to show how text mining social medias is different because of specific features of text length and language.
The Amazon product review is about mp3 players and was obtained from
[
Our test set is composed by 9 runs for each dataset. For the n-grams approach, we used 4 classifiers: SVM (SVM-Unigram), NB (NB-Unigram), MLP (MLP-Unigram) and RBF (RBF-Unigram). In the CSR approach we also use 4 classifiers: SVM-CSR, NB-CSR, MLP-CSR and RBF-CSR. Finally, we run our proposed genetic algorithm GA-CSR. In Figure 2 we present detailed parameters used for each approach.
1 https://dev.twitter.com/rest/public
DB-Amazon # sentences 1000 1500 # comparative sentences 97 (9.7%) 199 (13.26%)
Texts dates 2003-2007 Dec 2014
Topic mp3 players XBox and PS4 Table 1: Datasets used for tests
Unigrams 10-fold cross-validation stop words, stemm, infogain
1000 MLP-Unigram RBF-Unigram 10-fold cross-validation 3 0.1 0.6
PrefixSpan MLP-RCPS RBF-RCPS (c) Parameters GA-CSR approach
Fig. 2: Parameterization 4.2 The first test set was performed over DB-Amazon dataset (Figure 3). We can observe a poor performance for n-grams approach. As expected, it is a simple baseline that does not take into account elaborated features of our mining problem. Varying classifiers algorithms does not impact on results that reach a maximum accuracy of 68.6% for RBF neural network.
Fig. 3: Experimental results over DB-Amazon
Regarding CSR approach from [
The second test set ran over DB-Twitter (Figure 4). Graphics curves maintained the trend, however the average accuracy decreased around 10%. This can be explained due to the large amount of noise in Twitter texts. Moreover, sentences grammatical errors potentially harm the grammatical pattern approaches.
Fig. 4: Experimental results over DB-Twitter
Conclusion In this paper we addressed the problem of mining comparative sentences. We carried out an experiment using 1,500 short sentences from Twitter.com, equally divided into two domain categories: comparative and non-comparative sentences. The results showed that the higher success rate was obtained with our genetic algorithm approach (73%). As our sample is relatively small, we used crossvalidation (10-fold) to avoid overfitting and increase the accuracy of the success rate of the classifiers.
To ensure reproducibility of our results, in conjunction with the publication of this paper, we have released the full genetic algorithm GA-CSR code and Twitter data in the format used by our algorithm2.
As future work, once mined comparative sentences, our focus will be on mining user preferences. We consider that comparative sentences are good source of users opinions, enabling the development of reasoning user preferences models from social data.
References