Semantic indexing and retrieval is an important research area, as the available amount of information on the Web is growing more and more. In this paper, we introduce an original approach to semantic indexing and retrieval based on Formal Concept Analysis. The concept lattice is used as a semantic index and we propose an original algorithm for traversing the lattice and answering user queries. This framework has been used and evaluated on a song dataset.
Semantic indexing and retrieval refer to organizing a set of information items inside an
index according to the semantic relations and concepts that they share, and then
searching within this index to identify the items, the context of which matches a given user
query [
In the past years, Formal Concept Analysis (FCA [
Different from browsing support and automatic facet construction, some approaches
use the concept lattice directly as a document index and propose different strategies to
explore it in order to find those documents relevant for a given user query. In general,
given a document-term concept lattice and a conjunctive user query, these approaches
work by identifying a formal concept in the lattice that best represents the query. This
formal concept is then denominated as the “query concept”. Two strategies can be
distinguished to explore the concept lattice in order to retrieve documents: the work in
[
In this paper we propose a semantic indexation and retrieval technique supported over the FCA framework. It is based on the basic general idea of constructing a documentterm concept lattice and identifying a “query concept”, where we propose a novel exploration strategy based on the notion of “cousin concepts”. We illustrate this technique using a song dataset, where songs are indexed using the terms appearing in their lyrics (songs are documents). The specific goal of this approach is to retrieve relevant songs to a user based on the terms provided in his query using a concept lattice as a semantic index. In order to enrich the song descriptions we use Wordnet (an external knowledge source which describes semantic relations among terms). As an additional characteristic we address the problem of semantic indexing and retrieval as a 3-step knowledge discovery on databases (KDD) process, comprising three main steps: data preparation, discovery and filtering of the results.
The main contributions of this work are the following: – The notion of cousin concepts. – Highlighting the capabilities of using FCA and a concept lattice as a semantic index and proposing a novel algorithm that traverses the lattice to retrieve information based on the content of the concepts. – Proposing the incorporation of semantic indexing to current song retrieval systems and providing initial results, as a proof-of-concept of the potential that such an application can have.
We have selected songs indexing as an application domain since few work have been
done in content-based indexation using lyrics. To the authors knowledge, the work in
this area mostly focus on using low-level features of songs [
The rest of this paper is organized as follows. Firstly, Section 2 introduces the use of FCA for semantic indexing and querying and present our approach according to the main steps of KDD. Next, Section 3 presents the evaluation results obtained for our approach. Finally, Section 4 presents a discussion of the extension of our work and the conclusions of our research.
The problem addressed in this paper can be defined as finding songs the lyrics of which are related to a set of user-provided keywords, through a sufficient “closeness of meaning”. Subsequently, our goal is to construct a semantic index, from a given set of songs and their lyrics and a relation which will successfully support the context-based song retrieval.
To address the above we first constructed a dataset of songs, where each song is
related to a number of semantic meanings as follows. Two sources of data, namely
musiXmatch and WordNet were used. MusiXmatch is a lyrics database, recently
released as part of the MillionSong Dataset [
In the following, a song si is defined as a pair {ti, Li} where ti denotes the title and Li the lyrics of the song in the form of a bag-of-words, as provided by musiXmatch. 2.1
Given a song si = {ti, Li}, let synsets(Li) be the list of WordNet synsets that are associated with each word wj in the lyrics Li. Each retrieved synset has a definition and a set of synonyms. Word wj is part of the synonyms. As an example, Table 1 illustrates the synsets retrieved from WordNet for the word “Soldier”.
From the above example it can be understood that not every synset retrieved through WordNet is valuable in the context of a song. For instance, in the context of a war, a reference to a “soldier” would be clearly related to the definition of an enlisted man who serves in an army and not to the definition of a soldier ant. The third definition can also be disregarded since it is associated with a verb.
Therefore, to accurately annotate each song, we need to keep only those synsets that correspond to the actual context of the song. 3 http://wordnet.princeton.edu
To address this, a filtering process took place as follows: a well-known similarity
metric, namely the Wu-Palmer Similarity Measure [
P wp(ssj , ssk) j6=k |synsets(Li)| (1)
The synset with the lowest avg sim is deleted from synsets(Li). The filtering is repeated until we reach to a threshold of 20 most similar elements in synsets(Li), which will be considered to constitute the so-called semantic core of the song si, denoted as core(si). The threshold of 20 synsets was selected heuristically, since it was found to represent the semantic core of the songs, in the specific dataset, in a concise and non redundant way. As an example, Table 2 shows some of the synsets selected to describe the song titled “The Green Beret Balad”. As it may be observed, the synsets that do not belong to the song’s context (which is mostly about the notions of war, battle, man, etc.) will be less related to the rest of the song’s synsets, and therefore they will be more likely to be omitted. In this example, the synset “soldier.n.01: an enlisted man or woman who serves in an army” has been selected, instead of the other WordNet’s alternative “soldier ant: soldier.n.02: a wingless sterile ant or termite having a large head and powerful jaws adapted for defending the colony”.
The outcome of the filtering process is the set core(si), which is considered as the final set of semantic annotations of the song si since it refers to a well-defined semantic schema, i.e. WordNet, where each annotation contains a definition and relations with other annotations.
We built the semantic song index as a concept lattice using Formal Concept Analysis
(FCA) following the lines of [
In the formal context of songs considered in this paper K = (G, M, I), the set
of objects G contains the songs of the dataset while the set of attributes M contains
all the WordNet synsets included in the semantic cores of the songs in G. The set I
contains the relations gIm which stand for “song g has synset m in its semantic core”.
Table 3 shows an example of a formal context created from 11 songs and 6 synsets.
The concept lattice obtained from this example context is illustrated in Figure 1. The
concept lattice is presented in its reduced notation where objects (songs) and attributes
(synsets) are shown only next to their object/attribute-concept, i.e. the most general
concept introducing the attribute (which is inherited from higher to lower levels), the
most specific concept having the object in its extent (the object being shared from lower
to higher levels).
A simple query to the constructed semantic index (i.e. the concept lattice) is a pair
q = (Aq, Bq) where Aq denotes an empty extent to be filled and Bq = {ss} is a synset
to be searched for. Actually, the retrieval is based on two steps. The first one corresponds
to “exact matching” (as in [
For a given attribute concept (Ass, Bss), the querying algorithm traverses the lattice to extract all cousin concepts (Ai, Bi) of the synset ss, and then it moves down the concept lattice, repeating the same extraction level by level. It should be noticed that the original synset query ss is not present in any of the intents of the cousin concepts Bi, this is why we can speak of “partial matching”. Every cousin concept (Ai, Bi) is ranked according to the intersection that its extent has with the extent of the original attribute concept using the following metric: rank(Ai, Ass) = |Ai ∩ Ass| |Ai| (2)
This metric is two-fold since it allows the detection of concepts (Ai, Bi) which are far from the original concept and share no common objects with the extent of (Ass, Bss) (Ai ∩ Ass = ∅ and rank = 0) and those that are too abstract and describe too many objects (|Ai| ≫ |Ass| and rank ∼ 0).
Hereafter, we give details on the steps of the querying algorithm through the use of an example, graphically illustrated in Figure 2. Let us consider a user query for songs related to the synset “bolshevik.n.01” (concept 3 on Figure 2). 1. Find the attribute-concept (Ass, Bss) for the synset {ss}: concept 3. 2. Find the sub-hierarchy of (Ass, Bss) in the concept lattice, i.e. all concepts subsumed by (Ass, Bss) and order them by levels: concepts 8, 11, 10, 15, 13, 16, 17 (solid arrows in Figure 2). 3. For each concept in this sub-hierarchy, find the super-concepts which are cousin concepts of (Ass, Bss) (and then for the descendants of (Ass, Bss)): concept 2 is a cousin of 3 because of 8, 4 is a cousin of 3 because of 11, 6 is a cousin of 8 because of 10, etc. The final list is ordered by levels: concepts 2, 4, 5, 6, 9, 7, 12, 14 (dashed arrows in Figure 2). 4. Calculate the rank value of each cousin concept (according to Eq. 2) and sort these cousin concepts in descending order: concepts 6, 12, 9, 4, 2, 5, 7, 14. 5. The result is composed of the songs in the extent of the attribute-concept (Ass, Bss) and the extents of the cousin concepts.
The final result, in terms of the retrieved cousin concepts, their rankings and the songs in their extents, is shown in Table 4.
Concept rank Songs 3 (AC) 16,26,39 6 66% 33 12 50% 32 9 50% 4 50% 2 29% 1,10,14,18 5 25% 24 7 17% 14 0%
It can be noticed that the basic target of the algorithm proposed above is semantic retrieval. The order in which the algorithm presents the retrieved groups of songs to the user is a “recommendation decision”, which could depend on user preferences and imply the use of a threshold to filter the final list of songs. Semantic retrieval does not necessarily imply the use of a threshold, which is why, for the scope of this paper, we present all the songs retrieved. 3
As described in the previous section, the lattice is queried using a synset ss (e.g. bolshevik.n.01). This synset is directly related to a set of songs (direct answerss), i.e. those which are in the extent of the attribute concept (Ass, Bss) of that synset (in the case of bolshevik.n.01, songs 16, 27 and 39). These songs will be retrieved along with the set of songs found in the extents of the cousin concepts (indirect answerss) of (Ass, Bss) (songs 1, 10, 14, 18, 24, 32 and 33).
Regarding the songs in direct answerss , we are interested in examining whether our approach can find them if we apply it on a modified formal context where their relations with the synset ss have been eliminated. Of course, in this case, these songs cannot be retrieved as directly related songs, but only as songs found in the extents of cousin concepts. For example, if we eliminate the relation between song 16 and the synset bolshevik.n.01 we want to know if this song can be retrieved by querying the new lattice using the synset bolshevik.n.01.
Regarding the set indirect answerss, we are interested in examining how it changes after the application of our approach on the modified formal context since the elimination of a (song,synset) relation will affect the structure of the concept lattice and hence the output of the proposed retrieval algorithm. Small variations in the content of this set will indicate robustness. 3.1
To evaluate the above and subsequently the definition of cousin concepts presented in
section 2.3 we used and adapted the leave-one-out cross validation (LOOCV)
methodology, which is a special type of cross validation [
For a given scenario, if song sscn can be retrieved by querying for synset ssscn we mark the scenario as successful (e.g. querying for bolshevik.n.01 and retrieving song 16 for scenario with ssscn = bolshevik.n.01 and sscn = song 16). The number of successful scenarios for a synset ss is given by successf ul scenarios(ss). The total number of scenarios for a synset ss (given by total scenarios(ss)) is determined by the number of songs where the synset appears in (i.e. the number of crosses on the synset column in the primary formal context), since we only eliminate at each time a single (song,synset) relation from the primary formal context (e.g. for the synset bolshevik.n.01 we construct 3 scenarios for songs 16, 27 and 39). We can then define success rate(ss) as illustrated in equation 3.
success rate(ss) = successf ul scenarios(ss) total scenarios(ss) (3)
Because the relation between a song and a synset is eliminated in a given scenario, the song cannot be retrieved by the “exact matching” of the synset ss (the song will not be contained in direct answerss). Instead, the method proposed using cousin concepts has to be used and the song should be found through “partial matching”. The test consist on observing if the song can be found in indirect answerss. Hence, the measure of success rate represents the tendency of how related are those songs found through “partial matching” with the query and the usefulness of the proposed method.
To evaluate the changes in the set indirect answerss, we compare the full set of retrieved songs from each scenario with the respective set of songs retrieved from the primary concept lattice (i.e. the concept lattice constructed from the primary formal context). We calculate precision defined in Eq. 4 as the proportion of true positives over the retrieved list of songs in a scenario. Accordingly, we calculate recall, in Eq. 5, as the proportion of true positives over the retrieved list of songs in the primary concept lattice, i.e. the concept lattice without any removal. The expression Ret(scn, ss) denotes the total set of songs retrieved from scenario scn (direct answerss ∪ indirect answerss) querying for synset ss while primary denotes the primary concept lattice. precision(scn, ss) =
(4) (5) 3.2
For each synset we calculate the mean precision and recall from all their scenarios. From our test set of 357 songs and 1848 synsets we selected 192 synsets and simulated 1027 scenarios (working with approximately 1000 scenarios allows a lower volume of computation and more different trials). Table 5 shows the values of these measures for 10 synsets. For example, it can be seen that synset anteroom.n.01 has relations with 4 songs. A success rate of 1 means that all simulations were successful. Recall of 0.9 and Precision of 0.96 mean that for an elimination of 25% of the relations for the synset (1 over 4 songs), still 90% of the information was retrieved and 96% of the information was correct. There is a positive relation between the number of songs in which the synset appears and the success rate measure. This is not strange since synsets appearing in a few songs will be in fewer concepts in the lattice and hence the simulation affects them in the worst manner. For example, for the synset bar.n.03, the elimination of one relation with a song leads to the elimination of 50% of its relations (1/2), while for the synset battle.n.01 the elimination of one relation with a song leads to the elimination of only 5% of its relations (1/20).
Figure 3 shows the distribution of success rate, recall and precision (in the interval
of [
It should be noticed that a certain degree of bias, caused by the inclusion of the directly related songs in the measures of precision/recall, is to be expected. That is, given that for each scenario we are eliminating only one (song, synset) relation, the remaining directly related songs will be present in both sets retrieved when querying the scenario and the primary concept lattice. Therefore, the precision/recall measures are meant to be used, in the context of this paper, as a means of examining how the set of cousin concepts is affected for each synset, and they should not be considered as a medium of comparison with other information retrieval approaches.
Finally, even if more experiments have to be completed, we can conclude that the definition of cousin concepts is valuable and allows the use of a concept lattice as a semantic index to retrieve objects not directly related to a query. In this paper we propose an approach for semantic indexing and retrieval of songs based on Formal Concept Analysis and exploiting the representation of a song’s lyrics as a collection of relevant WordNet synsets.
A number of limitations may be found to the present work. First the evaluation focuses, at this stage, mainly on examining the robustness of the cousin concepts. This evaluation choice was made on the basis of two reasons: i) the definition of cousin concepts is the core of the proposed approach and therefore its efficiency is the first parameter that needs to be evaluated and ii) the literature reports an absence of other approaches that perform indexing and retrieval based on the semantics of song lyrics, and which could be used as a comparison benchmark. Given the above, and in view of the positive results that the current evaluation has yielded, the next stage is to proceed with a user evaluation study, which will allow us to examine the relativeness of the retrieved results according to the intended meaning of specific users’ queries.
A second limitation refers to the requirements of the proposed approach in case it is intended for a large-scale application. Specifically, at this stage a relatively small dataset of 357 songs was used, however additional experiments would be necessary to examine how the size of the dataset affects the performance of the approach. Another necessity refers to defining in more detail the way that a user query can be matched to a set of synsets, which can then be used to query the lattice-based song index.
Future work includes two directions: i) enriching the semantic song representation with other information resources such as DBpedia and ii) expanding the proposed approach to different data collections.
On the first direction, additional information about the meaning of the songs can be
found in external user-contributed sources, such as Wikipedia and its semantic
equivalent DBPedia. Therefore, as a first future direction we plan to enrich the constructed
semantic song representations with categorical knowledge, i.e. regarding the broader
“topic” that each song is about, from DBPedia. To take advantage of this categorical
knowledge we plan to extend the proposed FCA-based approach with Relational
Concept Analysis [
A second potential extension we consider applying the proposed approach to other types of information content, such as scientific papers or news information, to examine its generalization capability and to facilitate comparison with other benchmark techniques of semantic search and retrieval.
As a conclusion, in this paper we propose a novel contribution to the field of semantic indexing and retrieval, which is based on Formal Concept Analysis. We use the concept lattice as a semantic index and propose a novel algorithm to traverse the lattice in order to match user queries with semantically relevant information items. The approach was tested on a song dataset and the obtained results show good capabilities.