Salmon Run: semantic-web

Showing posts with label semantic-web. Show all posts

Thursday, December 04, 2014

Computing Semantic Similarity for Short Sentences

A reader recently recommended a paper for me to read - Sentence Similarity Based on Semantic Nets and Corpus Statistics. I found the algorithm quite interesting and I ended up implementing it. While I was not able to replicate the results exactly, my results did agree with results you would intuitively expect. I describe the algorithm and my implementation in this post.

My implementation is built with Python and Natural Language Tool Kit (NLTK). The Semantic Net referred to in the paper is Wordnet and the Corpus Statistics are from the Brown Corpus, both of which are available using NLTK's corpus API. Here is the complete code, which I explain below.

from __future__ import division
import nltk
from nltk.corpus import wordnet as wn
from nltk.corpus import brown
import math
import numpy as np
import sys

# Parameters to the algorithm. Currently set to values that was reported
# in the paper to produce "best" results.
ALPHA = 0.2
BETA = 0.45
ETA = 0.4
PHI = 0.2
DELTA = 0.85

brown_freqs = dict()
N = 0

######################### word similarity ##########################

def get_best_synset_pair(word_1, word_2):
    """ 
    Choose the pair with highest path similarity among all pairs. 
    Mimics pattern-seeking behavior of humans.
    """
    max_sim = -1.0
    synsets_1 = wn.synsets(word_1)
    synsets_2 = wn.synsets(word_2)
    if len(synsets_1) == 0 or len(synsets_2) == 0:
        return None, None
    else:
        max_sim = -1.0
        best_pair = None, None
        for synset_1 in synsets_1:
            for synset_2 in synsets_2:
               sim = wn.path_similarity(synset_1, synset_2)
               if sim > max_sim:
                   max_sim = sim
                   best_pair = synset_1, synset_2
        return best_pair

def length_dist(synset_1, synset_2):
    """
    Return a measure of the length of the shortest path in the semantic 
    ontology (Wordnet in our case as well as the paper's) between two 
    synsets.
    """
    l_dist = sys.maxint
    if synset_1 is None or synset_2 is None: 
        return 0.0
    if synset_1 == synset_2:
        # if synset_1 and synset_2 are the same synset return 0
        l_dist = 0.0
    else:
        wset_1 = set([str(x.name()) for x in synset_1.lemmas()])        
        wset_2 = set([str(x.name()) for x in synset_2.lemmas()])
        if len(wset_1.intersection(wset_2)) > 0:
            # if synset_1 != synset_2 but there is word overlap, return 1.0
            l_dist = 1.0
        else:
            # just compute the shortest path between the two
            l_dist = synset_1.shortest_path_distance(synset_2)
            if l_dist is None:
                l_dist = 0.0
    # normalize path length to the range [0,1]
    return math.exp(-ALPHA * l_dist)

def hierarchy_dist(synset_1, synset_2):
    """
    Return a measure of depth in the ontology to model the fact that 
    nodes closer to the root are broader and have less semantic similarity
    than nodes further away from the root.
    """
    h_dist = sys.maxint
    if synset_1 is None or synset_2 is None: 
        return h_dist
    if synset_1 == synset_2:
        # return the depth of one of synset_1 or synset_2
        h_dist = max([x[1] for x in synset_1.hypernym_distances()])
    else:
        # find the max depth of least common subsumer
        hypernyms_1 = {x[0]:x[1] for x in synset_1.hypernym_distances()}
        hypernyms_2 = {x[0]:x[1] for x in synset_2.hypernym_distances()}
        lcs_candidates = set(hypernyms_1.keys()).intersection(
            set(hypernyms_2.keys()))
        if len(lcs_candidates) > 0:
            lcs_dists = []
            for lcs_candidate in lcs_candidates:
                lcs_d1 = 0
                if hypernyms_1.has_key(lcs_candidate):
                    lcs_d1 = hypernyms_1[lcs_candidate]
                lcs_d2 = 0
                if hypernyms_2.has_key(lcs_candidate):
                    lcs_d2 = hypernyms_2[lcs_candidate]
                lcs_dists.append(max([lcs_d1, lcs_d2]))
            h_dist = max(lcs_dists)
        else:
            h_dist = 0
    return ((math.exp(BETA * h_dist) - math.exp(-BETA * h_dist)) / 
        (math.exp(BETA * h_dist) + math.exp(-BETA * h_dist)))
    
def word_similarity(word_1, word_2):
    synset_pair = get_best_synset_pair(word_1, word_2)
    return (length_dist(synset_pair[0], synset_pair[1]) * 
        hierarchy_dist(synset_pair[0], synset_pair[1]))

######################### sentence similarity ##########################

def most_similar_word(word, word_set):
    """
    Find the word in the joint word set that is most similar to the word
    passed in. We use the algorithm above to compute word similarity between
    the word and each word in the joint word set, and return the most similar
    word and the actual similarity value.
    """
    max_sim = -1.0
    sim_word = ""
    for ref_word in word_set:
      sim = word_similarity(word, ref_word)
      if sim > max_sim:
          max_sim = sim
          sim_word = ref_word
    return sim_word, max_sim
    
def info_content(lookup_word):
    """
    Uses the Brown corpus available in NLTK to calculate a Laplace
    smoothed frequency distribution of words, then uses this information
    to compute the information content of the lookup_word.
    """
    global N
    if N == 0:
        # poor man's lazy evaluation
        for sent in brown.sents():
            for word in sent:
                word = word.lower()
                if not brown_freqs.has_key(word):
                    brown_freqs[word] = 0
                brown_freqs[word] = brown_freqs[word] + 1
                N = N + 1
    lookup_word = lookup_word.lower()
    n = 0 if not brown_freqs.has_key(lookup_word) else brown_freqs[lookup_word]
    return 1.0 - (math.log(n + 1) / math.log(N + 1))
    
def semantic_vector(words, joint_words, info_content_norm):
    """
    Computes the semantic vector of a sentence. The sentence is passed in as
    a collection of words. The size of the semantic vector is the same as the
    size of the joint word set. The elements are 1 if a word in the sentence
    already exists in the joint word set, or the similarity of the word to the
    most similar word in the joint word set if it doesn't. Both values are 
    further normalized by the word's (and similar word's) information content
    if info_content_norm is True.
    """
    sent_set = set(words)
    semvec = np.zeros(len(joint_words))
    i = 0
    for joint_word in joint_words:
        if joint_word in sent_set:
            # if word in union exists in the sentence, s(i) = 1 (unnormalized)
            semvec[i] = 1.0
            if info_content_norm:
                semvec[i] = semvec[i] * math.pow(info_content(joint_word), 2)
        else:
            # find the most similar word in the joint set and set the sim value
            sim_word, max_sim = most_similar_word(joint_word, sent_set)
            semvec[i] = max_sim if max_sim > PHI else 0.0
            if info_content_norm:
                semvec[i] = semvec[i] * info_content(joint_word) * info_content(sim_word)
        i = i + 1
    return semvec                
            
def semantic_similarity(sentence_1, sentence_2, info_content_norm):
    """
    Computes the semantic similarity between two sentences as the cosine
    similarity between the semantic vectors computed for each sentence.
    """
    words_1 = nltk.word_tokenize(sentence_1)
    words_2 = nltk.word_tokenize(sentence_2)
    joint_words = set(words_1).union(set(words_2))
    vec_1 = semantic_vector(words_1, joint_words, info_content_norm)
    vec_2 = semantic_vector(words_2, joint_words, info_content_norm)
    return np.dot(vec_1, vec_2.T) / (np.linalg.norm(vec_1) * np.linalg.norm(vec_2))

######################### word order similarity ##########################

def word_order_vector(words, joint_words, windex):
    """
    Computes the word order vector for a sentence. The sentence is passed
    in as a collection of words. The size of the word order vector is the
    same as the size of the joint word set. The elements of the word order
    vector are the position mapping (from the windex dictionary) of the 
    word in the joint set if the word exists in the sentence. If the word
    does not exist in the sentence, then the value of the element is the 
    position of the most similar word in the sentence as long as the similarity
    is above the threshold ETA.
    """
    wovec = np.zeros(len(joint_words))
    i = 0
    wordset = set(words)
    for joint_word in joint_words:
        if joint_word in wordset:
            # word in joint_words found in sentence, just populate the index
            wovec[i] = windex[joint_word]
        else:
            # word not in joint_words, find most similar word and populate
            # word_vector with the thresholded similarity
            sim_word, max_sim = most_similar_word(joint_word, wordset)
            if max_sim > ETA:
                wovec[i] = windex[sim_word]
            else:
                wovec[i] = 0
        i = i + 1
    return wovec

def word_order_similarity(sentence_1, sentence_2):
    """
    Computes the word-order similarity between two sentences as the normalized
    difference of word order between the two sentences.
    """
    words_1 = nltk.word_tokenize(sentence_1)
    words_2 = nltk.word_tokenize(sentence_2)
    joint_words = list(set(words_1).union(set(words_2)))
    windex = {x[1]: x[0] for x in enumerate(joint_words)}
    r1 = word_order_vector(words_1, joint_words, windex)
    r2 = word_order_vector(words_2, joint_words, windex)
    return 1.0 - (np.linalg.norm(r1 - r2) / np.linalg.norm(r1 + r2))

######################### overall similarity ##########################

def similarity(sentence_1, sentence_2, info_content_norm):
    """
    Calculate the semantic similarity between two sentences. The last 
    parameter is True or False depending on whether information content
    normalization is desired or not.
    """
    return DELTA * semantic_similarity(sentence_1, sentence_2, info_content_norm) + \
        (1.0 - DELTA) * word_order_similarity(sentence_1, sentence_2)
        
######################### main / test ##########################

# the results of the algorithm are largely dependent on the results of 
# the word similarities, so we should test this first...
word_pairs = [
  ["asylum", "fruit", 0.21],
  ["autograph", "shore", 0.29],
  ["autograph", "signature", 0.55],
  ["automobile", "car", 0.64],
  ["bird", "woodland", 0.33],
  ["boy", "rooster", 0.53],
  ["boy", "lad", 0.66],
  ["boy", "sage", 0.51],
  ["cemetery", "graveyard", 0.73],
  ["coast", "forest", 0.36],
  ["coast", "shore", 0.76],
  ["cock", "rooster", 1.00],
  ["cord", "smile", 0.33],
  ["cord", "string", 0.68],
  ["cushion", "pillow", 0.66],
  ["forest", "graveyard", 0.55],
  ["forest", "woodland", 0.70],
  ["furnace", "stove", 0.72],
  ["glass", "tumbler", 0.65],
  ["grin", "smile", 0.49],
  ["gem", "jewel", 0.83],
  ["hill", "woodland", 0.59],
  ["hill", "mound", 0.74],
  ["implement", "tool", 0.75],
  ["journey", "voyage", 0.52],
  ["magician", "oracle", 0.44],
  ["magician", "wizard", 0.65],
  ["midday", "noon", 1.0],
  ["oracle", "sage", 0.43],
  ["serf", "slave", 0.39]
]
for word_pair in word_pairs:
    print "%s\t%s\t%.2f\t%.2f" % (word_pair[0], word_pair[1], word_pair[2], 
                                  word_similarity(word_pair[0], word_pair[1]))

sentence_pairs = [
    ["I like that bachelor.", "I like that unmarried man.", 0.561],
    ["John is very nice.", "Is John very nice?", 0.977],
    ["Red alcoholic drink.", "A bottle of wine.", 0.585],
    ["Red alcoholic drink.", "Fresh orange juice.", 0.611],
    ["Red alcoholic drink.", "An English dictionary.", 0.0],
    ["Red alcoholic drink.", "Fresh apple juice.", 0.420],
    ["A glass of cider.", "A full cup of apple juice.", 0.678],
    ["It is a dog.", "That must be your dog.", 0.739],
    ["It is a dog.", "It is a log.", 0.623],
    ["It is a dog.", "It is a pig.", 0.790],
    ["Dogs are animals.", "They are common pets.", 0.738],
    ["Canis familiaris are animals.", "Dogs are common pets.", 0.362],
    ["I have a pen.", "Where do you live?", 0.0],
    ["I have a pen.", "Where is ink?", 0.129],
    ["I have a hammer.", "Take some nails.", 0.508],
    ["I have a hammer.", "Take some apples.", 0.121]
]
for sent_pair in sentence_pairs:
    print "%s\t%s\t%.3f\t%.3f\t%.3f" % (sent_pair[0], sent_pair[1], sent_pair[2], 
        similarity(sent_pair[0], sent_pair[1], False),
        similarity(sent_pair[0], sent_pair[1], True))

Proceeding from the top-down (wrt the code, or bottom-up wrt the algorithm), the lowest unit of the algorithm is the semantic similarity between a pair of words. The word similarity is a combination of two functions f(l) and f(h), where l is the shortest path between the two words in Wordnet (our Semantic Network) and h the height of their Lowest Common Subsumer (LCS) from the root of the Semantic Network. The intuition behind these is that l is a proxy for how similar the words are, and d is a proxy for the specificity of the LCS, ie, LCS nodes closer to the root indicate broader/more abstract concepts and less similarity. The functions f(l) and f(h) serve to normalize these values to the range [0,1]. In formulas, then:

sim(w₁, w₂) = f(l).f(h)

    where:

    f(l) = e^-αl
            e^βh - e^-βh
    f(h) = ------------
            e^βh + e^-βh

Word similarities between a set of word pairs were reported in the paper. As a test, I computed the similarities between the same word pairs with my code above. The similarity values reported in the paper are shown under Exp.Sim and the ones returned by my code are shown under Act.Sim. As you can see, they are close but not identical - however, note that the computed similarites seem to line up with intuition. For example, sim(autograph, signature) is higher than sim(autograph, shore), sim(magician, wizard) is higher than sim(magician, oracle), etc.

Word #1	Word #2	Exp. Sim	Act. Sim
asylum	fruit	0.21	0.30
autograph	shore	0.29	0.16
autograph	signature	0.55	0.82
automobile	car	0.64	1.00
bird	woodland	0.33	0.20
boy	rooster	0.53	0.11
boy	lad	0.66	0.82
boy	sage	0.51	0.37
cemetery	graveyard	0.73	1.00
coast	forest	0.36	0.36
coast	shore	0.76	0.80
cock	rooster	1.00	1.00
cord	smile	0.33	0.13
cord	string	0.68	0.82
cushion	pillow	0.66	0.82
forest	graveyard	0.55	0.20
forest	woodland	0.70	0.98
furnace	stove	0.72	0.17
glass	tumbler	0.65	0.82
grin	smile	0.49	0.99
gem	jewel	0.83	1.00
hill	woodland	0.59	0.36
hill	mound	0.74	0.99
implement	tool	0.75	0.82
journey	voyage	0.52	0.82
magician	oracle	0.44	0.30
magician	wizard	0.65	1.00
midday	noon	1.00	1.00
oracle	sage	0.43	0.37
serf	slave	0.39	0.55

One thing I did differently from the paper is to select the most similar pair of synsets instead of just picking the first noun synset for each word (see the function get_best_synset_pair). This is because a word can map to multiple synsets, and finding the most similar pair mimics the human tendency to maximize pattern seeking (ie see patterns where there are none).

Sentence similarity is computed as a linear combination of semantic similarity and word order similarity. Semantic Similarity is computed as the Cosine Similarity between the semantic vectors for the two sentences. To build the semantic vector, the union of words in the two sentences is treated as the vocabulary. If the word occurs in the sentence, its value for that position is 1. If it doesn't, the similarity for the word is computed against all the other words in the sentence. If it happens to be above a threshold φ, then the value of the element is φ, else it is 0. This value is further attenuated by the information content for the word as found in the Brown corpus. In equations:

s₁ • s₂
    S_s = -----------------
          ||s₁|| * ||s₂||

    where:

    s_i = s * I(w_i) * I(w_j)

                log(n + 1)
    I(w) = 1 - ------------
                log(N + 1)

    where:
      n = number of times word w occurs in corpus
      N = number of words in the corpus

The word order similarity attempts to correct for the fact that sentences with the same words can have radically different meanings. This is done by computing the word order vector for each sentence and computing a normalized similarity measure between them. The word order vector, like the semantic vector is based on the joint word set. If the word occurs in the sentence, its position in the joint word set is recorded. If not, the similarity to the most similar word in the sentence is recorded if it crosses a threshold η else it is 0. In equations:

||r₁ - r₂||
    S_r = 1 - --------------
              ||r₁ + r₂||

    where:
      r₁ = word position vector for sentence 1
      r₂ = word position vector for sentence 2

The similarity between two sentences are modeled as a linear combination of their semantic similarity and word order similarity, ie:

S = δS_s + (1 - δ)S_r

Similar to word similarities, the paper also lists some sentence similarities computed with their algorithm. I tried these same sentences through my code, and as expected, got slightly different results (since the sentence similarity is dependent on word similarities). Here they are. Exp.Sim are the values reported in the paper, Act.Sim (w/o IC) are computed similarities without Information Content normalization and Act.Sim (w/IC) are computed similarities with Information Content normalization. As you can see the Exp.Sim and Act.Sim (w/IC) values are quite consistent.

Sentence #1	Sentence #2	Exp.Sim	Act.Sim (w/o IC)	Act.Sim (w/IC)
I like that bachelor.	I like that unmarried man.	0.561	0.801	0.345
John is very nice.	Is John very nice?	0.977	0.592	0.881
Red alcoholic drink.	A bottle of wine.	0.585	0.477	0.307
Red alcoholic drink.	Fresh orange juice.	0.611	0.467	0.274
Red alcoholic drink.	An English dictionary.	0.000	0.237	0.028
Red alcoholic drink.	Fresh apple juice.	0.420	0.389	0.215
A glass of cider.	A full cup of apple juice.	0.678	0.659	0.347
It is a dog.	That must be your dog.	0.739	0.452	0.709
It is a dog.	It is a log.	0.623	0.858	0.497
It is a dog.	It is a pig.	0.790	0.863	0.500
Dogs are animals.	They are common pets.	0.738	0.550	0.377
Canis familiaris are animals.	Dogs are common pets.	0.362	0.458	0.151
I have a pen.	Where do you live?	0.000	0.134	0.158
I have a pen.	Where is ink?	0.129	0.112	0.077
I have a hammer.	Take some nails.	0.508	0.431	0.288
I have a hammer.	Take some apples.	0.121	0.344	0.147

Once more, while the numbers don't match exactly, the results seem intuitively correct. For example, "Red alcoholic drink" is more similar to "A bottle of wine" than "Fresh apple juice", which is more similar than "An English dictionary", etc.

Thats all I have for today. Hope you found this paper (and my implementation) interesting. The (latest) code for this post is available on GitHub here.

Update 2017-03-13: Many thanks to Mathieu Chrétien for updating the code to use Python3 and contributing it back, you can find it on this github gist.

Saturday, October 25, 2014

Extracting SVO Triples from Wikipedia

I recently came across this discussion (login required) on LinkedIn about extracting (subject, verb, object) (SVO) triples from text. Jack Park, owner of the SolrSherlock project, suggested using ReVerb to do this. I remembered an entertaining Programming Assignment from when I did the Natural Language Processing Course on Coursera, that involved finding spouse names from a small subset of Wikipedia, so I figured I it would be interesting to try using ReVerb against this data.

This post describes that work. As before, given the difference between this and the "preferred" approach that the automatic grader expects, results are likely to be wildly off the mark. BTW, I highly recommend taking the course if you haven't already, there are lots of great ideas in there. One of the ideas deals with generating "raw" triples, then filtering them using known (subject, object) pairs to find candidate verbs, then turning around and using the verbs to find unknown (subject, object) pairs.

So in order to find the known (subject, object) pairs, I decided to parse the Infobox content (the "semi-structured" part of Wikipedia pages). Wikipedia markup is a mini programming language in itself, so I went looking for some pointers on how to parse it (third party parsers or just ideas) on StackOverflow. Someone suggested using DBPedia instead, since they have already done the Infobox extraction for you. I tried both, and somewhat surprisingly, manually parsing Infobox gave me better results in some cases, so I describe both approaches below.

Data and Initial Setup

The data is a small (tiny) XML dump of 24 Wikipedia pages about famous people, US Presidents, authors, actors and other historical figures. The markup is in MediaWiki format. I used Scala's native XML support and some character counting logic to extract and parse the Infoboxes from Wikipedia to a Map of name-value pairs.

To extract the text (ie the non-Infobox) portion from the Wikipedia data, I used the Bliki engine to convert the MediaWiki markup to HTML, then used the Jericho HTML parser to convert it to plain text. I needed to do this because of the richness of the Wiki format - direct conversion to text leaves some of the markup behind.

In order to access data on DBPedia, I used Apache Jena, the Java framework for all things Semantic. As I learnt at the Knowledge Engineering with Semantic Web Technologies course on OpenHPI, the Semantic Web landscape is full of great ideas and implementations which don't mesh together very well. Jena provides a common (albeit complex) API that attempts to unify all of these. It is composed of multiple sub-projects, but fortunately sbt (and friends) allow you to declare it with a single call to an uber-dependency (see below). In any case, all I used Jena for was to build a client to query DBPedia's SPARQL endpoint. As an aside, the call is an HTTP GET and the result can be streamed back as XML, so I could just have used plain Scala to do this, as this EBook by Mark Watson demonstrates.

For reference, here are the additions to my build.sbt that I had to do for this post.

resolvers ++= Seq(
  ...
  "Bliki Repo" at "http://gwtwiki.googlecode.com/svn/maven-repository/",
  ...
)

libraryDependencies ++= Seq(
  ...
  "info.bliki.wiki" % "bliki-core" % "3.0.19",
  "net.htmlparser.jericho" % "jericho-html" % "3.3",
  "edu.washington.cs.knowitall" % "reverb-core" % "1.4.0",
  "org.apache.jena" % "apache-jena-libs" % "2.12.1",
  ...
)

Parsing Infoboxes

As mentioned above, to understand which triples are interesting in the text, we need some indication of what/who the subject and object are in the triples, so we can filter on them and find interesting verbs. So the first step was to parse out the Infobox. We do this by isolating, for each page in the dump, the section of text bounded by the string "{{Infobox" and the matching "}}". Here is the code to parse the various components we care about - the titles, Infoboxes and texts for each page. The Infoboxes are returned as a List of Map of name-value pairs. Also, as mentioned above, the text is extracted in two steps - first to HTML then to plain text.

// Source: src/main/scala/com/mycompany/scalcium/utils/MediaWikiParser.scala
package com.mycompany.scalcium.utils

import java.io.File

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks._
import scala.xml.XML

import info.bliki.wiki.dump.WikiPatternMatcher
import info.bliki.wiki.model.WikiModel
import net.htmlparser.jericho.Source

class MediaWikiParser(xmlfile: File) {

  val InfoboxStartPattern = "{{Infobox"
    
  val titles = ArrayBuffer[String]()
  val texts = ArrayBuffer[String]()
  val infoboxes = ArrayBuffer[Map[String,String]]()
  
  def parse(): Unit = {
    val mediaWikiElement = XML.loadFile(xmlfile)
    (mediaWikiElement \ "page").map(pageElement => {
      val title = (pageElement \ "title").text
      val text = (pageElement \ "revision" \ "text").text
      // parse out Infobox
      val infoboxStart = text.indexOf(InfoboxStartPattern)
      var bcount = 2
      var infoboxEnd = infoboxStart + InfoboxStartPattern.length()
      breakable {
        (infoboxEnd until text.length()).foreach(i => { 
          val c = text.charAt(i)
          var binc = 0
          if (c == '}') binc = -1
          else if (c == '{') binc = 1
          else binc = 0
          bcount += binc
          infoboxEnd = i
          if (bcount == 0) break
        })
      }
      if (infoboxStart >= 0) {
        addTitle(title)
        addInfobox(text.substring(infoboxStart, infoboxEnd))
        addText(text.substring(infoboxEnd + 1))
      }
    })
  }
  
  def addTitle(title: String): Unit = titles += title

  def addInfobox(ibtext: String): Unit = {
    val infobox = ibtext.split("\n")
      .map(line => {
        val pipePos = line.indexOf('|')
        val nvp = line.substring(pipePos + 1).split("=")
        if (nvp.length == 2) {
          val wpm = new WikiPatternMatcher(nvp(1).trim())
          (nvp(0).trim(), wpm.getPlainText())
        } 
        else ("None", "")
      })
      .filter(nvp => ! "None".equals(nvp._1))
      .toMap
    infoboxes += infobox
  }
  
  def addText(text: String): Unit = {
    // convert wiki text to HTML, then to plain text
    val htmltext = WikiModel.toHtml(text)
    val plaintext = new Source(htmltext).getTextExtractor().toString()
    texts += plaintext
  }
  
  def getTitles(): List[String] = titles.toList
  
  def getInfoboxes(): List[Map[String,String]] = infoboxes.toList
  
  def getTexts(): List[String] = texts.toList
}

For the DBPedia client, we query the spouse relationship for each entry using the code below. Note that the actual code is mostly boilerplate, similar to JDBC code.

// Source: src/main/scala/com/mycompany/scalcium/triples/DBPediaClient.scala
package com.mycompany.scalcium.triples

import scala.collection.mutable.ArrayBuffer

import com.hp.hpl.jena.query.Query
import com.hp.hpl.jena.query.QueryExecution
import com.hp.hpl.jena.query.QueryExecutionFactory
import com.hp.hpl.jena.query.QueryFactory
import com.hp.hpl.jena.rdf.model.Literal

class DBPediaClient(url: String = "http://dbpedia.org/sparql") {

  val sparqlQueryTemplate = """
    PREFIX dbpedia: <http://dbpedia.org/resource/>
    PREFIX onto: <http://dbpedia.org/ontology/>
    PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
    
    SELECT ?label  WHERE {
      dbpedia:%s onto:%s ?o .
      ?o rdfs:label ?label .
    } LIMIT 100
  """

  def getObject(subj: String, verb: String): String = {
    val sparqlQuery = sparqlQueryTemplate
      .format(subj.replace(" ", "_"), verb)
    val query: Query = QueryFactory.create(sparqlQuery)
    val qexec: QueryExecution = QueryExecutionFactory.sparqlService(url, query)
    val results = qexec.execSelect()
    val objs = ArrayBuffer[String]()
    while (results.hasNext()) {
      val qsol = results.next()
      val literal = qsol.get("label").asInstanceOf[Literal]
      if ("en".equals(literal.getLanguage())) 
        objs += literal.getLexicalForm()
    }
    if (objs.isEmpty) null else objs.head
  }
}

The JUnit test below demonstrates the use of my MediaWikiParser and DBPediaClient to extract information directly from Infoboxes and from DBPedia resource pages respectively. The people list is the list of titles that were extracted from the Wikipedia XML dump.

// Source: src/test/scala/com/mycompany/scalcium/triples/DBPediaClientTest.scala
package com.mycompany.scalcium.triples

import java.io.File

import scala.collection.mutable.ArrayBuffer
import scala.util.matching.Regex

import org.junit.Test

import com.mycompany.scalcium.utils.MediaWikiParser

class DBPediaClientTest {

  val people = List("Andrew Johnson", "Edgar Allan Poe", 
      "Desi Arnaz", "Elvis Presley", "Albert Camus", 
      "Arthur Miller", "Boris Yeltsin", "Ernest Hemingway", 
      "Benjamin Franklin", "Bill Oddie", "Abraham Lincoln", 
      "Billy Crystal", "Bill Clinton", "Alfonso V of Aragon", 
      "Dwight D. Eisenhower", "Colin Powell", "Cary Elwes", 
      "Alexander II of Russia", "Arnold Schwarzenegger", 
      "Christopher Columbus", "Barry Bonds", "Bill Gates", 
      "Elizabeth Garrett Anderson")
  
  @Test
  def testExtractSpouseFromInfobox(): Unit = {
    val inParens = new Regex("""\(.*?\)""")
    val xmlfile = new File("src/main/resources/wiki/small_wiki.xml")
    val parser = new MediaWikiParser(xmlfile)
    parser.parse()
    val triples = ArrayBuffer[(String,String,String)]()
    parser.getTitles().zip(parser.getInfoboxes())
      .map(ti => {
        val spouse = if (ti._2.contains("spouse")) ti._2("spouse") else null
        // clean up data received (situation dependent)
        if (spouse != null) {
          val spouses = inParens.replaceAllIn(spouse, "")
            .split("\\s{2,}")
            .map(_.trim)
          spouses.foreach(spouse => 
            triples += ((ti._1, "spouse", spouse)))
        } else triples += ((ti._1, "spouse", "NOTFOUND"))
      })
    triples.foreach(Console.println(_))
  }
  
  @Test
  def testExtractSpouseFromDBPedia(): Unit = {
 val triples = ArrayBuffer[(String,String,String)]()
    val client = new DBPediaClient()
    people.map(person => {
      val spouse = client.getObject(person, "spouse")
      if (spouse != null) {
        // clean up data received (situation dependent)
        val spouses = spouse.replace(',', ' ')
          .replace(')', ' ')
          .split('(')
          .map(s => s.trim())
          .foreach(s => triples += ((person, "spouse", s)))
      } else triples += ((person, "spouse", "NOTFOUND"))
    })
    triples.foreach(Console.println(_))
  }
}

Parsing Text

Finally, I use the ReVerb project to parse triples out of the text portion of each Wikipedia entry. The classical approach to parsing out triples is to do deep parsing of sentences (ie convert it to a tree) and then find structures that are rooted at verbs. From what I could glean from the the paper backing ReVerb, the approach used here is to match regular expressions of POS tags of input sentences. The authors claim that this results in higher quality triples being extracted, since it misses out "incoherent extractions". It is also faster since (time-consuming) deep parsing is not involved, so is more suitable for large amounts of data. Here is the code for my ReVerbClient. It takes in a block of text and uses its own tokenizer to break it into sentences.

// Source: src/main/scala/com/mycompany/scalcium/triples/ReVerbClient.scala
package com.mycompany.scalcium.triples

import java.io.StringReader

import scala.collection.JavaConversions._

import edu.washington.cs.knowitall.extractor.ReVerbExtractor
import edu.washington.cs.knowitall.normalization.BinaryExtractionNormalizer
import edu.washington.cs.knowitall.util.DefaultObjects

class ReVerbClient {

  def parse(text: String): List[(String,String,String)] = {
    DefaultObjects.initializeNlpTools()
    val reader = DefaultObjects.getDefaultSentenceReader(
      new StringReader(text))
    val extractor = new ReVerbExtractor()
    val normalizer = new BinaryExtractionNormalizer()
    reader.iterator()
      .flatMap(sent => extractor.extract(sent))
      .map(extract => {
        val normExtract = normalizer.normalize(extract)
        val subj = normExtract.getArgument1().toString()
        val verb = normExtract.getRelation().toString()
        val obj = normExtract.getArgument2().toString()
        (subj, verb, obj)
      })
      .toList
  }
}

This extracts a large number of raw triples. Since our objective is to return spouse triples, we do a considerable amount of filtering and post-processing on the raw triples to return triples that are easily consumable by downstream code. This custom logic is in the JUnit test below.

// Source: src/test/scala/com/mycompany/scalcium/triples/ReVerbClientTest.scala
package com.mycompany.scalcium.triples

import java.io.File

import scala.collection.mutable.ArrayBuffer
import scala.util.matching.Regex

import org.junit.Test

import com.mycompany.scalcium.utils.MediaWikiParser

class ReVerbClientTest {

  val SpouseWords = Set("wife", "husband")
  val BeWords = Set("is", "was", "be")
  val StopWords = Set("of")

  @Test
  def testExtractTriplesFromXml(): Unit = {
    val reverb = new ReVerbClient()
    val infile = new File("src/main/resources/wiki/small_wiki.xml")
    val parser = new MediaWikiParser(infile)
    parser.parse()
    parser.getTitles.zip(parser.getTexts())
      .map(tt => {
        val title = tt._1
        val triples = reverb.parse(tt._2)
        Console.println(">>> " + title)
        // clean up triple
        val resolvedTriples = triples.map(triple => {
          // resolve pronouns in subj, replace with title
          if (isPronoun(triple._1)) (title, triple._2, triple._3)
          else triple
        })
        val tripleBuf = ArrayBuffer[(String,String,String)]()
        // filter out where verb is (married, divorced)
        tripleBuf ++= resolvedTriples.filter(triple => {
          (triple._2.indexOf("married") > -1 || 
            triple._2.indexOf("divorced") > -1)
        })
        // filter out where subj or obj has (wife, husband)
        // and the verb is (is, was, be)
        tripleBuf ++= resolvedTriples.filter(triple => {
          val wordsInSubj = triple._1.split("\\s+").map(_.toLowerCase).toSet
          val wordsInVerb = triple._2.split("\\s+").map(_.toLowerCase).toSet
          val wordsInObj = triple._3.split("\\s+").map(_.toLowerCase).toSet
          (wordsInSubj.intersect(SpouseWords).size > 0 &&
            wordsInVerb.intersect(BeWords).size > 0 &&
            isProperNoun(triple._3)) ||
          (isProperNoun(triple._1) &&
            wordsInVerb.intersect(BeWords).size > 0 &&
            wordsInObj.intersect(SpouseWords).size > 0)
        })
        // extract patterns like "Bill and Hillary Clinton" from either
        // subj or obj
        tripleBuf ++= resolvedTriples.map(triple => {
            val names = title.split("\\s+")
            val pattern = new Regex("""%s (and|&) (\w+) %s"""
              .format(names(0), names(names.size - 1)))
            val sfName = pattern.findAllIn(triple._1).matchData
                .map(m => m.group(2)).toList ++
              pattern.findAllIn(triple._3).matchData
                .map(m => m.group(2)).toList
            if (sfName.size == 1)
              (title, "spouse", List(sfName.head, 
                names(names.size - 1)).mkString(" "))
            else ("x", "x", "x")
          })
          .filter(triple => "spouse".equals(triple._2))
        // post-process the triples
        val spouseTriples = tripleBuf.map(triple => {
            // fix incomplete name in subj and obj from title
            val subjHasTitle = containsTitle(triple._1, title)
            val objHasTitle = containsTitle(triple._3, title)
            val subj = if (subjHasTitle) title else triple._1
            val obj = if (objHasTitle && !subjHasTitle) title else triple._3
            val verb = if (subjHasTitle || objHasTitle) "spouse" else triple._2
            (subj, verb, obj)
          })
          .filter(triple => 
            // make sure both subj and obj are proper nouns
            (isProperNoun(triple._1) && 
              "spouse".equals(triple._2) &&
              isProperNoun(triple._3)))
          
        spouseTriples.foreach(Console.println(_))
      })
  }
  
  def isPronoun(s: String): Boolean =
    "she".equalsIgnoreCase(s) || "he".equalsIgnoreCase(s)
    
  def isProperNoun(s: String): Boolean = {
    val words = s.split("\\s+").filter(w => !StopWords.contains(w))
    val initCapWords = words.filter(w => w.charAt(0).isUpper == true)
    words.length == initCapWords.length
  }
  
  def containsTitle(s: String, title: String): Boolean = {
    val words = Set() ++ s.split("\\s+") 
    val names = Set() ++ title.split("\\s+")
    words.intersect(names).size > 0
  }
}

Results

Each of the three approaches result in overlapping sets of spouse triples, as you can see from the summary below. Note that the "spouse" relationship is bidirectional, so the number of triples extracted are actually double what is shown. As you can see from the results below, none of the three sources seem to be authoritative in the sense that you can depend on them absolutely, and at least a few of them seem to be incorrect (although that could be very likely a bad text parse on my part).

Title	Infobox	DBPedia	Text
Andrew Johnson	(Andrew Johnson, spouse, Eliza McCardle Johnson)	(Andrew Johnson, spouse, Eliza McCardle Johnson)	(Andrew Johnson, spouse, Eliza McCardle)
Edgar Allan Poe	(Edgar Allan Poe, spouse, Virginia Eliza Clemm Poe)	(Edgar Allan Poe, spouse, Virginia Eliza Clemm Poe)	(Edgar Allan Poe, spouse, Virginia Clemm) (Edgar Allan Poe, spouse, Virginia)
Desi Arnaz		(Desi Arnaz, spouse, Lucille Ball) (Desi Arnaz, spouse, Edith Mack Hirsch)	(Desi Arnaz, spouse, Lucille Ball)
Elvis Presley
Albert Camus			(Albert Camus, spouse, Simone Hie) (Albert Camus, spouse, Francine Faure)
Arthur Miller		(Arthur Miller, spouse, Mary Slattery) (Arthur Miller, spouse, Marilyn Monroe) (Arthur Miller, spouse, Inge Morath)	(Arthur Miller, spouse, Mary Slattery) (Arthur Miller, spouse, Marilyn Monroe)
Boris Yeltsin	(Boris Yeltsin, spouse, Naina Yeltsina)	(Boris Yeltsin, spouse, Naina Yeltsina)
Ernest Hemingway	(Ernest Hemingway, spouse, Pauline Pfeiffer)	(Ernest Hemingway, spouse, Elizabeth Hadley Richardson) (Ernest Hemingway, spouse, Pauline Pfeiffer) (Ernest Hemingway, spouse, Martha Gellhorn) (Ernest Hemingway, spouse, Mary Welsh Hemingway)	(Ernest Hemingway, spouse, Hadley Richardson)
Benjamin Franklin	(Benjamin Franklin, spouse, Deborah Read)	(Benjamin Franklin, spouse, Deborah Read)	(Benjamin Franklin, spouse, Richard Bache) (Benjamin Franklin, spouse, Deborah Franklin)
Bill Oddie		(Bill Oddie, spouse, Jean Hart) (Bill Oddie, spouse, Laura Beaumont)	(Bill Oddie, spouse, Laura Beaumont)
Abraham Lincoln	(Abraham Lincoln, spouse, Mary Todd Lincoln)	(Abraham Lincoln, spouse, Mary Todd Lincoln)
Billy Crystal		(Billy Crystal, spouse, Janice Goldfinger)	(Billy Crystal, spouse, Janice Goldfinger)
Bill Clinton		(Bill Clinton, spouse, Hillary Rodham Clinton)	(Bill Clinton, spouse, Hillary Clinton)
Alfonso V of Aragon	(Alfonso V of Aragon, spouse, Maria of Castile Queen of Aragon)	(Alfonso V of Aragon, spouse, Maria of Castile)
Dwight D. Eisenhower	(Dwight D. Eisenhower, spouse, Mamie Eisenhower)	(Dwight D. Eisenhower, spouse, Mamie Mamie Doud Eisenhower)	(Dwight D. Eisenhower, spouse, Mamie Geneva Doud of Denver)
Colin Powell		(Colin Powell, spouse, Alma Vivian Johnson Powell)	(Colin Powell, spouse, Alma) (Colin Powell, spouse, Alma Powell)
Cary Elwes		(Cary Elwes, spouse, Lisa Marie Kurbikoff) (Cary Elwes, spouse, 1 child)
Alexander II of Russia	(Alexander II of Russia, spouse, Maria Alexandrovna) (Alexander II of Russia, spouse, Marie of Hesse and by Rhine)	(Alexander II of Russia, spouse, Marie of Hesse and by Rhine)	(Alexander II of Russia, spouse, Princess Marie of Hesse)
Arnold Schwarzenegger			(Arnold Schwarzenegger, spouse, Maria Shriver)
Christopher Columbus	(Christopher Columbus, spouse, Filipa Moniz Perestrelo)	(Christopher Columbus, spouse, Filipa Moniz)	(Christopher Columbus, spouse, Filipa Moniz Perestrello)
Barry Bonds
Bill Gates		(Bill Gates, spouse, Melinda Gates)	(Bill Gates, spouse, Melinda Gates)
Elizabeth Garrett Anderson			(Elizabeth Garrett Anderson, spouse, Richard Garrett III)

This is what I have for this week. Hope you found it interesting. I am hoping to do something with SVO triples on a larger scale (not on Wikipedia) so this was a good way for me to check out the toolkit. It also introduced me to Apache Jena and SPARQL, something I've been meaning to do ever since I attended the OpenHPI course on Knowledge Engineering.

Salmon Run

Thursday, December 04, 2014

Computing Semantic Similarity for Short Sentences

Saturday, October 25, 2014

Extracting SVO Triples from Wikipedia

Data and Initial Setup

Parsing Infoboxes

Parsing Text

Results

Posts

Labels

Blogs I Read

About me

My Nerd Rating

Visitor Map

Contact Me