Overview: Semantic similarity

Semantic Similarity: The Resnik Method

In 1995, Resnik introduced a method for evaluating the semantic similarity between two concepts in an ontology with is_a relations.¹

• Core Idea: Associate probabilities with the concepts of an ontology.
• Definitions:
  • Let \(\mathcal{C}=\left\{c_1,c_2,\ldots,c_n\right\}\) be the set of concepts in the ontology (permits multiple inheritance).
  • Define a function \(p:\mathcal{C}\longrightarrow \left[ 0,1\right]\).
  • \(p(c_i)\) is the probability of encountering an instance of class \(c_i \in \mathcal{C}\).

Ontology Probabilities & Information Content

Information Content (IC)

• Monotonicity: \(p\) is a monotonically increasing function as we move up the hierarchy.
  • If \(c_i\) is_a \(c_j\), then \(p(c_i) \leq p(c_j)\).
• Root Probability: If the ontology has a unique root node \(r\), then \(p(r)=1\).

Resnik’s Definition

The Information Content (IC) of a concept is the negative log likelihood of its probability:

\[\text{IC}(t) = -\log p(t)\]

Intuition Behind IC

As the probability of a concept increases, its information content decreases. This mirrors information theory:

• Common vs. Rare: We gain less new information from an observation of a common event than from a rare one.
• The Root Term: Since the root subsumes all concepts:
  • \(p(\text{root}) = 1\)
  • \(\text{IC}(\text{root}) = -\log(1) = 0\)

Basic Properties of Information Content (IC)

The following logarithmic identities are fundamental to the behavior of \(IC(t) = -\log p(t)\):

\[ \begin{aligned} \log 1 &= 0 \\ \log xy &= \log x + \log y \\ \log x^r &= r \log x \\ \log \frac{1}{x} &= - \log x \\ \log_a x &= \frac{\log x}{\log a} \end{aligned} \]

Entropy

Entropy

• Let us assume we are analyzing a random variable \(X\), which can take on one of a finite number of specific values \(\left\{x_1,x_2,\ldots,x_n\right\}\) with a probability \(\left\{p_1,p_2,\ldots,p_n\right\}\), where the probability of the outcome \(x_i\) is \(p_i\) and \(\sum_{i=1}^n p_i=1\).
• We will use the notation \(p(X=x)\) or simply \(p(x)\) to denote the probability that the random variable \(X\) takes on some specific value \(x\), where \(x\in \left\{x_1,x_2,\ldots,x_n\right\}\).
• We will refer to each of the specific values that \(X\) can take on as .

Shannon defined the information content of an outcome \(x\) as

\[ h(x) = \log_2 \dfrac{1}{p(x)} \tag{1}\]

Entropy (2)

Note that because of the properties of logarithms, \(\log_2 \frac{1}{p(x)} = -\log_2 p(x)\), which is the definition of information content. The of the random variable \(X\), written as \(H(X)\), was defined by Shannon as the average information content of all of the possible outcomes of \(X\).

\[ H(X) = \sum_{i=1}^n p(x_i)\log_2\dfrac{1}{p(x_i)} \tag{2}\]

• Note that by convention \(p(x')\log_2 p(x')=0\) for \(p(x')=0\). This is necessary because \(\log 0\) is undefined, and reasonable because \(\lim_{x\rightarrow 0} x\log x = 0\).

Entropy (3)

Entropy and information content are measured in units called bits (not to be confused with the definition of a bit as a zero or one in computer science).

• The entropy of a random variable \(X\) can be interpreted as the uncertainty of the random variable. For instance, if \(X\) has only one outcome (i.e., \(p(x')=1\) for some \(x'\)), then the entropy of \(X\) is zero.

\[ H(X) = p(x')\log_2\dfrac{1}{p(x')} = 1\times (-1)\times\log_2 1 = 0 \]

Entropy (4)

It can easily be shown that the entropy of \(X\) is maximized if there is maximal uncertainty about the outcome – this is the case if no outcome is more likely than the others, or stated differently, if \(X\) follows a uniform distribution.

Entropy of a random variable \(X=\left\{\mathtt{0, 1}\right\}\) representing Bernoulli process such as a coin toss for different values of \(p(X=1)\). Maximum entropy is achieved if \(p(\mathtt{0}) = p(\mathtt{1}) = 0.5\), i.e., for a uniform distribution. The minimum entropy of zero occurs if the probability of one of the two outcomes is 1.

Entropy (5)

The function \(IC(x) = -\log p(x)\) is a natural one for measuring information content, for several reasons.

• If there is no uncertainty, i.e., if \(p(x=1)\), then \(IC(x)= \log 1 = 0\).
• On the other hand, the information content can be arbitrarily large as the probability of an outcome goes to arbitrary small quantities: \(\lim_{x\rightarrow 0}\log x = \infty\).
• Say we have two random variables, \(X\) and \(Y\), that are independent from one another. It is reasonable to assume that the information content of the outcomes \(x\) and \(y\) must be additive. This is a natural consequence of the logarithm, because

\[ IC(x,y) = -\log_2 (xy) = -\log_2 x - \log_2 y = IC(x) + IC(y) \]

Shannon’s Entropy: The Uniqueness Theorem

Claude Shannon’s definition of entropy is not arbitrary; it is the only function that satisfies three fundamental postulates.

Entropy

A proof of this theorem can be found in Khinchin’s book¹. It can also be shown that \(\lambda=1\) if \(\log_2\) is used.

Information Content in Gene Ontology (GO)

In the setting of GO, the probability of a term \(t\) is the probability that a randomly chosen protein is annotated to that term.

• The Root Term: Assuming all genes are annotated to the root (the most general term):
  • \(p(\text{root}) = 1\)
  • \(\text{IC}(\text{root}) = -\log_2(1) = 0\)
• General vs. Specific:
  • Terms used for many genes have low IC.
  • Terms used for very few genes have high IC.

IC: Numerical Examples

Assume we have a set of 256 annotated genes:

Semantic Similarity (\(t_1 \leftrightarrow t_2\))

Resnik defined similarity between two terms based on the Information Content of their Most Specific Ancestor (MSA).

\[\text{IC}(t) = -\log p(t)\]

Semantic similarity: An example

• An ontology with annotated items