ii c ○ Koninklijke Philips Electronics N.V. 2006 Philips Restricted TN-PR-TN 200600495 Tit

Technical note TN-PR-TN2006/00495Issued:07/2006Weighting in fuzzy subsumption discoveryRisto GligorovPhilips Research EindhovenPhilips Restrictedc Koninklijke Philips Electronics N.V.2006TN-PR-TN2006/00495Philips RestrictedPhilips Restricted TN-PR-TN2006/00495 Keywords:semantic web,concept hierarchy,music,subsumption discovery,weigh-ing,normalized google distanceAbstract:We address the problem of discovering fuzzy subsumption relations between concepts from different concept hierarchies.We investigatetwo approximate reasoning schemes which aim at improving of thefuzzy subsumption relation assessment.Thefirst scheme utilizes thestructure of a concept hierarchy and the second takes advantage of aGoogle-based dissimilarity measure.We present the results of experi-ments with several music concept hierarchies from actual sites on theInternet.TN-PR-TN2006/00495Philips Restricted Conclusions:In this study,we have addressed the problem of discovering fuzzy sub-sumption relations between concepts from different concept hierarchies.We have examined two weighting schemes.Thefirst exploits the struc-ture of the CH and the second the NGD dissimilarity measure.Fromthe evidence provided in section1.4we can conclude that weightingimproves the accuracy of the fuzzy subsumption relation assessment.The structure-based weighting as it is,depends solely on the struc-ture of the CH.Hence,if the CH’s structure does not preserve theactual supergenre-subgenre relations then the weight values can be mis-leading.Unfortunately,in reality this is the case.ADN,for instance,evenly disperse the classified music genres into a tree-like structure ofdepth2.In order to achieve this artificial structure the designers ofADN music metaschema had to sacrifice some supergenre-subgenre re-lations;Metal and rock are siblings in ADN classification even thoughmetal is a subgenre of rock.Google-based weighting,on the other hand,utilizes the NGD which takes advantage of the vast knowledge available on the web today.Con-sequently,it should provide a more accurate assessment of the weightvalues.Therefore,we are inclined to believe that the Google-basedweighting is a better method.iv c Koninklijke Philips Electronics N.V.2006Philips Restricted TN-PR-TN2006/00495 Contents1Fuzzy subsumption discovery11.1Introduction (1)1.1.1Internet Music Schemas (2)1.1.2Terminology and definitions (3)1.1.3Matching (5)1.1.4Approximate subsumption algorithm (5)1.1.5Weighting (6)1.2Structure-based weighting (8)1.2.1The two-phase method (8)1.2.2Equal cardinality weighting (10)1.2.3Path length weighting (11)1.3Google-based weighting (12)1.3.1Normalized Google Distance (12)1.3.2The weighting scheme (12)1.4Experiments (17)1.4.1Structure-based weighting experiments (18)1.4.2Google-based weighting experiments (19)1.5Conclusion (19)1.6Appendix A (21)1.7Appendix B (26)1.8Appendix C (29)1.9Appendix D (33)c Koninklijke Philips Electronics N.V.2006vPhilips Restricted TN-PR-TN2006/00495Section1Fuzzy subsumption discovery1.1IntroductionThe progress of information technology has made it possible to store and access large amounts of data.However,since people think in different ways and use different termi-nologies to store information,it becomes hard to search each other’s data stores.With the advent of the Internet,which has enabled the integrated access of an ever-increasing number of such data stores,the problem becomes even more serious.The music domain is no exception.(We restrict to legal distribution.)The variety and size of offered con-tent makes it difficult tofind music of interest.It is often cumbersome to retrieve even a known piece of music.Our goal is to improve this Internet music search.We aim to use semantics in the retrieval process,which is conveyed in the Semantic Web.In this context we study the problem of semantic integration over different music provider’s schemas.More specific, the problem is tofind pairs of concepts(genres,styles,classes...)from different metadata schemas that have an equivalent meaning.It is not sufficient to use the concept labels only,since,for example,their position in the schemas influences their meaning as well. Figure1.1illustrates with an example from existing music schemas.Although the labels are equivalent(“Experimental”),they represent different classes.Figure1.1:Two music genres:Although the labels are equivalent,Experimental,they represent different classes.The problem offinding the right music thatfits a user preferences is similar to the problem of matching the schemas of two different providers.The main problem when matching different schemas is the discovery of concept pairs across the schemas that c Koninklijke Philips Electronics N.V.20061TN-PR-TN2006/00495Philips RestrictedFigure1.2:The extracted music schemas.have an equivalent meaning,orfinding a concept with the closest meaning in the other schema when an equivalent one does not exist.The discovery of such similar concepts requires mechanisms that are able tofind fuzzy correspondences rather than the exact ones.In this study,we explore the problem of discovering fuzzy subsumption relations across schemas,and in particular the improvement of the accuracy when assessing fuzzy relations.We develop weighting schemes that emphasize the more important parts of the fuzzy subsumption problem at hand.The document is structured as follows.In the rest of section1.1we explain the problem we are addressing in more detail and introduce the terminology used in this document.In section1.2we present a weighting scheme that utilizes the structure of the metadata schema.In section1.3we lay out a Google-based weighting scheme and in section1.4we present results from the experiments on the effect of weighting.1.1.1Internet Music SchemasOn the Internet,music metadata schemas mostly exist in the form of a navigation path through the music offered.A metadata schema isn’t always offered next to the music,but a visitor can interactively navigate through different pages that list the music. We consider this structure of navigation paths together with the labeling on the links and pages as the metadata schema of that provider.After considering several music provision sites,we selected seven of them and extracted the schema(navigation path): CDNOW()1,MusicMoz2,CD Baby3,ARTIST direct Network4,allmusic 5,LAUNCH cast on Yahoo6and 7.Also,we have extracted the music schema present in the free online encyclopaedia Wikipedia8.In Figure1.2we present a general overview of the data.Philips Restricted TN-PR-TN2006/00495Music classifications and stylesMusic content providers usually classify the music they offer into classes for easy ac-cess.These classes are organized in a hierarchy.We refer to the classified entities as ually these are artists,albums,compilations,other kinds of releases,songs, and etc.The majority of the terms used to identify a class of music entities are music genres and styles,for example Blues,Jazz,....They can be associated with various kinds of attributes that make a further distinction,for example Americal Blues,Electronic Jazz,....Music genres and styles on their own are intrinsically ill-defined,there is no single authority that can decide for a music entity which genre or style it belongs to.For example,it’s becoming increasingly dificult to categorize the newly emerging musical styles that incorporate features from multiple genres.Also,the attempts to clasify particular musicians in a single genre are sometimes ill-founded as they may produce music in a variety of genres over time or even within a single piece.In general,however, two definitions are accepted:intrinsic-a set of rules that decide when an entity belongs to the genre or not,and extrinsic-a set of all possible music entities that belong to the genre.For our purpose,we use the second one and account for the genres and styles as sets of music entities.Consequently,music classification is a collection of music classes described with english language terms,where instances are being classified.It can be modelled as a concept hierarchy.Fuzziness in music classificationThere are no objective criteria that sharply define music classes.Genre is not precisely defined.As a result,different providers often classify the same music entities(artists, albums,songs...)differently.Widely used terms like Pop and Rock do not denote the same sets of artists at different portals.That is also the case for even more specific styles of music like Speed Metal.In our experiments when testing with instance data,we restricted to the artists shared by Music Moz and Artist Direct Network,i.e.artists that are present and classified in both portals.In the sequel we refer to them as MM and ADN,respectively.From the class named Rock(including its subclasses)in MM there are471shared classified artists, in ADN there are245,and196shared artists are classified under Rock in both of them. Hence,from all the artists classified under Rock in at least one of the two portals,only about38%is classified under Rock in both portals,figure1.3.This example shows that there is a high degree of fuzziness present in the music domain.Therefore we expect that exact reasoning methods to create matching are not useful,and approximate methods are more appropriate.1.1.2Terminology and definitionsIn this section we will introduce several terms used in the rest of the text.Definition1(Concept hierarchy)A Concept Hierarchy(CH)is a triple(N,E,l), where N is a set of nodes,E⊆N×N is a set of edges among the nodes,and l:N→L is a function that assigns a label from the set of all labels L to every node.The graph structure underlying the CH represents a directed acyclic graph.c Koninklijke Philips Electronics N.V.20063TN-PR-TN2006/00495Philips RestrictedFigure1.3:Equivalence testing between ADN and MM.Figure1.4:Part of MusicMoz CHIn our case the classifications and the corresponding CHs have tree-like structure. Figures1.4depicts part of the CH used within MuzicMoz electronic catalogue of music. We extracted the CH using the navigation paths and the labeling of the pages that list the music offered by several providers.In the problem of integration,besides the node’s labels in a CH,we can also use the structure implied by the edges.We carry out this idea by introducing the notions of node concept and extension concept of a node.Definition2(Node Concept)Given CH(N,E,l)and n∈N,the node concept of n,designated with C(n),is the concept denoted by the label l(n)attached to n.For instance,the label Alternative attached to node5from MusicMoz CH(figure1.4)reffers to the concept C Alternative which is the node concept for this node i.e.C(5)≡C Alternative.According to[1]and[2]we define the extension concept of a node as follows:Definition3(Extension concept of node)If n1,n2,···,n is the path leading from 4c Koninklijke Philips Electronics N.V.2006the root node n1to the node n in CH(N,E,l)then the extension concept of the node n is the concept given with Ext(n)=C(n1)∩C(n2)∩···∩C(n)Example1C Rock and C Alternative represent the node concepts of nodes3and5, respectively(figure1.4).Extension concept of node5is given with Ext(5)≡C Rock∩C Alternative.The extended concept of a node takes into consideration not only the node label of that node but also the node’s position in the graph.By using the extended concept in-stead of the node concept we capture more semantics.We will clarify this using example 1.Clearly,if looking at the CH(figure1.4)one would deduce that node5semantically coincides with the set of rock music entities that are also members of alternative music genre,which is the exact meaning of Ext(5).Node concept of node5(C Alternative), on the other hand,includes non-rock music entities(members of alternative hip-hop, an altenative music subgenre that has no connection with rock music).Therefore it is semantically inacurate just to consider the node concept.In the rest of the text we will use the terms concept and node concept interchangeably.1.1.3MatchingIn this section we will state the problem of matching different CHs.A CH can be represented as a graph.Therefore the problem of matching CHs can be phrased as a problem of matching graphs.According to[2]we can define graph matching as follows:Mapping element is a4-tuple<m ID,N i1,N j2,R>,i=1,···,h;j=1,···,k;where m ID is a unique identifier of the given mapping element;N i1is the i-th node of thefirst graph, h is the number of nodes in thefirst graph;N j2is the j-th node of the second graph,k is the number of nodes in the second graph;and R specifies a similarity relation of the given nodes.A mapping is a set of mapping elements.Matching is the process of discovering mappings between two graphs through the application of a matching algorithm.In the sequel we will adapt the above definition to better suite our purpose of matching terminologies.We have two concept hierarchies A=(N A,E A,l A)and B= (N B,E B,l B)with the corresponding label sets L A and L B that represent two different terminologies.Let n∈N A be a node from A and m∈N B a node from B.With Ext A(n) and Ext B(m)we will denote the extension concepts of the nodes n and m,respectively. As we have said previously we focus our attention on the problem of discovering fuzzy subsumption relations across CHs,therefore the similarity relation R will be a sumsump-tion relation quantified by a coefficient on[0,1]interval.R measures by what extent the fuzzy subsumption relation between Ext A(n)and Ext B(m)holds.Mapping elements are computed as4-tuples<m ID,Ext A(n),Ext B(m),R>where Ext A(n)and Ext B(m)are extension concepts of nodes n and m,respectively and R is a coefficient that measures by what extent the fuzzy subsumption relation between Ext A(n)and Ext B(m)holds.The algorithm that computes the fuzzy subsumption relation is stated in the next section.1.1.4Approximate subsumption algorithmWe utilize the algorithm stated in[3]that addresses the problem of subsumption test between two propositional logic formulas used to represent classes(concepts).We briefly explain the algorithm.c Koninklijke Philips Electronics N.V.20065The subsumption check between classes can be split into a set of subproblems,each checking if one(left)disjunct is a subclass of a(right)conjunct.If all the subproblems are satisfied,the original problem is also satisfied.In our approximation,we allow a few of the subproblems to be unsatisfiable,while still declaring the original problem satisfiable.The(relative)number of satisfiable subproblems is a measure of how strongly the subclass relation between the two given formulas hold.Below,we explain the approach in a more formal way.In our notion we use the inter-pretation of the concepts as sets and consequently we replace conjunction by intersection relation,and implication by a subset relation.We want to check ifA⊆B(1.1) where A≡A n1∩A n2∩···∩A n I and B≡B m1∩B m2∩···∩B m J,holds.It can be easily seen that(1.1)is true if and only ifA⊆B m(1.2)jholds for all j=1,2,···,J.We refer to the expresions(1.2)as subproblems.Now we introduce the idea of approximation:The relation(1.1)holds ifffor all subproblems the subclass relation(1.2)holds.If for only a few of the subproblems the relation(1.2)doesn’t hold,we may say that the relation(1.1)almost holds.Even more, we can express the strength at which the relation(1)holds as the ratio between the number of false subproblems(subproblems for which the subclass relation doesn’t hold) and the total number of subproblems.We call this ratio the sloppiness and we use the letter s to denote its value:|{j:A⊆B m j|}s(A⊆B)=For this purpose we can“weight”the subproblems to determine their contribution in the end result.In the remainder of this report we address the problem of improving the accuracy when assessing fuzzy subsumption relations by subproblem weighting.We investigate two different approaches to obtain the weighting coefficients.Thefirst ap-proach uses the graph structure of the CH and the second one takes advantage of the vast knowledge available on the web today by using a google-based dissimilarity measure. Both approaches are described in detail in the subsequent sections.c Koninklijke Philips Electronics N.V.20067Figure1.5:Example1.2Structure-based weightingIn structure-based weighting we exploit the graph structure of the concept hierarchy to derive the weights.The approach we take is based on the following two assumptions.•Generally,the greater the distance from the root of the graph the more specific the node concept of the node.•Both,more specific and less specific node concepts are relevant for the sumsumption relation discovery.Figure1.1suggests that when there is high level of agreement between the more specific concepts,thefinal outcome should be mainly influenced by the less specific concepts.Figure1.5,on the other hand,indicates the opposite.The subsumption relation assessment should be mainly influenced by the more specific concepts when there is high level of agreement between the less specific concepts.In-line with these assumptions we investigate aflexible subsumption relation dis-covery method comprised of two phases.In thefirst phase we assign more importance (weight)to less specific concepts,and in the second phase we reverse the situation, more specific concepts receive more importance(weight).From each phase we obtain a sloppiness value.Thefinal sloppiness value is a combination of these two sloppiness values.1.2.1The two-phase methodIn this subsection we will present the aforementioned method.We are given the con-cept hierachies(N A,E A,l A)and(N B,E B,l B).n I and m J are nodes from N A and N B respectively.We want to check the validity ofExt A(n I)≡A n1∩···∩A n I⊆B m1∩···∩B m J≡Ext B(m J)where n1,···,n I is the path leading from root node n1to node n I in CH(N A,E A,l A), m1,···,m J is the path leading from root node m1to node m J in CH(N B,E B,l B),8c Koninklijke Philips Electronics N.V.2006A ni≡C(n i)i=1,···,I and B m j≡C(m j)j=1,···,J.According to the algorithm destribed in section1.1.4we have the following subproblems to solveA⊆B mj(1.4)where A≡A n1∩···∩A n I,j=1,···,J.As said,in thefirst(second)phase more (less)importance is assigned to the more(less)general concepts.Therefore the level of“generality”of a concept plays a central role in our method.In the subsequent sections we will introduce(graph)structure based measures for quantifying this notion of concept “generality”.But,for the time being,given a node concept B mjj=1···,J,we assumethat gen(B mj )measures the generality of the concept B mj.In the sequel we explain themethod in detail.Phase1:The“weight”assigned to the subproblem A⊆B mjin phase1is given byw j=gen(B mj)1.2.2Equal cardinality weightingAs stated previously,we define genre as a set of all music entities that belong to the genre.From a semantics viewpoint,node concepts and extended concepts represent musical genres.Therefore,we can think of node concepts and extended concepts as the set of all entities included in the genre they represent.We can use this interpretation to develop “generality”measure.We focus ourselves on the subproblems given by (1.4)in subsection 1.2.1.We will use the logarithm of cardinality ratio as a generality measure i.e.gen (B m j )=ln|B m j ||B 1∩B 2∩B 22|.From the CH we haveB 1=21 i =2(B 1∩B i )The sets (B 1∩B i ),i =2,···,21,represent different sibling nodes from the CH.Hence,they are pairwise disjoint.If we assume that these sets have equal cardinality we will get the following result |B 1|=20·|B 1∩B 2|.Furthermore,B 1∩B 2=41 i =22(B 1∩B 2∩B i )10cKoninklijke Philips Electronics N.V.2006and(B1∩B2∩B i),i=22,···,41represent different sibling nodes from the CH.There-fore,they are pairwise disjoint.If we again assume that these sets have equal cardinality we obtain the result|B1|=400·|B1∩B2∩B22|Next,we will try to approximately assess the value of|B2||B1∩B2∩B22|.The set B3is partitionedby the sets B1and B2into four disjoint sets,B3\(B1∩B2),(B3∩B1)\(B1∩B2∩B3), (B3∩B2)\(B1∩B2∩B3)and B1∩B2∩B3.We assume that|B3\(B1∩B2)|= |(B3∩B1)\(B1∩B2∩B3)|=|(B3∩B2)\(B1∩B2∩B3)|=|B1∩B2∩B3|.As a consequence we have|B3|=4·|B1∩B2∩B22|The type of partition of a set that we have used in the last two cases is formally defined in Appendix A.Also,in Appendix A we have proved that the number of disjoint sets in which a set A i is partitioned by a family of sets A1,···,A i−1,A i+1,···,A n is equal to2n−1(Appendix A,theorem3).Using this fact,we can deduce,just as we did in the example,thatgen(B mj)=(j−1)ln(2)+ J−1k=j ln(p m k)j=1,···,J−1gen(B mJ)=(J−1)ln(2)where p mj,j=1,···,J−1,is the branching factor(number of children)of the node m j. We reffer to the two-phase method that uses this generality measure as equal cardinality weighting.In Appendix B we state and prove several theorems regarding the maximal values of the weights used in equal cardinality weighting scheme.If we observe the cardinality ratios given in the example we notice that their values decrease exponentially.Consequently,if we substitute these values into(1.5)as generality measures,thefirst subproblem in thefirst phase will receive far more weight than the rest of the subproblems.This observation is also valid for the last subproblem in the second phase.Therefore,thefinal result will be mainly influenced by thefirst and the last subproblem.In order to alleviate this effect we consider the logarithm of the cardinality ratios rather than the actual cardinality ratios,as expressed in(1.7).1.2.3Path length weightingOnce again,we attach our attention to the subproblems given by(1.4)in subsection 1.2.1.We will use the lenght of the path in the graph representation of CH as a generality measure i.e.gen(B mj)=dist(m j,m J)(1.8)where m j and m J are the nodes to whom the node concepts B mj and B mJbelong,respectively.The measure given with(1.8)is calculated in respect to the node m J and it is defined only for the node concepts of the ancestors of m J.We call the two-phase method that uses(1.8)as generality measure path length weighting.c Koninklijke Philips Electronics N.V.2006111.3Google-based weightingThe weighting scheme we consider in this section takes advantage of the vast knowledge available on the web today by using a google-based dissimilarity measure described in the next section.1.3.1Normalized Google DistanceWe utilize a dissimilarity measure,called Normalized Google Distance(NGD),intro-duced in[4].According to[4]each web page indexed by the Google search engine can be observed as a set of index terms.A search for a particular index term returns a certain number of hits-web pages where this term occurred.NGD takes advantage of the number of hits returned by Google to compute the semantic distance between concepts. The concepts are represented with their labels which are fed to the Google search engine as search terms.Given two search terms x and y,the the normalized google distance between x and y,NGD(x,y),can be obtained as followsmax{log f(x),log f(y)}−log f(x,y)NGD(x,y)=to the subproblem A⊆B i,i=1,···,m,depends on how much information the concept B i provides about the concept B.The level of informativeness can be observed as a“semantic closeness”between the concepts B i and B.Intuitively,a concept that is semantically less distant should be more relevant than a concept that is semantically more distant.As a semantic distance measure we use the Normalized Google Distance. The procedure that assigns weights to the subproblems proceeds as follows: First,we compute the normalized google distances.d1=NGD(B1,B)...d m=NGD(B m,B)We normalize these values to the[0,1]intervald 1=d1m i=1d i(1.11)Subsequently,the normalized distance values are converted into similaritiess1=1−d 1...s m=1−d mFinally,from the similarity values the weights for the subproblems are derived.w1=s1mi=1s iAfter solving the subproblems we obtain the sloppiness value in the following manners(A⊆B)= A⊆B i w i(1.12) Google queriesAs said,concepts are represented with their labels.The concept labels are transformed into search queries and fed into the Google search engine.For instance,if we have to compute the NGD between the concepts C rock and C rock∩C alternative we have to gather three pieces of information:the number of hits for the term rock(label of C rock),the number of hits for the terms alternative and rock(labels of C alternative∩C rock)and the number of hits for the tuple of search terms rock and alternative rock(C rock,C alternative∩C rock).To get the number of web pages in which the search term rock occurs we use the query:rock music.Besides music style,the word rock has other senses.One of them is rock as a lump or mass of hard consolidated mineral matter(stone).Therefore,tofilter out the occurrences of the term rock in a non-musical context we add the search term music to the google query.c Koninklijke Philips Electronics N.V.200613Analogously,we retrieve the number of web pages where both search terms alternative and rock occur using the query:alternative rock music.Finally,we use the query: alternative rock music to retrieve the number of pages where the tuple of search terms rock and alternative rock occurs.In general,if we want to compute the NGD between the concepts B i and B,where the label L k denotes the concept B k,k=1,···,m,we proceed as follows: First,we obtain the number of hits for B i using the query:“L i”music.L i might be a multi-word,and by putting quotes around it we force Google to search for the exact occurrences of the word.Second,we obtain the number of hits for B using the query:“L1”···“L m”music. L k,k=1,···,m,might be a multi-word,and by putting quotes around it we force Google to search for the exact occurrences of the word.Finally,we obtain the number of hits for the tuple(B i,B)using the query:“L1”···“L m”music.L k,k=1,···,m,might be a multi-word,and by putting quotes around it we force Google to search for the exact occurrences of the word.L i∈{L1,···,L m}, therefore the last query coincides with the previous.Modified NGDAs said,we compute the NGD values using(1.9)d i=NGD(B i,B)=max{log f(B i),log f(B)}−log f(B i,B)log M−log f(B)(1.14) ord i=NGD(B i,B)=N iNN =N if(B)(1.16)where mNGD stands for modified Normalized Google Distance.14c Koninklijke Philips Electronics N.V.2006ExampleIn this section we explain the process of weighting when assessing fuzzy subsumption relation in detail.In our example we consider the subsumption relation between two styles from MusicMoz and ArtistDirectNetwork portals,seefigure1.11.Thefirst step is to transform the concepts into formulas.The formulas representing the meaning of Country from ADN and Bluegrass Gospel from MM are given as follows:CountryMM=Country∩Bluegrass∩Bluegrass GospelWe use these formulas to test for the subsumption relation between the two concepts Country MM(CountryMM).According to the algorithm described in section1.1.4we have to solve the following subproblems:Country⊆Country−true(Country is on both sides)Country⊆Bluegrass−false,Country⊆Bluegrass Gospel−falseFor this set of subproblems the uniform weighting scheme yields a sloppiness value of 66%.Next,we apply the google-based weighting scheme on the same set of subproblems. As described in section1.3.2we willfirst compute the NGD valuesd1=NGD(Country,Country∩Bluegrass∩Bluegrass Gospel)d2=NGD(Bluegrass,Country∩Bluegrass∩Bluegrass Gospel)d3=NGD(Bluegrass Gospel,Country∩Bluegrass∩Bluegrass Gospel)The google queries“Country”music,“Bluegrass”music,“Bluegrass Gospel”music and “Country”“Bluegrass”“Bluegrass Gospel”music return467000000,24000000,338000 and261000hits,respectively.Consequently,wefind the following mNGD distances:d1=7.44147d2=4.39942d3=0.164622As described in section1.3.2,using these values we derive the weights for the subproblemsw1=0.190081w2=0.336629w3=0.493144In this case the sloppiness value is81%.Compared to the66%sloppiness of the uniform weighting scheme,the google-based weighting scheme yields an accuracy gain of15%.c Koninklijke Philips Electronics N.V.200615。