Learning Outcomes

(a)  Demonstrate knowledge and understanding of core ideas and foundations of unsu-

pervised and supervised learning on vectorial data

(b)  Explain principles and techniques for mining textual data

(c)  Demonstrate understanding of the principles of efficient web-mining algorithms

(d)  Demonstrate understanding of broader issues of learning and generalisation in ma- chine learning and data analysis systems

Question 1 Dimensionality Reduction

(a)  Explain what is meant by  “dimensionality reduction” and why it is sometimes nec-essary.

(b) Consider the following dataset of four sample points 

Explain how to calculate the principal components of this dataset, outlining each step and performing all calculations up to (but not including) the computation of eigenvectors and eigenvalues.

(c) What does principal component analysis (PCA) tell you about the nature of a multi- variate dataset? Explain how it can be used for dimensionality reduction?

(d) What are the limitations of PCA and what other dimensionality reduction techniques may be used instead?

(e) You are given a dataset consisting of 100  measurements,  each of which  has  10

variables. The eigenvalues of the covariance matrix are shown in the following table:

What can you say about the underlying nature of this dataset?

Model answer / LOs / Creativity:

Learning outcomes a and d.  Part e is creative.

(a)  Finding a basis (coordinate system) in which the data can be represented in terms of a

reduced number of coordinates without loss of significant information. It is necessary because of the curse of dimensionality which leads to problematic phenomena such as convergence of distances and ultra-sparse sampling, and sometimes also because it allows the data size to be reduced.

(b)  From data matrix X subtract column means to form

Form the covariance matrix

Find eigenvalues/vectors – NOT needed as we did not do this in class.

Ordered eigenvalues correspond to the variance of the data projected onto the cor- responding eigenvector. Usually aim to remove directions with small variance as not informative.

(c) Aligns coordinates with natural directions in the data in order of decreasing variance. Directions in which the data does not vary can be considered to be unimportant and thus removed, reducing the dimensionality.

(d)  PCA can be costly to perform, and is a strictly linear technique.  RP is very cheap but it is also linear and interpretation is difficult.

(e)  95% variance is in first three dimensions, with ¿ 99% in the first five dimensions.

Likely that true dimensionality of data is in this region. Unlikely that data is genuinely 10-dimensional.

Question 2 Classification

(a) Consider the Soft Margin Support Vector Machine learnt in Lecture 4e. Consider also that C = 100 and that we are adopting a linear kernel, i.e., k(x（〉] , x（/]) = x（〉]T x（/] . Assume an illustrative binary classification problem with the following training ex- amples:

Question 3 Document Analysis

(a)  In a small universe of five web pages, one page has a PageRank of 0.4. What does

this tell us about this page?

(b) Compare and contrast the TF-IDF and word2vec approaches to document vectori-

sation.  You should explain the essential principles of each method, and highlight their respective advantages and disadvantages.

(c) One possible approach to searching a large linked set of documents is to combine a measure of document similarity such as TF-IDF similarity with a measure of a page’s importance such as that provided by PageRank. Suggest three ways in which this could be done and discuss the advantages and disadvantages of each of them.

Model answer / LOs / Creativity:

Learning outcomes b, c.  Part c is creative.

(a) The page is more important than average, as measured by the number of links that

point to it.  If all pages were equally important, the pagerank would be 0.2.  This page is therefore much more heavily linked to than the other pages. 2

(b) TF-IDF uses pure word frequency information locally (TF) and globall (IDF). Does

not capture any semantic information, in particular about word order. Can be applied to relatively small data. Documents and terms can be added on-the-fly. Interpretable representation.

word2vec learns the semantic context of words as it is trained to predict either a missing word (bas of words) or a word’s context (skip-gram). Generally needs large corpus. Cannot be retrained on-the-fly. Can learn non-linear relationships within the training set.  Representation not interpretable.

(c) The  idea that these two concepts can  be combined for  high quality  information retrival was discussed in lectures, but now how it could actually be done. A number

of possible creative solutions are possible here.

Potential approaches that might be discussed are:

● Compute the document similarity vs all document, multiply by the Page rank and sort. This is simple to implements but computationally expensive for very large document sets. It also implicitly means that it’s very hard to compensate for a low Page rank which could lead to less relevant documents being returned.