RDF model

The core of RDF is to describe resources, which basically are "things" in the world that can be described in words og relations to other resources etc. RDF consists of a lot of triples that together describe something about a particular resource. A triple consist of (Subject, Predicate, Object), and is called a statement.

The subject is the resource, the thing we'd like to talk about. Examples are authors, apartments, people or hotels. Every resource has a URI (unique resource identifier). This could be an ISBN-number, a URL, coordinates, etc.

The predicate states the relation between the subject and the object and are called property. For example Anna is a friend of Bruce, Harry Potter and the Philosopher's Stone was written by J.K. Rowling or Oslo is located in Norway.

The object is another resource, typically a value.

The statements are often modeled as a graph, and an example could be: (lit:J.K.Rowling, lit:wrote, lit:HarryPotter).

Below is a more complex example where you can see that http://www.w3.org/People/EM/contact#me has the property fullName defined in http://www.w3.org/2000/10/swap/pim/contact, which is set to the value of Eric Miller.

Serialization formats

N-triples, Turle, RDF/XML, RDF/JSON.

N-triples

It is plain text format for encoding an RDF graph.

Turtle

Turtle can only serialize valid RDF graphs. It is generally recognized as being more readable and easier to edit manually than its XML counterpart.

RDF/XML

It expresses RDF graph as XML document.

RDF/JSON

It expresses RDF graph as JSON document.

Classes

A class is a set of elements. It defines a type of objects. Individual objects are instances of that class. Classes can be structured hierarchical with sub- and super-classes.

Properties

Properties are restriction for classes. Objects of a class must obey these properties. Properties are globally defined and can be applied to several classes. Properties can also be structured hierarchical, in the same way as classes.

Example query

Returns all sports, from the ontology, that contains the text "ball" in their name.

PREFIX dbpediaowl:<http://dbpedia.org/ontology/>

SELECT DISTINCT ?sport where {
    ?sport rdf:type dbpediaowl:Sport .
    FILTER regex(?sport, "ball", "i") .
}

An online endpoint for queries can be found here.

OWL Full

RDF-based semantics

This approach uses all the OWL primitives. It is great in the way that any legal RDF document is also a legal OWL Full document, and any valid RDF Schema inference is also a valid OWL Full conclusion. The problem is that it has become so powerfull that it is undecidable, there is no complete (efficient) reasoning support.

OWL DL

Direct semantics

DL stans for Descriptive Logic, and is a subset of predicate logic (first-order logic). This approach offers efficient reasoning support and can make use of a wide range of existing reasoners. The downside is that it looses full compability with RDF: a RDF document must be extended in some way to be a valid OWL DL document. However, every legal OWL DL document is a legal RDF document.

Three profiles, OWL EL, OWL QL, and OWL RL, are syntactic subsets that have desirable computational properties. In particular, OWL2 RL is implementable using rule-based technology and has become the de facto standard for expressive reasoning on the Semantic Web.

The OWL language

OWL uses an extension of RDF and RDFs. It can be hard for humans to read, but most ontology engineers use a specialized ontology development tool, like Protégé.

There are four standard syntaxes for OWL:

RDF/XML

OWL can be expressed using all valid RDF syntaxes.

Functional-style syntax

Used in the language spesification document. A compact and readable syntax.

OWL/XML

XML-syntax, allows us to use off-the-shelf XML authoring tools. Does not follow RDF conventions but closely maps onto function-style.

Manchester syntax

As human readable as possible. Used in Protégé.

Document-level

Document-level sentiment classification works with entire documents and tries to figure out of the document has a positive or negative view of the subject in question. An example of this is to look at many reviews and see what the authors mean, if they are positive, negative or neutral.

Sentence-level

Sentence-level sentiment classification works with opinion on a sentence level, and is about figuring out if a sentence is positive, negative or neutral to the relevant subject. This is closely related to subjectivity classification, which distinguishes between objective and subjective sentences.

Entity and aspect-level

Entity and aspect-level sentiment classification wants to discover opinions about an entity or it's aspects. For instance we have the following sentence, "The iPhone’s call quality is good, but its battery life is short", two aspects are evaluated: call quality and battery lifetime. The entity is the iPhone. The iPhone's call quality is positive, but the battery duration is negative. It's hard to find and classify these aspects, as there are many ways to express positive and negative opinions, metaphors, comparisons and so on.

There are two core tasks of aspect-based sentiment analysis: the aspect extraction, and the aspect sentiment classification. We'll start by looking at the latter.

1. Input
    - "The voice quality of this phone is not good, but the battery life is long"
2. Mark sentiment words and phrases
    - good [+1] (voice quality)
3. Apply sentiment shifters
    - NOT good [-1] (voice quality)
4. Handle but-clauses
    - long [+1] (battery life)
5. Aggregate opinions
    - voice quality = -1
    - battery life = +1

Search-based

Turney: Thumbs Up or Thumbs Down?.

Lexicon-based

Kreutzer & Witte: Opinion Mining Using SentiWordNet.

User-based nearest neighbor recommendation

Take ratings database and current user as input, identify other users that had similar preferences to those of the active user in the past. For all products not yet seen by the active user, predict the product based on ratings made by the peer users. This is done under the assumptions that: (a) if users had similar tastes in the past they will have similar tastes in the future, and (b) user preferences remain stable and consistent over time.

The best similarity metric for user-based nearest neighbor is Pearson's correlation coefficient. This returns a number between -1 and 1, describing the correlation (positive or negative).

$$ sim(a,b) = \frac{\sum_{p\in P}{\left( r_{a,p} - \bar{r_{a}} \right)\left( r_{b,p} - \bar{r_{b}} \right)}}{\sqrt{\sum_{p \in P}{\left( r_{a,p} - \bar{r_{a}} \right)^2}}\sqrt{\sum_{p \in P}{\left( r_{b,p} - \bar{r_{b}} \right)^2}}} $$

where $a$ and $b$ are users, $r_{a,p}$ is the rating of user $a$ for item $p$, and $P$ is the set of all items, rated by both $a$ and $b$.

Some challenges with user-based nearest neighbor is the computational complexity; it does'nt scale. How to deal with new items for which no ratings yet exists, called the cold start problem. And the fact that rating matrix is typically very sparse (see Sparsity).

Item-based nearest neighbor recommendation

Large-scale systems needs to handle handle millions of users and items and make it impossible to compute predictions in real time (user-based collaborative filtering won't do). The idea is to compute predictions using the similarity between items and not the similarity between users. Look at the collumns of the rating-matrix, rather than the rows.

The Cosine similarity measure finds the similarity between rating-vectors for two items, and ranges from 0 to 1. The adjusted cosine measure subtracts the user average from the ratings, and ranges from -1 to 1. The best similarity metric for item-based nearest neighbor is Adjusted cosine similarity.

$$ sim(i,j) = \frac{\sum_{u\in U}{\left( r_{u,i} - \bar{r_{u}} \right)\left( r_{u,j} - \bar{r_{u}} \right)}}{\sqrt{\sum_{u \in U}{\left( r_{u,i} - \bar{r_{u}} \right)^2}}\sqrt{\sum_{u \in U}{\left( r_{u,j} - \bar{r_{u}} \right)^2}}} $$

where $i$ and $j$ are items, $U$ is the set of all users that have rated both items, and $r_{u,i}$ is the user $u$'s rating for item $i$, and $\bar{r_{u}}$ is the user $u$'s average rating (of items he have rated).

Data can be preprocessed for item-based filtering. The idea is to construct the item similarity matrix in advance (pairwise similarity of all items). At run time, a prediction for a product and user is made by determining the items that are most similar to the product and by building the weighted sum of the users ratings for these items in the neighborhood.

Similarity-based retrieval

Recommend items that are similar to those the user liked in the past

You can use the nearest-neighbor approach, check whether the user liked similar documents in the past, or a relevance feedback approach called Rocchio’s method, where the user gives feedback on whether the retrieved items were relevant. Both these build on the vector space model.

book = [fantasy=0.3, adventure=0.2, biography=0, ...]

Sparsity

Relates to how much of the ratings-matrix that is empty, being items not rated by users. It is calculated by:

$$ Sparsity = 1 - \frac{|R|}{|I|\cdot|U|} $$

where $R$ is the ratings, $I$ is the items, and $U$ is the users.

Error Rate

Mean Absolute Error (MAE) computes the deviation between predicted ratings and actual ratings.

$$ MAE = \frac{1}{n} \sum_{i=1}^{n}{| p_i - r_i |} $$

Root Mean Square Error (RMSE) is similar to MAE, but places more emphasis on larger devation.

$$ RMSE = \sqrt{\frac{1}{n} \sum_{i=1}^{n}{( p_i - r_i )^2}} $$

Precision

A measure of exactness, determines the fraction of relevant items retrived out of all items retrieved. e.g. the proportion of recommended items that are actually good.

$$ precision = \frac{tp}{tp + fp} = \frac{| \textit{ good items recommended } |}{| \textit{ all recommendations }|} $$

Recall

A measure of completness, determines the fraction of relevant items retrieved out of all relevant items. e.g. the proportion of all good items recommended.

$$ recall = \frac{tp}{tp + fn} = \frac{| \textit{ good items recommended } |}{| \textit{ all good items }|} $$

F1

Combines precision and recall in a singe metric.

$$ F_1 = 2 \times \frac{precision \times recall}{precision + recall} $$

Rank Score

Extends the recall metric to take the position of correct items in a ranked list into account (the order of the recommendations matter). Defined as the ratio of the Rank Score of the correct items to best theoretical Rank Score achivable for the user.

$$ rankscore = \frac{rankscore_p}{rankscore_{max}} $$

$$ rankscore_p = \sum_{i \in h}{2^{-\frac{rank(i) - 1}{\alpha}}}, rankscore_{max} = \sum_{i=1}^{|T|}{2^{-\frac{i-1}{\alpha}}} $$

where $h$ is the set of correctly recommended items (hits), $rank(i)$ returns the position (rank) of an item, $T$ is the set of all items of interest, and $\alpha$ is the ranking half life, i.e. an exponential reduction factor.

Liftindex

Assumes that the ranked list is divided into 10 equal deciles $S_i$ where $\sum_{i=1}^{10}{S_i} = | h |$ is a linear reduction factor (?).

$$ liftindex = \begin{cases} \frac{1 \times S_1 + 0.9 \times S_2 + ... + 0.1 \times S_{10}}{\sum_{i=1}^{10}{S_i}} & \quad \text{if } |h| \gt 0 \\ 0 & \quad \text{else}\\ \end{cases} $$

where $h$ is the set of correct hits.

Discounted Cummulative Gain

Discounted Cummulative Gain (DCG) is a logarithmic reduction factor (?).

$$ DCG_{pos} = rel_1 + \sum_{i=2}^{pos}{\frac{rel_i}{\log_2 i}} $$

where $pos$ denotes the position up to which relevance is accumulated, and $rel$ returns the relevance of recommendation at position $i$.

Idealized Discounted Cummulative Gain (IDCG) assumes that items are ordered by decreasing relevance.

$$ IDCG_{pos} = rel_1 + \sum_{i=2}^{|h| - 1}{\frac{rel_i}{\log_2 i}} $$

Normalized Discounted Cummulative Gain (nDCG) normalizes to the interval [0,1].

$$ nDCG_{pos} = \frac{DCG_{pos}}{IDCG_{pos}} $$

Average Precision

This is a ranked precision metric that places emphasis on highly ranked correct predictions (hits). It is the average of precision values determined after each successful prediction.

Given this result:

$$ AP = \frac{1}{3} \left( \frac{1}{1} + \frac{2}{4} + \frac{3}{5} \right) $$