nearly everything good to go, mod minor hierarchy bug

[nltk_ontology_framework.git] / src / mjacob / ontologybuilder / simple_concepts.py

# This Python file uses the following encoding: utf-8
'''
Created on May 5, 2011

@author: mjacob
'''

from itertools import chain
from framework import OntologyBuilderConcepts, OntologyBuilderFramework
import nltk
from util.cached import Cached
from util.memoized import Memoized
wn = nltk.corpus.wordnet # this is to subvert a bug in my IDE
import re

DOMAIN_LABEL = re.compile('\(of ([^\)]*)\)')
NOMINAL_SYNSET = re.compile('\w+\.n\.\d+$')
        
class Nyms(object):
    """
    Shortcuts for referring to particular relationships in wordnet
    
    HYPERNYMS = C{nltk.corpus.reader.wordnet.Synset.hypernyms}
    INSTANCE_HYPERNYMS = C{nltk.corpus.reader.wordnet.Synset.instance_hypernyms}
    
    HYPERNYMY = (HYPERNYMS, INSTANCE_HYPERNYMS)
    
    HYPONYMS = C{nltk.corpus.reader.wordnet.Synset.hyponyms}
    INSTANCE_HYPONYMS = C{nltk.corpus.reader.wordnet.Synset.instance_hyponyms}
    
    HYPONYMY = (HYPONYMS, INSTANCE_HYPONYMS)
    
    MEMBER_HOLONYMS = C{nltk.corpus.reader.wordnet.Synset.member_holonyms}
    SUBSTANCE_HOLONYMS = C{nltk.corpus.reader.wordnet.Synset.substance_holonyms}
    PART_HOLONYMS = C{nltk.corpus.reader.wordnet.Synset.part_holonyms}
    
    HOLONYMY = (MEMBER_HOLONYMS, SUBSTANCE_HOLONYMS, PART_HOLONYMS)
    
    MEMBER_MERONYMS = C{nltk.corpus.reader.wordnet.Synset.member_meronyms}
    SUBSTANCE_MERONYMS = C{nltk.corpus.reader.wordnet.Synset.substance_meronyms}
    PART_MERONYMS = C{nltk.corpus.reader.wordnet.Synset.part_meronyms}
    
    MERONYMY = (MEMBER_MERONYMS, SUBSTANCE_MERONYMS, PART_MERONYMS)
    
    ATTRIBUTES = C{nltk.corpus.reader.wordnet.Synset.attributes}
    ENTAILMENTS = C{nltk.corpus.reader.wordnet.Synset.entailments}
    CAUSES = C{nltk.corpus.reader.wordnet.Synset.causes}
    ALSO_SEES = C{nltk.corpus.reader.wordnet.Synset.also_sees}
    VERB_GROUPS = C{nltk.corpus.reader.wordnet.Synset.verb_groups}
    SIMILAR_TOS = C{nltk.corpus.reader.wordnet.Synset.similar_tos}
    
    ALL = all of them
    """
    HYPERNYMS = nltk.corpus.reader.wordnet.Synset.hypernyms
    INSTANCE_HYPERNYMS = nltk.corpus.reader.wordnet.Synset.instance_hypernyms
    
    HYPERNYMY = (HYPERNYMS, INSTANCE_HYPERNYMS)
    
    HYPONYMS = nltk.corpus.reader.wordnet.Synset.hyponyms
    INSTANCE_HYPONYMS = nltk.corpus.reader.wordnet.Synset.instance_hyponyms
    
    HYPONYMY = (HYPONYMS, INSTANCE_HYPONYMS)
    
    MEMBER_HOLONYMS = nltk.corpus.reader.wordnet.Synset.member_holonyms
    SUBSTANCE_HOLONYMS = nltk.corpus.reader.wordnet.Synset.substance_holonyms
    PART_HOLONYMS = nltk.corpus.reader.wordnet.Synset.part_holonyms
    
    HOLONYMY = (MEMBER_HOLONYMS, SUBSTANCE_HOLONYMS, PART_HOLONYMS)
    
    MEMBER_MERONYMS = nltk.corpus.reader.wordnet.Synset.member_meronyms
    SUBSTANCE_MERONYMS = nltk.corpus.reader.wordnet.Synset.substance_meronyms
    PART_MERONYMS = nltk.corpus.reader.wordnet.Synset.part_meronyms
    
    MERONYMY = (MEMBER_MERONYMS, SUBSTANCE_MERONYMS, PART_MERONYMS)
    
    ATTRIBUTES = nltk.corpus.reader.wordnet.Synset.attributes
    ENTAILMENTS = nltk.corpus.reader.wordnet.Synset.entailments
    CAUSES = nltk.corpus.reader.wordnet.Synset.causes
    ALSO_SEES = nltk.corpus.reader.wordnet.Synset.also_sees
    VERB_GROUPS = nltk.corpus.reader.wordnet.Synset.verb_groups
    SIMILAR_TOS = nltk.corpus.reader.wordnet.Synset.similar_tos
    
    ALL = (HYPERNYMS 
         , INSTANCE_HYPERNYMS 
         , HYPONYMS
         , INSTANCE_HYPONYMS
         , MEMBER_HOLONYMS
         , SUBSTANCE_HOLONYMS
         , PART_HOLONYMS
         , MEMBER_MERONYMS
         , SUBSTANCE_MERONYMS
         , PART_MERONYMS
         , ATTRIBUTES
         , ENTAILMENTS
         , CAUSES
         , ALSO_SEES
         , VERB_GROUPS
         , SIMILAR_TOS)    

class SimpleConcepts(OntologyBuilderConcepts):
    """
    Generate concepts for terms out of collections of wordnet synsets.
    
    The basic idea is taken from [Navigli and Velardi 2002], though it's simplified somewhat.
    
    Concepts are basically generated by doing a primitive sort of lexical
    disambiguation, by computing scores for a subterm based upon the presence
    of specific connections in wordnet of a subterm and the subterm preceding it. 
    
    In [Navigli and Velardi 2002], the synset for the initial subterm was 
    chosen manually, but this algorithm instead tries to match it against 
    the subterm following it. It seems to work well enough for the purposes
    of demonstration.
    """
    
    @Cached(lambda *x, **y: OntologyBuilderFramework.CONCEPTS)
    def _get_concepts(self, **state):
        """
        given a collection of synonyms (bundles of synsets per subterm),
        disambiguate the synsets and return a single synsets per subterm.
        
        12 specific structural relations mentioned in [Navigli and Velardi 2002]
        are used in the process of disambiguation.
        """
        synonyms = state[OntologyBuilderFramework.SYNONYMS]
        
        concepts = {}
        for synonym in synonyms:
            if len(synonym) < 2:
                continue
            
            """make sure that the head of the concept is nominal"""
            nominal_concept = self.__ensure_nominal(synonym)
            if not nominal_concept[-1]:
                continue # if not a nominal concept, just skip it
            
            concept = self.get_concept(nominal_concept)
            
            if concept:
                concept = tuple(concept) # finalize it
                print "%s means %s" % (synonyms[synonym], concept)
                
                if concept in concepts:
                    concepts[concept].update(synonyms[synonym])
                else:
                    concepts[concept] = set(synonyms[synonym])
            else:
                print "...... unmeaningful: %s" % (synonyms[synonym])
        
        return concepts
    
    def __ensure_nominal(self, synonym):
        """filters out non-nominal synsets from the head of the term"""
        filtered_end = filter(NOMINAL_SYNSET.match, synonym[-1])
        return tuple(chain(synonym[:-1], [filtered_end]))
    
    def get_concept(self, synonym, debug=False):
        """
        disambiguate a specific synonym. 
        """
        initial_synset = self.__get_initial_synset(synonym, debug=debug)
        if not initial_synset:
            if debug:
                print "no initial synset found"
            return None
        
        concept = [initial_synset]
        
        for k in xrange(1, len(synonym)):
            best_synset = self.__get_best_synset(synonym, k, debug=debug)
            
            if not best_synset:
                if debug:
                    print "no optimal synset found for %s" % (synonym[k])
                return None
            
            concept.append(best_synset)
        
        return concept
    
    def __get_initial_synset(self, synonym, debug=False):
        """
        compares the synsets for the initial subterm to those coming after it
        to attempt to disambiguate the sense of the subterm. 
        """
        subterm_synsets = list(synonym[0])
        scores = []
        for subterm_synset in subterm_synsets:
            score = self.__get_initial_score(subterm_synset, synonym)
            scores.append(score)
        
        if debug:
            print subterm_synsets
            print scores
        
        index = self.__get_best_score_index(scores)
        if index is not None:
            return subterm_synsets[index]
        else:
            return None # we can't do anything w/ this
    
    def __get_initial_score(self, synset, synonym):
        """
        get the score for a particular initial synset.
        If no matching synsets are found at all, returns C{[0]}
        """
        for i in xrange(1, len(synonym)):
            score, score_total = self.__get_initial_specific_score(synset, synonym[i])
            if score_total != 0:
                return score
        
        return [0] # it's all 0s, we'll dump the term later
    
    def __get_initial_specific_score(self, synset, other_synsets):
        """
        get the initial score of a synset compared to each of a collection of other synsets
        """
        score = [self.__get_intersection_score(synset, other_synset) 
                 for other_synset in other_synsets]
        return score, sum(score)
    
    def __get_best_synset(self, synonym, k, debug=False):
        """
        disambiguate the synsets of a subterm by looking for particular relations in wordnet
        between them and the the synsets of the preceding subterm. 
        
        returns the best synset, or None if no relationships are found.
        """
        subterm_synsets = list(synonym[k])
        scores = []
        for subterm_synset in subterm_synsets:
            score = self.__get_score(subterm_synset, synonym, k)
            scores.append(score)
        
        if debug:
            print subterm_synsets
            print scores
            
        index = self.__get_best_score_index(scores)
        if index is not None:
            return subterm_synsets[index]
        else:
            return None # we can't do anything w/ this
        
    def __get_score(self, synset, synonym, k):
        """
        get the score of a C{synset} compared to all of the synsets
        at subterm C{k-1}
        
        if no matches are found at C{k-1}, try C{k-2} all the way to C{0}
        """
        for i in xrange(k-1, -1, -1):
            score, score_total = self.__get_specific_score(synset, synonym, synonym[i])
            if score_total != 0:
                return score
        
        return [0] # it's all 0s, we'll deal w/ that later
    
    def __get_specific_score(self, synset, synonym, other_synsets):
        """
        get the score of a synset compared to each of a collection of other synsets
        """
        score = [self.__get_intersection_score(other_synset, synset)
                 for other_synset in other_synsets]
        return score, sum(score)
    
    @Memoized
    def __get_intersection_score(self, other_synset, synset):
        """
        count the number of semantically meaningful relationships in wordnet
        as specified in [Navigli and Velardi 2002]
        """
        S1 = wn.synset(other_synset)
        S2 = wn.synset(synset)
        score = 0
        score += self.__get_colour_score(S1, S2)
        score += self.__get_domain_score(S1, S2)
        score += self.__get_synonymy_score(S1, S2)
        score += self.__get_hypernymy_meronymy_path_score(S1, S2)
        score += self.__get_hyponymy_holonymy_path_score(S1, S2)
        score += self.__get_parallelism_score(S1, S2)
        score += self.__get_gloss_score(S1, S2)
        score += self.__get_gloss_hyperonymy_meronymy_path_score(S1, S2)
        score += self.__get_gloss_parallelism_score(S1, S2)
        score += self.__get_gloss_gloss_score(S1, S2)
        score += self.__get_hyperonymy_meronyomy_gloss_path_score(S1, S2)
        score += self.__get_parallelism_gloss_score(S1, S2)
        #print "intersection score: %s %s %s" % (other_synset, synset, score)
        return score

    CHROMATIC = wn.synset('chromatic.a.03')
    PHYSICAL_ENTITY = wn.synset('physical_entity.n.01')
    COLORS = frozenset(CHROMATIC.similar_tos())

    def __get_colour_score(self, S1, S2):
        """
        if S1 is a color and S2 is a physical object, return 1. else return 0.
        """
        if S1 in SimpleConcepts.COLORS and SimpleConcepts.PHYSICAL_ENTITY in chain(*S2.hypernym_paths()):
            return 1
        else:
            return 0
        
    def __get_domain_score(self, S1, S2):
        """
        if the definition of S1 is of the form that it indicates a property
        of something specific, see if S2 is that type of thing.
        """
        m = DOMAIN_LABEL.match(S1.definition)
        if m:
            domain_label_synsets = wn.synsets(m.group(1).replace(' ', '_'), pos=wn.NOUN)
            score = 0
            for domain_label_synset in domain_label_synsets:
                if S2 == domain_label_synset or S2 in domain_label_synset.hyponyms():
                    score += 1
            return score
        return 0

    @Memoized
    def __glosses(self, synset):
        """
        return a list of all definitions and examples of the synset,
        along with all definitions and examples of anything similar to it.
        """
        l = list(synset.examples)
        l.append(synset.definition)
        for other in synset.similar_tos():
            l.append(other.definition)
            l.extend(other.examples)
        return l

    def __get_synonymy_score(self, S1, S2):
        """
        If S1 and S2 are synonyms, return 1. else 0.
        """
        if S1 == S2 or S2 in chain(*[(b.synset for b in a.pertainyms()) for a in S1.lemmas]):
            return 1
        else:
            return 0
    
    @Memoized
    def __net(self, synset, max_depth=3, *relations):
        """
        finds all connected synsets of @param synset of the kind specified in @param relations,
        up to @param max_depth, which has a default of 3. 
        """
        if max_depth < 1:
            return []
        
        if not relations:
            relations = Nyms.ALL
            
        connections = frozenset(chain(*[nym(synset) for nym in relations]))
        
        if max_depth == 1:
            return connections
        
        else:
            return frozenset(chain(connections, 
                                   chain(*[self.__net(connection, max_depth-1, *relations) for connection in connections])))

    
    def __get_hypernymy_meronymy_path_score(self, S1, S2):
        """
        If something above S1 and something below S2 are identical,
        return 1, otherwise return 0.
        """
        net1 = self.__net(S1, 3, *chain(Nyms.HYPERNYMY, Nyms.MERONYMY))
        net2 = self.__net(S2, 3, *chain(Nyms.HYPONYMY, Nyms.HOLONYMY))
        if S1 in net2 or S2 in net1 or net1.intersection(net2):
            return 1
        else:
            return 0
    
    def __get_hyponymy_holonymy_path_score(self, S1, S2):
        """
        If something above S2 and something below S1 are identical,
        return 1, otherwise return 0.
        """
        return self.__get_hypernymy_meronymy_path_score(S2, S1)
    
    def __get_parallelism_score(self, S1, S2):
        """
        If S1 and S2 share something above them, return 1, else return 0
        """
        net1 = self.__net(S1, 3, *chain(Nyms.HYPERNYMY))
        net2 = self.__net(S2, 3, *chain(Nyms.HYPERNYMY))
        if S1 in net2 or S2 in net1 or net1.intersection(net2):
            return 1
        else:
            return 0
        
    def __is_a_subsequence(self, a, b):
        """
        returns true if @param a is a subsequence of @param b
        """
        for j in xrange(len(b)-len(a)+1):
            match = True
            for i in xrange(len(a)):
                if not a[i] == b[i+j]:
                    match=False
                    break
            if match:
                return True
        return False
    
    def __get_gloss_score(self, S1, S2):
        """
        if a word representing S1 is mentioned in the glosses of S2 or vice versa,
        return 1, otherwise return 0
        """
        for lemma in S2.lemmas:
            for example in self.__glosses(S1):
                if self.__is_a_subsequence(lemma.name.split('_'), example.split(' ')):
                    return 1 
        for lemma in S1.lemmas:
            for example in self.__glosses(S2):
                if self.__is_a_subsequence(lemma.name.split('_'), example.split(' ')):
                    return 1 
        return 0
        
    def __get_gloss_hyperonymy_meronymy_path_score(self, S1, S2):
        """
        if something in the gloss of S1 is above or below S2, return 1
        otherwise 0
        """
        for example in self.__glosses(S1):
            for word in example.split(' '):
                for synset in wn.synsets(word):
                    if (self.__get_hypernymy_meronymy_path_score(synset, S2)
                     or self.__get_hyponymy_holonymy_path_score(synset, S2)):
                        return 1
        return 0

    def __get_gloss_parallelism_score(self, S1, S2):
        """
        if there is a common term above S2 and a word in the glosses of S1,
        return 1, otherwise 0
        """
        for example in self.__glosses(S1):
            for word in example.split(' '):
                for synset in wn.synsets(word):
                    if self.__get_parallelism_score(synset, S2):
                        return 1
        return 0
                
    def __get_gloss_gloss_score(self, S1, S2):
        """
        If a word in the glosses of S1 shares a synset with a word in the glosses of S2,
        return 1, otherwise 0.
        """
        synsets_lists1 = list(chain(*((wn.synsets(word) for word in example.split(' ')) for example in self.__glosses(S1))))
        synsets_lists2 = list(chain(*((wn.synsets(word) for word in example.split(' ')) for example in self.__glosses(S2))))
        for synsets in synsets_lists1:
            if synsets in synsets_lists2:
                return 1
        
        return 0
    
    def __get_hyperonymy_meronyomy_gloss_path_score(self, S1, S2):
        """
        if something in the gloss of S2 is above or below S1, return 1
        otherwise 0
        """
        return self.__get_gloss_hyperonymy_meronymy_path_score(S2, S1)
    
    def __get_parallelism_gloss_score(self, S1, S2):
        """
        if there is a common term above S1 and a word in the glosses of S2,
        return 1, otherwise 0
        """
        return self.__get_gloss_parallelism_score(S2, S1)
    
    def __get_best_score_index(self, scores):
        """
        given a set of scores, return the index of the "best" one
        
        scores are assumed to be lists of numbers
        """
        best_score_index = None
        for i in xrange(len(scores)):
            score = scores[i]
            if score:
                if best_score_index is None:
                    if len(filter(lambda x: x != 0, score)) != 0:
                        best_score_index = i
                elif self.__is_better_score(score, scores[best_score_index]):
                    best_score_index = i
        return best_score_index
    
    def __is_better_score(self, score_a, score_b):
        """
        returns true if score_a is better than score_b
        """
        return self.__value(score_a) > self.__value(score_b)
    
    def __value(self, score):
        """
        [Navigli and Velardi 2002] mention some sort of "lexicographic ordering" of scores
        but don't specify exactly what they mean by this, and my attempts at recreating it
        produced incredibly weird results. Thus, I've opted for something a little simpler
        that seems to work well enough in practice.
        
        the "value" of a score is considered to be 3* the number of non-0 subscores in it,
        plus the sum total of the subscores.
        thus, having two scores of "1" results in a total score of 8, which is equivalent
        to a single score of "5"
        """
        # dictionary order gives weird results.
        return sum(score) + 3*len(filter(lambda x: x != 0, score))