3.1 Phase 1: Mining sequential patterns associated to seed patterns

Phase 1 objective is to extract sequential patterns (SPs) corresponding to a given set of seed patterns such that extracted patterns improve precision of the seed patterns while keeping a comparable (or the same) recall. This is done, first, by applying the mining process for extracting SPs from a set of training sentences expressing hypernym relations, being these sentences matching any seed pattern and extracting any HH-pair; second, by automatically selecting the SPs showing better precision than precision of seed patterns and a comparable (or the same) recall.

3.2 Phase 2: Discovering new sequential patterns

Phase 2 objective is to discover new SPs (additional to patterns extracted in phase 1) for the purpose of increasing recall under the constraint of keeping precision stable (i.e. close to the precision of SPs of phase1). These new patterns are discovered by applying the mining process for extract SPs from sentences expressing hypernym relations but not matching with patterns extracted in phase 1. Discovered patterns are then further selected for keeping precision at least equal to precision of patterns extracted in phase 1.

3.3 Phase 3: Anti-hypernym sequential patterns

Phase 3 objective is to extract patterns enabling to identify pairs wrongly extracted as HH-pairs by SPs resulting from phase 1 or phase 2. Patterns extracted in phase 3 are often qualified as anti-patterns, thus referred here as anti-hypernym sequential patterns. Using both patterns and anti-patterns in combination contributes to increase precision while keeping recall unvaried. Anti-patterns are extracted by applying the mining process for extracting SPs from sentences not expressing hypermym relations and matching with patterns found in phase 1 and phase 2. Discovered patterns are then further selected among the ones showing lowest precision (i.e. selected patterns are likely to extract non-hypernym pairs).

3.4 Sequential hypernym patterns learning workflow

The steps required to extract sequential patterns are common to the 3 phases. This is an important aspect of the proposed approach. Figure 1 shows the generic 5 steps workflow: (i) Corpus Labeling, (ii) Sequences Preparation, (iii) SPM, (iv) Relevant Sequential Pattern Selection and (v) Evaluation. Some steps are executed only once (the ones above the dotted line in Figure 1) and other generic steps (the ones below the dotted line in Figure 1) repeated for each phase and requiring to be configured in terms of inputs and constraint parameter values, according to the objective of each specific phase.

Figure 1.

The workflow of sequential patterns learning.

3.4.1 Corpus labeling step and evaluation Step

Usually, hypernym patterns performance is evaluated in terms of precision and recall based on extracted pairs and expected HH-pairs found in a dataset. However, for patterns, we consider that this evaluation is partially inaccurate because (1) on the one hand, (right) patterns can match sentences indicating hypernym relations and extract HH-pairs which are not among expected HH-pairs, (2) on the other hand, (wrong/imprecise) patterns can match sentences that do not express hypernym relations but extract expected HH-pairs. The first point can be traced back to misalignment between the corpus and the dataset, which can quite often be observed. As a consequence and for limiting as much as possible any human intervention (because of the huge number of sentences to be checked out), we suggest to proceed in two ways: first, virtually completing the dataset by using HH-pairs suggested by WordNet (Fellbaum Reference Fellbaum1998) (but other resources can be used); second, manually classifying the remaining extracted pairs covered neither by the dataset nor WordNet. With these ways to proceed, the evaluation does not require heavy human interventions.

For taking into account the second point, we label each sentence in a corpus C as positive or negative. A positive sentence expresses at least one hypernym relation according to a given set of HH-pairs, a negative sentence is not a positive one. The set of positive sentences (PS) and the set of negative sentences (NS) in C are defined as follows:

(1) \begin{equation}PS=\{ s\ |\ s\ \in\ C, \ \exists\ (x,y) \in\ HH{-}pairs\ s\ expresses\ hypernym\ relation\ between\ x\ and\ y\}\end{equation}

(2) \begin{equation}NS = C-PS\end{equation}

where ‘s expresses hypernym relation between x and y’ means that sentence s meaning expresses one hypernym relation between two terms x and y occurring in s.

Then, to accurately assess the quality of a set of patterns P, we propose to evaluate Matching Precision (M-Precision) and Matching Recall (M-Recall), more adapted than usual precision and recall, defined as:

(3) \begin{equation} M{-}Precision(P,C) = \frac{|TM|}{|TM| + |FM|}\end{equation}

(4) \begin{equation} M{-}Recall(P,C) = \frac{|TM|}{|TM| + |FNM|} \end{equation}

where TM (True Matched sentences), FM (False Matched sentences), and FNM (False Not Matched sentences) are computed as follows:

(5) \begin{align} TM & = \{ s\ |\ s\ \in\ PS,\ \exists\ p\ \in\ P,\ p\ matches\ s\ extracts\ (x, y), (x, y)\in\ HH{-}pairs\}\ \cup\nonumber\\ & \{ s\ |\ s\ \in\ NS,\ \exists\ p\ \in\ P,\ p\ matches\ s\ extracts\ (x, y),\ (x, y)\ is\ validated\ manually\nonumber\\& \quad as\ HH-pair,\ s\ expresses\ hypernym\ relation\ between\ x\ and\ y\} \end{align}

(6) \begin{equation} FM = \{ s\ |\ s\ \in\ C,\ \exists\ p\ \in\ P,\ p\ matches\ s\ s\ \notin\ TM\} \end{equation}

(7) \begin{equation}FNM = \{ s\ |\ s\ \in\ PS,\ \forall\ p\ \in\ P,\neg\ p\ matches \ s\}\end{equation}

Where

1. • $p\ matches\ s\ \&\ extracts\ (x, y)$ means that the pattern p matches sentence s and, at the same time, extracts pair (x, y),

2. • $p\ matches\ s$ is equivalent to $\exists\ (x,y)\ p\ matches\ s\ \&\ extracts\ (x, y)$ , and

3. • $(x, y)\ is\ validated\ manually\ as\ HH-pair$ means that an human expert has validated pair (x, y) as one hypernym relation.

However, using M-Precision, M-Recall requires to know for every sentence in a corpus which hypernym relations are expressed in the sentence itself. This cannot be expected for any corpus; thus, we have designed a corpus labeling heuristics for approximating as better as possible the required information, as explained hereinafter.

Corpus labeling objective is to label each sentence in corpus C as positive or negative according to Definitions 1 and 2 above. Labeling is done once, in the beginning of workflow (Figure 1), and makes possible to compute TM, FM, and FNM when needed. For the purpose of labeling, we have defined some heuristics: indeed, for labeling a sentence as positive it is not enough to check if the sentence comprises at least one HH-pair. For instance, sentence ‘Country music began a slow rise in American main pop charts’ comprises HH-pair (country music, pop), but it does not express one hypernym relation between those terms. Therefore, after having analyzed several counterexamples in available corpora (see Section 4.1), we have defined 5 heuristics to select sentences comprising both HH-pairs and potentially expressing hypernymy relations between those pairs:

1. (i) at least one HH-pair (i.e. found in the given dataset) occurs in the sentence;

2. (ii) the hyponym and the hypernym occur in the sentence as noun phrases (NP). Generally, the relationships expressed in a sentence are between noun phrases (NP). For instance, in sentence ‘Country music began a slow rise in American main pop charts’, hypernym ‘pop’ occurs as a ‘modifier’ and not as a noun phrase;

3. (iii) the distance between the hyponym and the hypernym in a sentence is 10 words maximum (this is similar to what it is suggested in the reviewed approaches for deciding if a dependency path should be a feature). For instance, sentence ‘Art rock aspires to elevate rock from teen entertainment to an artistic statement, opting for a more experimental and conceptual outlook on music’ is likely to do not express hypernymy for pair (rock, music) because the distance between ‘rock’ and ‘music’ is more than 10 words;

4. (iv) hyponym and hypernym should not be directly related by ‘and’ or ‘or’ conjunction. For instance, sentence ‘The contradictions may stem from different definitions of the terms ragtime and jazz’ is likely to do not express hypernymy for pair (ragtime, jazz) and (jazz, ragtime) because terms are related by ‘and’;

5. (v) hyponym and hypernym do not occur in distinct brackets in the sentence. For instance, in sentence ‘By the 7th century, the koto (a zither) and the biwa (a short-necked lute) had been introduced into Japan from China’, terms belonging to HH-pair (zither, short-necked lute) occur in distinct brackets, so that the sentence is likely to do not express hypernymy between those terms.

Once labeling is performed, the set of positive sentences belonging to the labeled corpus is randomly partitioned: 60% of positive sentences constitutes the learning corpus while 40% of remaining positive sentences constitutes the testing corpus. Learning corpus is then completed by adding a number of negative sentences equal to the number of positive sentences already contained in it. Testing corpus is also completed as done for the learning corpus. Evaluation step is also performed once for a given corpus, whenever all 3 phases have been completed. The objective is to evaluate the final achieved M-precision, M-recall, and f-score (i.e. the harmonic mean of M-precision and M-recall) for whole set of extracted patterns, possibly in combination with anti-patterns. These values are then compared to the metrics values calculated for the seed patterns (non-regression evaluation), original HPs, and ExtHPs; all metrics are evaluated by using the testing corpus as well.

3.5 Sequential representation of sentences

The sequence representation of a sentence is one important aspect of the proposed approach. Indeed, pattern representation may or may not enable to extract relevant relations. For instance, a simple lexico-syntactic pattern representation cannot allow representing the relationship between ‘musical instrument’ and ‘guitar’ in the sentence ‘I like musical instruments invented in Spain, such as guitar’ because of ‘invented in Spain’. However, by using deep grammatical dependencies, it is possible to found that ‘musical instruments’ is related to ‘guitar’. Nevertheless, as reported the related work section, grammatical dependencies can be used in several ways both for representing and discovering patterns, leading to better or worse precision and recall.

Before presenting in detail the proposed representation of patterns based on deep grammatical dependencies, we list and explain below the main differences and similarities between the proposed representation of sequences and the ones described in (Bechet et al. Reference Bechet, Cellier, Charnois and Cremilleux2012; Nguyen et al. Reference Nguyen, Matsuo and Ishizuka2007) works:

1. • Sequence coverage. In Nguyen et al. (Reference Nguyen, Matsuo and Ishizuka2007), the sequence only represents the shortest dependency path in a sentence connecting pairs of terms. In Bechet et al. (Reference Bechet, Cellier, Charnois and Cremilleux2012), all sentence words are represented in the sequence. We suggest covering all sentence words as in Bechet et al. (Reference Bechet, Cellier, Charnois and Cremilleux2012) because we assume that the shortest dependency paths may not comprise all information that characterizes hypernym patterns.

2. • Sequence elements. In Nguyen et al. (Reference Nguyen, Matsuo and Ishizuka2007), one sequence element is an item representing either a word or a dependency relation linking two words: if the word is a noun, ‘NN’ replaces the word itself. In Bechet et al. (Reference Bechet, Cellier, Charnois and Cremilleux2012), the sequence element is an itemset (a set of items) including the word itself, its lemma, and its POS tag. We also suggest that a sequence element is an itemset, precisely representing any dependency relation with one another element in the sequence (as better explained in the remainder).

3. • Taking Noun Phrases into account. Rather than referring to nouns (Nguyen et al. Reference Nguyen, Matsuo and Ishizuka2007; Bechet et al. Reference Bechet, Cellier, Charnois and Cremilleux2012), we refer to Noun Phrases (NPs) for sentence representation as a sequence. Thus, the extracted sequential patterns enable to extract relations between NPs, which is more adapted because a sentence often conveys a hypernym relation between NPs, and not between single nouns.

4. • Links between sentence elements. In Nguyen et al. (Reference Nguyen, Matsuo and Ishizuka2007), sentence elements are linked by the grammatical relation linking them together in the dependency tree. In Bechet et al. (Reference Bechet, Cellier, Charnois and Cremilleux2012), sentence elements are linked by their order of occurrence in the sentence. We suggest that sentence elements need to be linked by both their order of occurrence in the sentence and the grammatical relation linking them together in the dependency tree. The dependency relation of each element is part of the itemset (more details are provided in the remainder).

Proposed representation. Let $S = <e_1, e_2, \cdots, e_n>$ denote the sequence of elements representing a sentence. As also said above, an element of a sentence represents either a NP or any other word that does not belong to any NP. Let $I_{e_j} = <i_{(j,1)}, i_{(j,2)}, \cdots, i_{(j,m)}>$ a set of items (the itemset) representing all information about the element $e_j$ .

For one element representing a NP, most information refers to the NP head wordFootnote ² .The headword is the most important word in the NP, conveying the main meaning of the NP. A NP is composed of several words that usually are either nouns or modifiers, but only one of these nouns corresponds to the head word (root).

The nature of information associated to each element can be lexical, syntactic, and dependency. Information used in the proposed representation is:

1. • Element label: the label of the element. If the element is a NP, the label is the concatenation of the words (separated by ‘ $\_$ ’) composing the NP.

2. • NP: in case of a NP element, ‘NP’ item is added.

3. • Lemma: the lemma (or the head word if the element represents a NP).

4. • POS tag: the POS tag (possibly the POS tag of the head word if the element represents a NP).

5. • Relation and its direction: the grammatical dependency in which the element is involved (possibly the grammatical dependency in which the head word is involved if the element represents a NP) concatenated with the dependency direction. A grammatical dependency is a binary relation between two words: the governor and the dependent (the element represents the dependent in the relation). The direction is right ( $\rightarrow$ ) if the location of the governor word is after the dependent in the sentence; otherwise, it is left ( $\leftarrow$ ).

6. • Governor word: the word (it can be a head word of a NP) to which the element is grammatically related.

For the purpose of learning sequential hypernym patterns, hyponym and hypernym should also be explicitly indicated in the sequence. Thus, two items, ‘hypo’ and ‘hyper’, are added. Additionally, for the purpose of representing the dependency path connecting the hyponym to the hypernym, the governor word item in a sequence element can be replaced by the generic ‘hypo_gov’ or ‘hyper_gov’.

Let’s consider the following sentence ‘Piano is a musical instrument invented in Italy’. Figure 2 shows the representation of the sentence as a sequence according to the proposed representation and both (Nguyen et al. Reference Nguyen, Matsuo and Ishizuka2007; Bechet et al. Reference Bechet, Cellier, Charnois and Cremilleux2012) representations (‘_label’, ‘_lemma’, and ‘_gov’ suffixes are used in the sequence representation for making easy to recognize items as corresponding to Element label, Lemma, and Governor Word). Looking to the shown representations of the sentence above, it is clear that the shortest path dependency is not enough for expressing all needed information (e.g. the tense is not necessarily part of the path linking hypernym and hyponym so that the relationship between terms is not explicit). It is also clear that a sequence based on POS-tags is not enough because hypernym and hyponym are not explicitly related by dependencies (and hypernym and hyponym may be unrelated in the sentence).

Figure 2.

Examples of sequence representation of a sentence.

4.1 Corpora and datasets

For conducting the experiments, we use three different corpora and two datasets. Two of three corpora are provided for the hypernym discovery task at SemEval2018 (Camacho-Collados et al. Reference Camacho-Collados, Delli Bovi, Espinosa-Anke, Oramas, Pasini, Santus, Shwartz, Navigli and Saggion2018): a domain-specific corpus (Music) and a general-purpose corpus (English-1). The third corpus is also a general-purpose corpus (English-2), used by Shwartz et al. (Reference Shwartz, Santus and Schlechtweg2017), which is a concatenation of the following two corpora: a corpus constructed by crawling the.uk domain (ukWaC), and a 2009 dump of the English Wikipedia (WaCkypedia EN). The two datasets comprise the known HH-pairs, and are more or less specialized: Music is a dataset consisting of specific hypernym relations for the music domain (used with Music corpus), and English is a dataset consisting of general hypernym relations for the English language (used with both English-1 and English-2 corpora). Both datasets have been provided for the task of hypernym discovery at SemEval2018.

As described in Section 3.4.1, starting from a given corpus and a dataset of known HH-pairs, labeling is performed once for each corpus. For all used corpora, Table 1 shows the results of the corpus labeling step using the heuristics: numbers of sentences, corresponding numbers of positive and negative sentences, and numbers of learning and testing sentences.

Table 1

Corpus labeling results expressed in number of sentences

4.2 Setting up workflow configuration

Each learning labeled corpus is used to learn sequential patterns by following the proposed 3-phase approach as shown in Figure 3. In previous work (Aldine et al. Reference Aldine, Harzallah, Giuseppe, BÉchet and Faour2018), DHPs have been manually designed from HPs and it has been shown that DHPs lead to better performance than HPs and ExtHPs. For this reason, we use DHPs as seed patterns instead of HPs or ExtHPs. It should be noted that each manually designed DHP corresponds to one and only one HP: in the remainder, we therefore use the HP simple syntax to refer to the corresponding DHP because DHPs are syntactically complex and the interested reader can refer to Aldine et al. (Reference Aldine, Harzallah, Giuseppe, BÉchet and Faour2018).

Figure 3.

Sequential patterns learning using the 3-phase approach.

Starting from DHPs, in phase 1, learning process steps (Figure 1) are repeated for each DHP, leading to one extracted set of sequential Hearst patterns for each DHP (i.e. a $SHPs_i$ for a $DHP_i$ , $1\leq i\leq 6$ ). SHPs $=\bigcup_{i=1}^{6}{SHPs_{i}}$ is then the union of all extracted sets of sequential patterns for the six DHPs. It should be noted that with this strategy, the usage of CloSPEC can be parallelized, limiting the risk of memory fault due to the mining complexity.

In phase 2, learning process steps are performed once to extract new sequential patterns from FNM sentences (FNM sentences are found according to definition 7 taking into account patterns SHPs and the learning labeled corpus). SHyPs $= \{SHyPs_{j}, 1\leq j\leq m\}$ denotes the set of extracted sequential patterns in this phase.

In phase 3, learning process steps are repeated for each $SHPs_i$ and for each $SHyPs_{j}$ , leading to two sets of sequential anti-hypernym patterns $SHPs^{-}$ and $SHyPs^{-}$ respectively. $SHPs^{-} = \bigcup_{i=1}^{M}{SHPs_{i}^{-}}$ is the union of all extracted sets of sequential anti-hypernym patterns for each sequential pattern extracted in phase 1. $SHyPs^{-} = \bigcup_{i=1}^{K}{SHyP_{i}^{-}}$ is the union of all extracted sets of sequential anti-hypernym patterns for each sequential pattern extracted in phase 2. Even in this case, the strategy enables to parallelize the CloSPEC usage.

As described in Section 3.4, performing the generic workflow requires to set up some configurations. Specifically, the values of constraint parameters used for sequential patterns learning and thresholds for selection step should be set. The values of parameters and threshold shown in Figure 3 are the best-fit values after having performed a tuning process. Tuning values are given below. Note that some values have been fixed for all phases.

1. • Support: tuned using the following relatively low values {20%, 10%, 5%, 2%}. Indeed, some interesting patterns can be relatively infrequent.

2. • Minimum gap: fixed to 0. Positive values do not allow to find patterns.

3. • Maximum gap: tuned by using the following values {0, 3, 5, 10}. As already explained, we found that it is needed to set a maximum gap strictly positive ( $>$ 0). We also found that using greater values than 3 has no advantage since no new patterns are discovered while, at the same time, falling in high mining complexity.

4. • Minimum itemset number Nb: fixed to 2.Patterns must have at least 2 elements i.e. one hypernym and one hyponym.

5. • Maximum itemset number Nb: tuned by using the following values {7, 8, 9, 10}. We found that using 7 is enough to learn hypernym patterns because with greater values extracted patterns are mostly wrong while, at the same time, falling in high mining complexity.

6. • PT (M-Precision Threshold): set according to the objective of each phase.

   1. − Phase 1 objective is to find sequential patterns (SHPs) more precise than DHPs. For this purpose, precision threshold is set to $0.5$ corresponding to the lowest bound of M-precision of DHPs evaluated on VS1 (by definition VS1 comprises only 30% of TM and the equal number of randomly selected FM sentences; both TM and FM are computed with DHPs and the learning labeled corpus, written as VS1=30%TM+=FM). Additional details can be found in Section 4.2.1.

   2. − Phase 2 objective is to find patterns (SHPyPs) other than SHPs, thus improving recall, and showing the same or better precision than SHPs. For this purpose, precision threshold is set to the value of M-Precision of SHPs computed in the validation step.

   3. − Phase 3 objective is to find anti-patterns for patterns extracted in phases 1 and 2. For this purpose, precision threshold is set to a very low value ( $0.1$ ) and patterns extracted should have even lower precision, because these patterns should be representative counterexamples of hypernym relations, as better explained in Section 4.4.

7. • RT (M-Recall Threshold): is only used in phase 1 where the learned patterns are constrained to do not reduce M-recall of DHPs. Thus, recall threshold is set to 1 because, by definition of VS1 (which does not comprise any FNM sentence with respect to DHPs), M-recall of DHPs on VS1 is necessarily equal to 1.

4.2.1 Phase 1: SHPs learning results

The sequence preparation step in phase 1 computes TM, FM and FNM by using DHPs and the learning labeled corpus (comprising both positive and negative sentences). For each DHP, a set of training sequences (TS) is constituted with 70% of TM sentences (written as TS=70%TM); a corresponding set of validation sequences (VS) is also constituted with the remaining 30% of TM sentences and the same number of FM sentences. VS1 and TS1 are the union of all computed VS and TS respectively (detailed results of this step are provided in Appendix A).

Table 2 shows the number of frequent closed raw sequential patterns extracted by applying CloSPEC on each TS (FCSPs) and, for each selection criterion, the number of selected patterns. The results show the high selectivity of the first criterion (i.e. existence of one hypernym-hyponym dependency path), specifically targeting precision. This selectivity is however partially balanced by keeping highest the resulting recall. We also report in the table the case of High Precision Sequential Hearst’s patterns (HiPre-SHPs) selected by setting $PT=0.8$ and without setting any RT. This specific experiment shows how to manage thresholds and what can be the impact—as a consequence, the number of patterns selected is dramatically reduced because PT is very high and recall may freely decrease.

Table 2

Phase 1: Values for FCSPs, selected patterns for each selection criterion

Table 3 shows representative examples of SHPs learned from the Music corpus alongside additional details. For each SHP, the table points the corresponding DHP, one sample of TM sentence with the extracted HH-pair, one sample of FM sentence matching the corresponding DHP while not matching with the SHP, and the explanation/interpretation of the SHP. The M-precision evaluated on the relevant VS is also shown.

Table 3

Phase 1: Representative samples of learned SHPs

4.3 Phase 2: SHyPs learning results

The sequence preparation in phase 2 computes TM, FM and FNM partitions with SHPs, resulting from phase 1, and the learning labeled corpus. A set of training sequences (TS2) is constituted as 70% of FNM sentences (written as TS2=70%FNM); a set of validation sequences (VS2) is also constituted with 30% of the remaining FNM sentences and the same number of FM sentences (written as VS2=30%FNM+=FM). Detailed results of this step are shown in Appendix B.

Table 4 shows the size of TS2, the number of raw patterns extracted by CloSPEC on TS2 (FCSPs), and, for each selection criterion, the number of selected patterns; as for phase 1, the high selectivity of the first criterion should be noted.

Table 4

Phase 2 : Values for TS2, FCSPs, and selected patterns for each selection criterion

Table 5 shows all the (five) new learned SHyPs from the three corpora and samples of TM sentences. To the best of our knowledge, 2 of them ( $SHyP_{ranging}$ and $SHyP_{who}$ , the first and third SHyP in the table) have not been identified in the literature. New sequential patterns refining the Hearst’s pattern ‘NP and/or other NP’ have also been discovered. These new patterns do not have any counterpart in both DHPs and SHPs—indeed, dependency paths connecting hyponym to hypernym in the newly discovered patterns are different from paths occurring in DHPs and SHPs. The limited number of new patterns can be explained by setting their M-precision to be equal or greater than M-precision of SHPs.

Table 5

Phase 2: All learned SHyPs from the three corpora

4.4 Phase 3: SHPs $^-$ learning results

The objective of phase 3 is to discover anti-patterns for patterns discovered in phases 1 and 2. Hereinafter, we first focus on anti-patterns for patterns discovered in phase 1 (i.e. SHPs). The sequence preparation step provides training and validation sequence sets per each set of SHPs patterns corresponding to one DHP (remeber that for one DHP several SHPs have been discovered in phase 1). Accordingly, for each set of SHPs patterns corresponding to one DHP, each TS is constituted with 70% of FM sentences (written as TS3=70%FM), being FM sentences computed with that set of SHPs and the training labeled corpus. The same is done for defining validation sets: each validation set VS is constituted with 30% of remaining FM sentences and the equal number of TM sentences (written as VS=30%FM+=TM), being TM sentences computed with that set of SHPs and the training labeled corpus. Discovering patterns showing a very low M-precision corresponds to patterns mostly matching with FM sentences (found in TS and VS). FM sentences are by definition sentences (positive or negative) matching with a pattern such that: a pair is extracted but it cannot be found in known HH-pairs or in WordNet, or human experts do not validate the sentences as expressing hypernymy stated by the pair. As a consequence, these sentences are likely to provide counterexamples of hypernymy.

Table 6 shows the number of extracted raw patterns from each TS (except the ones with few elements) and the number of selected patterns for each selection criterion.

Table 6

Phase 3: Values for FCSPs, and selected patterns for each selection criterion

Table 7 shows representative samples of learned SHPs $^-$ . Each SHP $^-$ is provided with one sample of FM sentence alongside with the false HH-pair extracted from the sentence, and an explanation. We also show the M-precision of each SHP $^-$ calculated on VS. The very low precision of these patterns allows to filter the FM sentences by SHPs but also reduces slightly the recall by filtering some TM sentences matching SHPs. For instance, the second learned SHP $^-$ in Table 7 filters sentences like ‘NP is in NP’ (e.g. ‘the vehicle is in motion’) and ‘NP is under NP’ (e.g. ‘the situation is under control’). However, the same pattern also filters sentences like ‘NP is among NP’ (e.g. ‘the brain is among the organs that $\cdots$ ’), which both express hypernymy and pattern extracts a right pair of hypernym-hyponym.

Table 7

Phase 3: Representative samples of learned SHPs $^-$

Table 8

Evaluation results on Music, English-1, and English-2 corpora

4.5 Phase 3: SHyPs $^-$ learning results

In this section, we shortly present the anti-patterns SHyPs $^-$ for patterns discovered in phase 2 (SHyPs). In Appendix C, Table 17 shows values for TM, FM, TS, VS computed with each SHyP and on each training labeled corpusFootnote ³ . It should be noted that only $SHyP_{like}$ , learned from Music corpus, has a relevant number of training sequences ( $54>=20$ ). Therefore, it is the only pattern for which anti-patterns may be found. Starting from the associated training sequence set, 486 818 raw anti-patterns have been extracted and only patterns with M-precision lower than $0.1$ are kept. Unfortunately, this criterion is highly selective and no pattern has been found (SHyPs $^-$ is void).

4.6 Evaluation step: Quantitative results

Experiments presented in previous sections, are performed in the context the evaluation step (Figure 1) with the main objective to validate the 3-phase approach. For that purpose, precision and recall of available patterns HPs, ExtHPs, and DHPs, computed with each testing label corpus, are compared to precision and recall of discovered patterns, computed with the same corpus. Table 8 shows those M-precision, M-recall, and f-score for respectively Music, English-1, and English-2 testing corpora. The table also shows M-precision and M-recall stated on the testing corpora for the learned patterns resulting from each phase. This is indeed useful for understanding the contribution of each phase to the improvement of precision and recall.

The best f-score for the 3 corpora and for all patterns compared in Table 8, is achieved by the combination of all learned patterns and anti-patterns. On the one side, this confirms that selection criterion used for automatically selecting patterns are effective because performances are better than seed patterns. Indeed, for the 3 corpora, the table shows that, there is no regression of M-Precision and M-Recall (only for English 2, M-Recall is slightly under the M-Recall shown by DHPs) and detected improvements of M-Recall and M-Precision are significant. On the other side, the interest of the approach over the manual design of patterns is also confirmed. The approach can then be practically used, starting from other corpora for getting additional patterns in a systematic way. It can also be noted that if M-precision threshold used in phase 1 is set very high (HiPre-SHPs), M-recall dramatically decreases. This fact suggests that for discovering patterns, any M-precision threshold used in phase 1 should be set only slightly greater than $0.5$ .

Concerning the contribution of each phase, Table 8 shows that the best results are anyway got whenever the 3 phases are completed (last column of the table). Specifically, phase 2 is really needed to guarantee a much better recall and much better f-score. However, phase 3 only (column header SHPs+SHPs $^-$ ) is required to guarantee as much as possible a good M-Precision of discovered patterns (only slightly reduced by patterns discovered in phase 2) when compared to available patterns (HPs and ExtHPs). For better understanding of M-Precision/M-Recall variations, a qualitative analysis is presented in the next section.

4.7 Evaluation step: Qualitative analysis of learned patterns

In this section, a qualitative analysis for explaining quantitative results presented in the previous section, is developed. The first analysis is about DHPs (i.e. seed patterns) and learned patterns. We have inspected sentences both classified as FM with DHPs (i.e. sentences matching with any DHP but extracting a wrong HH-pair) and, at the same time, not matching with any SHPs. These are 75 sentences out of 653 of FM sentences with respect to DHPs. One example of these 75 sentences is: ‘Some prominent Swedish bands spawned during this second wave, such as Marduk, Nifelheim and Dark Funeral’. This sentence does not match any SHPs because in all SHPs the headword of the hypernym has to be plural while ‘wave’ in ‘second wave’ is singular. However, constraining hypernym requiring headword to be plural in patterns type ‘NP such as NP’, is not necessarily interesting in all situations. For instance, for sentence “So before a band such as Tower of Power would reject the style …’, SHPs do not match (because ‘band’ is singular), but a HH-pair is rightly extracted by using DHPs. This situation provides a partial explanation for the slight reduction in recall when moving from DHPs to SHPs. Once again, this situation explains why completing all phases is needed for achieving better performances. The usage of SHPs $^-$ shows the important impact of these patterns on M-precision when moving from DHPs. These patterns have the greatest impact on FM sentences computed with SHPs. Out of 621 sentences found in FM with respect to SHPs, 75 sentences match to SHPs $^-$ . An example of such sentences is: ‘their music is rock, pop, and alternative’ where the occurrence of possessive pronoun ‘their’ leads the sentence to match the first SHP $^-$ in Table 7. In this case, the anti-pattern is able to correct the absence of article ‘a’, usually part of ‘is-a’ patterns. However, anti-patterns cut some pairs extracted by SHPs, so that the recall naturally decreases. To understand the slight reduction in M-recall caused by SHPs $^-$ , we have analyzed TM sentences computed with SHPs and also matching SHPs $^-$ . We have found only 5 of such sentences out of 557 TM sentences, which explains the limited impact on M-recall. An example of such sentences is: ‘Berry was among the first musicians to be inducted into the rock and roll hall of fame on its opening in 1986’ where the occurrence of ‘among’ and the associated grammatical relation ‘case $\rightarrow{}$ ’, leads the sentence to match the second SHP $^-$ in Table 7. Moving from DHPs and adding SHyPs, Table 8 shows a considerable M-recall improvement. To better understand this quantitative result, we have compared TM and FM sentences computed with SHyPs and TM and FM sentences computed with SHPs. TM computed with SHyPs comprises 111 additional sentences. An example of such additional sentences is: ‘they fuse together sounds from different genres like metal and reggae’ — HH-pair(metal, genres) and HH-pair(reggae, genres) are extracted. FM computed with SHyPs comprises 105 additional sentences. An example of such additional sentences is: ‘Her voice is an instrument all it’s own, slicing through the air like a weapon sometimes’ — wrong HH-pair(weapon, air) is extracted. Therefore, because moving to SHyPs results in comparable TM and FM increments, M-precision remains stable. However, the additional 111 sentences in TM, are sentences removed from FNM computed with SHPs. Therefore, M-recall is dramatically improved. Phase 2 is therefore important to find several additional pairs even though several useful sentences remain unmatched.

4.8 Evaluation step: Analysis of learned patterns generality

As said in the Introduction, patterns are interesting because they can be interpreted and explained. For this raison, it can be possible to assess to what extent a pattern can be used across distinct domains. In this section, we are going to analyze ‘pattern generality’. We define ‘pattern generality’ as the pattern ability to extract (right) HH-pairs across distinct corpora. Table 9 shows specific and common patterns (SHPs, SHyPs, and SHPs $^-$ ) learnt from each of the three corpora. For instance, 52 patterns have been learnt from the Music corpus and additional 5 have been learnt from both Music and English-1 corpora. The two columns headed ‘Total common’ and ‘Total distinct’ provide the total numbers of patterns found by using any of the 3 corpora and found by using only some of these corpora. It should be noted that, globally, very few patterns can be found by using all corpora and patterns are often specific to the corpus. Figure 4 shows for each corpus, the f-score across the three corpora got with the related learnt patterns. The f-score of DHPs is also shown. As it can be seen, the results confirm that all patterns learnt by using one corpus can be used for any other corpus without any significant negative impact on the f-score.

Table 9

Replicability of the learned sequential patterns

Figure 4.

Performance of the learned sequential patterns on the three corpora.

The results also highlight the advantage of the learnt sequential patterns from English-1 corpus over patterns learnt with the other two corpora. By conducting a deeper analysis, we have observed that there are 2 additional SHyPs patterns learnt from English-1 corpus compared to SHyPs patterns learnt form English-2 corpus. This fact explains why M-Recall (and f-score) is, for English-2 corpus, greater when using SHyPs patterns learnt with English-1 corpus. However, the situation is not the same for Music corpus. This is because English-1 and English 2 are general-purpose corpora while Music corpus is more specialized. So that, Music-corpus needs adapted patterns for raising M-recall (and f-score too).

5.1 Comparing patterns to unsupervised distributional approaches

Four measures typically used to evaluate unsupervised approaches are considered here: one similarity measure (Cosine), two inclusion measures (ClarkeDE and invCL), and one informativeness measure (SLQS). According to results presented in Shwartz et al. (Reference Shwartz, Santus and Schlechtweg2017), distributional semantic spaces built using dependency-based contexts are semantically richer than those using window-based contexts; moreover, one weighting feature over another one has no impact. Thus, we first build a distributional semantic space for each corpus using dependency-based contexts and occurrence frequency as feature weight. Then, we use the measures and distributional semantic spaces to compute a score for each pair in a dataset. Finally, pairs are ranked based on their score and the average precision is computed (Zhang & Zhang Reference Zhang and Zhang2009).

For meaningful comparison with unsupervised distributional baselines, there is the need to compute the average precision for patterns too. For this purpose, patterns are first applied to extract HH-pairs from the three corpora. For each extracted pair (x, y), taking into account the extraction frequency of such a pair, a score is computed as follow:

(8) \begin{equation} score(x,y) = \frac{w(x, y)}{max(\{w(x_{i}, y_{i})\}_{i=1}^{n})}\end{equation}

where w(x, y) counts how often the pair is extracted by using all patterns (the frequency) and n is the number of distinct pairs extracted by the patterns. Then, the average precision is computed.

Table 11 shows the average precision for learnt patterns, HPs, DHPs, ExtHPs, computed with the four measures mentioned above. Globally, the results confirm that any set of patterns outperforms any unsupervised distributional baselines. However, the best results are achieved by the full set of learnt patterns (SHPs + SHP $^-$ + SHyPs). Nevertheless, unsupervised approaches based on inclusion measures (ClarkeDE and invCL) show better results on Weeds dataset. As stated by Shwartz et al. (Reference Shwartz, Santus and Schlechtweg2017), the reason is that Weeds dataset comprises numerous specific hypernyms for hyponyms, a situation specifically well handled by inclusion measures.

Table 11

Average precision for comparing learnt patterns to both existing patterns and unsupervised methods on the base the four datasets and the three corpora

Table 12

Performance of pattern based and embedding classifiers for hypernym detection with the four datasets and the three corpora

5.2 Comparing patterns to supervised distributional baselines

To compare patterns and supervised distributional approaches, patterns cannot be used as such because patterns cannot be directly used for hypernym detection. Therefore, we have specifically implemented one supervised baseline enabling to detect hypernyms, based on learnt patterns as features. Additionally, for better showing the interest of learnt patterns, we have also implemented an additional supervised baseline using the shortest dependency paths as features, as proposed in (Snow et al. Reference Snow, Jurafsky and Ng2005). All the classification results (precision, recall, and f-score) become therefore comparable. Details of the implemented baselines are given hereinafter.

Patterns as features. A similar method of Snow approach (Snow et al. Reference Snow, Jurafsky and Ng2005) has been implemented to train a hypernym classifier. But rather than using the shortest dependency paths as features, we use all patterns extracted from the 3 phases.

Dependency paths as features. We have re-implemented the approach described in (Snow et al. Reference Snow, Jurafsky and Ng2005) to train a classifier model. Accordingly, we first extract all shortest dependency paths connecting dataset noun pairs in a corpus; we consider only dependency paths that occur at least 5 times between noun pairs; we extend paths with satellite links to cover patterns like ‘such NP as NP’. These paths are then used as features to train the classifier.

Embedding. We have implemented a distributional supervised baseline that relies on word embedding to represent the feature vector between a pair of nouns by concatenating their word embedding vector (Baroni et al. Reference Baroni, Bernardi, Do and Chieh Shan2012). For this purpose, we train 3 word embedding models for each corpus using Word2Vec Footnote ⁴ with CBOW and dimension equal to 300.

All classifiers are then trained and evaluated by performing 10-fold cross-validation on each dataset using SVM with RBF kernel. Table 12 shows the average precision, recall, and f-score across all folds for the three approaches listed above, the three corpora and the four datasets. The results show that using patterns as features outperforms dependency paths as features. However, the best results are mostly achieved by the classifier based on word embedding even if precision is sometimes comparable.

As stated in the literature review, various works (Mirkin et al. Reference Mirkin, Dagan and Geffet2006; Shwartz et al. Reference Shwartz, Goldberg and Dagan2016) have considered pattern-based and distributional approaches complementary and combined approaches have been proposed. For this purpose, we compute the percentage of hypernym pairs detected by relevant implemented baselines (features as patterns and feature as embedding vectors) and the percentage of pairs detected by exclusively one of these baselines (see Table 13). The results confirm this complementary: for instance, for English-1 corpus and BLESS dataset, 24.7% of the total hypernym pairs is detected by using patterns as features and not detected by using embedding vectors as features.

Table 13

Percentages of HH-pairs detected both jointly and exclusively

We also propose to evaluate the generality of using patterns or embedding vectors as features. For this purpose, we train two respective classifiers on the BLESS dataset, test them on the EVALution dataset, and vice versa using both English-1 and English-2 corpora. Table 14 shows the performance of each classifier. We highlight that the performance of the embedding based classifier is now much worse in comparison with its corresponding performance shown in Table 12; on the contrary, the performance of the classifier based on patterns as features also decreases but much less than the embedding based classifier. Hence, we can state that using patterns as features is expected to show a better general validity than pure embedding vectors, probably because patterns remain less dependent on the training dataset. Moreover, these results also confirm that the supervised distributional baselines are heavily affected by lexical memorization while this is not the case for patterns.

Table 14

Performance across distinct datasets of classifiers using patterns as features and embedding