微信客服：xiaoxionga100
微信客服：ITCS521
Python代写-COMP61021
时间：2021-11-27
COMP61021: Representation Learning Ke Chen
Manifold Learning*
Ke Chen
To carry out this assessed coursework, you will need the Python notebook file, manifold.ipynb,
which contain code to get you started with each of the assignments and the data files: bars.npz
for the bar images and face_tenenbaum.npz for the face images. Other datasets (e.g. ten_city)
are generated by using built-in functions in the notebook. All above are available in a zipped file
on BlackBoard alongside this document.
Caveat: You may not display some resultant figures correctly with %matplotlib notebook which
appears in the first line of the given Jupyter notebook file, especially on MS Windows. To deal with
this issue, you need to use the Firefox browser instead of Chrome, Microso IE and Edge.
Manifold learning is one of the central themes in representation learning. In this coursework, you
are asked to use Python to implement several manifold learning algorithms learnt from this course
and apply your own implementation to synthetic and real datasets for manifold learning.
Supportive Soware
To do this coursework, you are provided with our own Python implementation of LLE and visuali-
sation tools required by this coursework.
Our implementation in Python includes: optimization functions in optimization.py, locally lin-
ear embedding inlle.py, display functions inhelpers.pyand dataset functions indataset.py.
optimization.py enables you to carry out the gradient descent method required for the assign-
ments regarding the stress-based MDS algorithms.
To solve an optimization problem by using the gradient descent method, the signature of this func-
tion is as follows:
gradient_descent(D, x0, loss_f, grad_f, lr, tol, max_iter)
where D is a distance matrix between points in the original space and x0 is an initial value we want
to get. loss_f and grad_f are the loss function and its first derivative or gradient, respectively. lr
and tol are learning rate and tolerance for early stopping. max_iter is the maximum number of
iteration.
In lle.py, the signature of lle function is as follows:
lle(data, n_components=2, n_neighbors=None, epsilon=None, dist_func=None,
reg_func=None)
where data contains data points in the original space, n_components is the dimensionality of tar-
get embedded space, n_neighbors is the number of neighbours for KNN, epsilon is the value of
*Assessed Coursework: the deadline and requirements can be found at the end of this document.
Page 1
COMP61021: Representation Learning Ke Chen
fixed radius for -distance, dist_func is the function to find out neighbours and their distances,
and reg_func implements a regularization term to avoid the singular case.
Below, you can see two examples on how to use thelle function with dierent neighbourhoods.
from Code . l l e import l l e
data = . . . # data po i n t i n the o r i g i n a l space
n_dim = 2
k = 7
Y = l l e ( data , n_components =n_dim , n _ n e i g h b o r s =k ,
d i s t _ f u n c = n e a r e s t _ n e i g h b o r _ d i s t a n c e , r e g _ f u n c = r e g _ f u n c )
from Code . l l e import l l e
data = . . . # data po i n t i n the o r i g i n a l space
n_dim = 2
e = 5 . 3
Y = l l e ( data , n_components =n_dim , e p s i l o n =e ,
d i s t _ f u n c = f i x e d _ r a d i u s _ d i s t a n c e , r e g _ f u n c = r e g _ f u n c )
where KNN is used in the first case and -NN is used in the second case. For the reg_func ar-
gument, the None value can be set except for Assignment 7 where the function reg_func(C, K)
provided in manifold.ipynb must be used.
helpers.pyprovides the useful functions to enable you to visualise the results of each assignment.
This Python module containsVIS_Shortest_path_2dandImageViewer, VIS_Bars classes.
VIS_Shortest_path_2d is used to display not only the embedded points in latent space but also
the shortest path between two specified data points. Its constructor is as follows:
VIS_Shortest_path_2d(proj, dist, predecessors, fig_vis)
where proj refers to the embedded points in the target space, dist and predecessors are dis-
tance matrix and the index of predecessors for the shortest path which are obtained from isomap
function. fig_vis is figure object created by the Python built-in function figure() in the mat-
plotlib package. The usage of this class is as follows:
import m a t p l o t l i b . p y p l o t as p l t
from Code . isomap import isomap , d i s t _ n e a r e s t _ n e i g h b o r
p o i n t s = . . . # data po i n t i n column v e c t o r
n_components = 2
n _ n e i g h b o r s = 6
Y , d i s t , p r e d e c e s s o r s = isomap ( . . . )
f i g = p l t . f i g u r e ( )
V I S _ S h o r t e s t _ p a t h _ 2 d ( Y , d i s t , p r e d e c e s s o r s , f i g )
Page 2
COMP61021: Representation Learning Ke Chen
By using the VIS_Shortest_path_2d, the embedded points in latent space will be plotted. Also,
you can see the shortest path between two selected points.
ImageViewer is used to display images on the shortest path and its constructor is as follows:
ImageViewer(data, index, image_size, fig_vis, max_row=5)
where data refers to data points in the source space, index refers to the indices of points on the
shortest path, image_size is the size of images used in data, fig_vis is a figure object created
by Python built-in function, figure(), in the matplotlib package and max_row is the maximum
number of images in a row. The usage of this class is as follows:
import m a t p l o t l i b . p y p l o t as p l t
data = . . . # data po i n t s i n the o r i g i n a l space
i m a g e _ s i z e = [ 6 4 , 6 4 ]
s t a r t _ i d x = 1
e n d _ i d x = 100
path = g e t _ s h o r t e s t _ p a t h ( p r e d e c e s s o r s , s t a r t _ i d x , e n d _ i d x )
f i g = p l t . f i g u r e ( )
i m g _ v i e w e r = ImageViewer ( data , path , i m a g e _ s i z e , f i g , 5 )
i m g _ v i e w e r . show ( )
where get_shortest_path is provided in manifold.ipynb for Assignment 5 and predecessors
is returned from the isomap function.
VIS_Bars allows you to display the bar images in the dataset, bars.npz, and its result yielded by
the lle function. Its constructor is as follows:
VIS_Bars(data, proj, fig_vis, color=’r’, image_size=(40,40), both=True)
where data are points in the source space, proj are the embedded points yielded by lle, fig_vis
is a figure object created by figure() in the matplotlib package, color is the value of colour to
represent the embedded points in this colour (e.g. ’r’ for red, ’b’ for blue), image_size is the size of
images specified in data, and both is the flag to indicate whether both horizontal bars and vertical
bars appear in data or not. If the last parameter, both, is set as True, the colour parameter, color,
will be ignored. The usage of this class is as follows:
Case 1: set both=True
from Code . d a t a s e t import b a r s
data_bar , c e n t e r s = b a r s ( )
d a t a _ b a r = d a t a _ b a r . T
c e n t e r s = c e n t e r s . T
i m a g e _ s i z e = [ 4 0 , 4 0 ]
Page 3
COMP61021: Representation Learning Ke Chen
n _ n e i g h b o r s = 5
n_components = 2
Y _ b a r = l l e ( . . . )
f i g _ b a r = p l t . f i g u r e ( )
v i s _ b o t h = V I S _ B a r s ( data = data_bar , p r o j = Y_bar , f i g _ v i s = f i g _ b a r ,
i m a g e _ s i z e = i m a g e _ s i z e , both = True )
Case 2: set both=False
from Code . d a t a s e t import b a r s
data_bar , c e n t e r s = b a r s ( )
d a t a _ b a r = d a t a _ b a r . T
c e n t e r s = c e n t e r s . T
i m a g e _ s i z e = [ 4 0 , 4 0 ]
n _ n e i g h b o r s = 5
n_components = 2
Y _ b a r = l l e ( . . . )
f i g _ b a r = p l t . f i g u r e ( )
v i s _ v = V I S _ B a r s ( data = d a t a _ b a r [ : , : 5 0 0 ] , p r o j = Y _ b a r [ : , : 5 0 0 ] ,
f i g _ v i s = f i g _ v _ b a r , c o l o r = ’ r ’ ,
i m a g e _ s i z e = i m a g e _ s i z e , both = F a l s e )
The dataset.pymodule contains functions for loading datasets given in the Data/directory or for
being used as the built-in functions for data generation.
ten_city contains data regarding the distances between 10 U.S.A. cities. This returns a lower trian-
gle part of the distance matrix. The full distance matrix for this dataset can be achieved by adding
this matrix and its transpose as follows:
from Code . d a t a s e t import t e n _ c i t y
f l y i n g _ d i s t , c i t y = t e n _ c i t y ( )
f l y i n g _ d i s t = f l y i n g _ d i s t + f l y i n g _ d i s t . T
synthetic_spiral generates 3-D spiral dataset. This is a 3× 30 matrix, meaning that there are 30
points in 3-D space. This function can be used as follows:
from Code . d a t a s e t import s y n t h e t i c _ s p i r a l
X _ s p i r a l = s y n t h e t i c _ s p i r a l ( )
Page 4
COMP61021: Representation Learning Ke Chen
bars loads the bar image dataset from Data/bars.npz and returns bar images in row vector and
its center coordinates, and the size of images is 40 × 40. The bar dataset can be loaded and used
as follows:
from Code . d a t a s e t import b a r s
data_bar , c e n t e r s = b a r s ( )
d a t a _ b a r = d a t a _ b a r . T
c e n t e r s = c e n t e r s . T
i m a g e _ s i z e = [ 4 0 , 4 0 ]
face_tenenbaum loads the face dataset from Data/face_tenenbaum.npz. The size of each image
in this dataset is 64 × 64. The images are returned as column vectors, so this dataset can be used
as follows:
from Code . d a t a s e t import face_tenenbaum
d a t a _ f a c e = face_tenenbaum ( )
i m a g e _ s i z e = [ 6 4 , 6 4 ]
1 Multidimensional Scaling
Multidimensional scaling (MDS) is one of manifold learning techniques that learns to preserve the
distance between observations in a high-dimensional source space into a low-dimensional target
space. It has been one of the most commonly used techniques for visualisation.
Given a distance matrix for N points in d-dimensional source space, ∆ = (δij)N×N , MDS is going
to find out low-dimensional representations of N points in a p-dimensional target space (p < d),
Zp×N = {z1, z2, · · · , zN}, such that dij ≈ f(δij), where dij is the distance between points i and j
in the target space and f(·) is a parametric monotonic function, e.g., f(δij) = α + βδij . To solve
the MDS problem, there are several dierent algorithms, e.g., cMDS and stress-based MDS1.
1.1 Classical MDS (cMDS)
For a centralised data matrix, X, its inner-product (Gram) matrix,GN×N = XTX , is expressible by
its distance matrix, ∆2 = (δ2ij)N×N :
G = XTX = −1
2
H∆2H;HN×N = IN×N − 1
N
eeT ,
where IN×N is the identity matrix and e = [11 · · · 1]T
In cMDS, p-dimensional optimal coordinates in the target space can be obtained by conducting
eigen-decomposition on G = XTX . Let Σp is a diagonal matrix consisting of top p eigenvalues
of the Gram matrix, G, and Vp is the matrix of the corresponding N -dimensional eigenvectors,
1For details of the cMDS and stress-based algorithms, see the “Multi-dimensional Scaling (MDS)” lecture note.
Page 5
COMP61021: Representation Learning Ke Chen
v1, v2, · · · , vp. The optimal p-dimensional coordinates ofN data points inX are collected inZ∗p×N
as follows:
Z∗p×N = Σ
1
2
p V
T
p .
Assignment 1 [6 marks] In your answer notebook, complete the function cmds, which imple-
ments cMDS algorithm described above. In your implementation, you can use the built-in func-
tions in Python libraries, e.g., sklearn.metrics.pairwise.euclidean_distances, to calculate
Euclidean distance and numpy.linalg.eigh to conduct eigen decomposition. Apply your com-
pleted cmds code on the ten_city dataset. In your answer notebook, (a) report the first 2 largest
eigenvalues and their corresponding eigenvectors achieved on the dataset, and (b) visualise 1-D
and 2-D embedded points along with the name of 10 cities.
1.2 Stress-based MDS
In stress-based MDS, optimal embedded coordinates are obtained by minimising loss functions
(a.k.a. stress). The Sammon mapping is a well-known stress-based MDS.
Assignment 2 [2 marks] In your answer notebook, implement two functions: loss_sammon and
grad_sammon, which are used to calculate the stress and its gradient in the Sammon mapping al-
gorithm, respectively. In your implementation, you can use the built-in function in scikit-learn,
sklearn.metrics.pairwise.euclidean_distances, to calculate distances between data points.
Assignment 3 [4 marks] Run the provided stress_based_mds function using the two functions
you implement in Assignment 2. In your answer notebook, (a) report the optimal hyperparame-
ters: learning rate (lr) and tolerance (tol) by setting max_iter=6000, (b) explain how you obtain
two optimal hyperparameters with justification, and (c) display 2-D embedding results with the
optimal parameters.
2 Isometric Feature Mapping (ISOMAP)
In the ISOMAP2, geodesic distance is used to overcome the weakness of cMDS where the Euclidean
distance metric does not respect the geometry of a non-linear manifold.
The ISOMAP algorithm consists of two steps:
1. Find out approximate geodesic distances between any points in high-dimensional space.
2. Apply cMDS to the geodesic distance matrix for low-dimensional embedding.
Assignment 4 [4 marks] To gain a geodesic distance matrix, local distances need to be calculated
via one of two ways: i) K-nearest neighbourhood (KNN) or ii) -radius neighbourhood. In your an-
swer notebook, a) implement the fixed_radius_distance, the nearest_neighbour_distance
and isomap functions (where you must re-use your own c-MDS implementation in Assignment 1),
and (b) run your implementedisomap function on the Swiss roll dataset with the given parameters:
2For details of the ISOMAP, see the “Isometric Feature Mapping (ISOMAP)” lecture note.
Page 6
COMP61021: Representation Learning Ke Chen
k=6, epsilon=3.5, target=2-D and display your results. Note that you can use the built-in func-
tion in scikit-learn, sklearn.metrics.pairwise.euclidean_distances, to calculate distances
between data points. However, the use of sklearn.neighbors.NearestNeighbors in your code
is strictly forbidden.
Assignment 5 [2 marks] Run your own isomap code implemented in Assignment 4 on the face
dataset,face_tenenbaum.npz. The routine used for displaying the connectivity between the neigh-
bouring embedded points in low-dimensional space is provided for this dataset in the notebook
file. In the figure showing the connectivity, randomly pick two pairs of start and end points to spec-
ify two shortest paths that reflect meaningful manifold structures underlying this dataset. In your
answer notebook, (a) display the images on the two specific paths you choose with the layout of 5
images in each row, and (b) report the indices of points you choose on each path and explain what
you observe on those points in two paths in terms of manifold learning. To do this assignment, you
may use the provided functions/classes, VIS_Shortest_path_2d for selecting a pair of start and
end points to generate a shortest path, and ImageViewer to display all images on your specified
paths. Nevertheless, you are allowed to show the images with your own display functions.
3 Locally Linear Embedding (LLE)
The LLE3 is yet another method to solve the same problem as ISOMAP encounters. For a given
dataset, Xp×N , a point xi is reconstructed by linear combination of its neighbours xj and optimal
weights,W ∗, can be learned by minimising the following loss function:
L(W ;X) =
N∑
i=1
‖xj −
N∑
j=1
Wijxj‖2 s.t.
N∑
j=1
Wij = 1.
Once the weights are obtained, the points ,xi, can be embedded into target space as p-dimensional
coordinates (p < d), Zp×N = {z∗1, z∗2, · · · , z∗N}, by minimising the loss function with respect to the
embedded coordinates inZ:
L(Z;W ∗) =
N∑
i=1
‖z i −
N∑
j=1
z j‖2 s.t.
N∑
i=1
z i = 0,
1
N − 1
N∑
i=1
z iz
T
i = IN×N .
The p-dimensional optimal embedded coordinates can be obtained by conducting eigen-analysis
onD = (I−W ∗)T (I−W ∗) whereW ∗ is the optimal weight matrix for data reconstruction in high
dimensional source space.
Assignment 6 [4 marks] In the notebook file, you are provided with our LLE implementation in
Python (see Supportive Soware for details):
lle(data, n_components=2, n_neighbors=None, epsilon=None, dist_func=None,
reg_func=None)
3For details of the LLE, see the “Locally Linear Embedding (LLE)” lecture note.
Page 7
COMP61021: Representation Learning Ke Chen
In this assignment, you are asked to apply this function to the S-Curve dataset provided in the
scikit-learn library, sklearn.datasets.make_s_curve, which has been included in the notebook
file. In your experiment, you need to use bothKNN and the fixed radius methods to decide local
neighbourhood of a point. Thus, you need to find proper values for n_neighbors and epsilon, re-
spectively. As an exploratory exercise, you are asked to figure out a criterion that can guide you to
find out the optimal hyperparameters, K and (Note that any trial-and-test criteria are unaccept-
able). In your experiment, apply your criterion to investigate the value ofK taken in the range from
5 to 50 with the increment by 1 forKNN neighbourhood and the value of in the range from 0.1 to
0.8 with the increment by 0.1. In your answer notebook, (a) describe a criterion that works eec-
tively in finding out the optimal hyperparameters,K and ; (b) provide the computational evidence
based on your criterion described in (a) to find out the optimalK and on the S-Curve dataset. (c)
display 2-D embedded coordinates of the S-Curve dataset with the optimal parameters. You can
reuse the distance functions: fixed_radius_distance and nearest_neighbour_distance, you
implement in Assignment 4.
Assignment 7 [3 marks] In this assignment, you are asked to apply the provided LLE function
with KNN neighbourhood to the bar dataset, bars.npz, where there are 1,000 images; 500 ver-
tical and 500 horizontal bars. For this dataset, you must use the provided regularisation function
reg_func and the nearest_neighbour_distance, you implement in Assignment 4 in the lle
function (Note that failing to use these two functions may result in incorrect results). To display
2-D embedding coordinates, you can use the provided VIS_Bars class. In your answer book, (a)
applying the criterion you described in Assignment 6(a), report the optimalK in the range (40 < K
< 60) with computational evidence, (b) display 2-D embedded coordinates of 1,000 bar images us-
ing the optimalK, and (c) describe what you observe from those embedded coordinates in terms
of manifold learning.
Requirement: Before starting working on this assessed coursework, you need to
1. download all the files required by this coursework from Blackboard as specified at the be-
ginning of this document;
2. unzip the file then you should be see a Jupyter notebook file named manifold.ipynb and
two sub-directories named Data and Code, respectively (you must keep this directory/sub-
directory structure and their names unchanged when you work on this coursework);
3. rename manifold.ipynb in the directory as yourfullname_manifold.ipynb. For instance,
if your name is “John Smith”, your filename should be john_smith_manifold.ipynb. This
file will be your answer notebook to be submitted for marking, so you must include every-
thing required by the coursework in this Jupyter notebook.
Deliverable: Only your answer notebook, yourfullname_manifold.ipynb, which should include
all your code, output, answers and your interpretation/justification. In this Jupyter notebook, all
assignments have been separated with the clear delimiters. You must put your stu regarding an
assignment in those cells related to this assignment and, if necessary, create new cells within the
delimiters of this assignment.
Your answer notebook, yourfullname_manifold.ipynb, must be submitted via the Black-
Page 8
COMP61021: Representation Learning Ke Chen
board.
Marking: Marking is on the basis of (1) correctness of results and quality of comments on your
code; (2) rigorous experimentation; (3) how informative and clear your description/answers pre-
sented in your answer book; and (4) your knowledge exhibited, interpretation and justification.
Late Submission Policy: The default university late submission policy (for details, see the of-
ficial document: http://documents.manchester.ac.uk/DocuInfo.aspx?DocID=29825) is ap-
plied to this coursework.
Extension Policy: The default departmental extension policy is applied to this coursework. That
is, no extension is allowed unless you have a mitigating circumstance. If you have any mitigating
circumstance and want to make an extension, you should submit the completed mitigating cir-
cumstance form to SSO (for details, see the departmental Mitigating Circumstances page: http://
studentnet.cs.manchester.ac.uk/assessment/mitigatingcircumstances.php?view=pgt).
Note: the decision will be made by the departmental mitigating circumstance panel rather than the
lecturer.
Deadline: 18:00 GMT, 2nd December 2021 (Thursday)
Page 9
Manifold Learning*
Ke Chen
To carry out this assessed coursework, you will need the Python notebook file, manifold.ipynb,
which contain code to get you started with each of the assignments and the data files: bars.npz
for the bar images and face_tenenbaum.npz for the face images. Other datasets (e.g. ten_city)
are generated by using built-in functions in the notebook. All above are available in a zipped file
on BlackBoard alongside this document.
Caveat: You may not display some resultant figures correctly with %matplotlib notebook which
appears in the first line of the given Jupyter notebook file, especially on MS Windows. To deal with
this issue, you need to use the Firefox browser instead of Chrome, Microso IE and Edge.
Manifold learning is one of the central themes in representation learning. In this coursework, you
are asked to use Python to implement several manifold learning algorithms learnt from this course
and apply your own implementation to synthetic and real datasets for manifold learning.
Supportive Soware
To do this coursework, you are provided with our own Python implementation of LLE and visuali-
sation tools required by this coursework.
Our implementation in Python includes: optimization functions in optimization.py, locally lin-
ear embedding inlle.py, display functions inhelpers.pyand dataset functions indataset.py.
optimization.py enables you to carry out the gradient descent method required for the assign-
ments regarding the stress-based MDS algorithms.
To solve an optimization problem by using the gradient descent method, the signature of this func-
tion is as follows:
gradient_descent(D, x0, loss_f, grad_f, lr, tol, max_iter)
where D is a distance matrix between points in the original space and x0 is an initial value we want
to get. loss_f and grad_f are the loss function and its first derivative or gradient, respectively. lr
and tol are learning rate and tolerance for early stopping. max_iter is the maximum number of
iteration.
In lle.py, the signature of lle function is as follows:
lle(data, n_components=2, n_neighbors=None, epsilon=None, dist_func=None,
reg_func=None)
where data contains data points in the original space, n_components is the dimensionality of tar-
get embedded space, n_neighbors is the number of neighbours for KNN, epsilon is the value of
*Assessed Coursework: the deadline and requirements can be found at the end of this document.
Page 1
COMP61021: Representation Learning Ke Chen
fixed radius for -distance, dist_func is the function to find out neighbours and their distances,
and reg_func implements a regularization term to avoid the singular case.
Below, you can see two examples on how to use thelle function with dierent neighbourhoods.
from Code . l l e import l l e
data = . . . # data po i n t i n the o r i g i n a l space
n_dim = 2
k = 7
Y = l l e ( data , n_components =n_dim , n _ n e i g h b o r s =k ,
d i s t _ f u n c = n e a r e s t _ n e i g h b o r _ d i s t a n c e , r e g _ f u n c = r e g _ f u n c )
from Code . l l e import l l e
data = . . . # data po i n t i n the o r i g i n a l space
n_dim = 2
e = 5 . 3
Y = l l e ( data , n_components =n_dim , e p s i l o n =e ,
d i s t _ f u n c = f i x e d _ r a d i u s _ d i s t a n c e , r e g _ f u n c = r e g _ f u n c )
where KNN is used in the first case and -NN is used in the second case. For the reg_func ar-
gument, the None value can be set except for Assignment 7 where the function reg_func(C, K)
provided in manifold.ipynb must be used.
helpers.pyprovides the useful functions to enable you to visualise the results of each assignment.
This Python module containsVIS_Shortest_path_2dandImageViewer, VIS_Bars classes.
VIS_Shortest_path_2d is used to display not only the embedded points in latent space but also
the shortest path between two specified data points. Its constructor is as follows:
VIS_Shortest_path_2d(proj, dist, predecessors, fig_vis)
where proj refers to the embedded points in the target space, dist and predecessors are dis-
tance matrix and the index of predecessors for the shortest path which are obtained from isomap
function. fig_vis is figure object created by the Python built-in function figure() in the mat-
plotlib package. The usage of this class is as follows:
import m a t p l o t l i b . p y p l o t as p l t
from Code . isomap import isomap , d i s t _ n e a r e s t _ n e i g h b o r
p o i n t s = . . . # data po i n t i n column v e c t o r
n_components = 2
n _ n e i g h b o r s = 6
Y , d i s t , p r e d e c e s s o r s = isomap ( . . . )
f i g = p l t . f i g u r e ( )
V I S _ S h o r t e s t _ p a t h _ 2 d ( Y , d i s t , p r e d e c e s s o r s , f i g )
Page 2
COMP61021: Representation Learning Ke Chen
By using the VIS_Shortest_path_2d, the embedded points in latent space will be plotted. Also,
you can see the shortest path between two selected points.
ImageViewer is used to display images on the shortest path and its constructor is as follows:
ImageViewer(data, index, image_size, fig_vis, max_row=5)
where data refers to data points in the source space, index refers to the indices of points on the
shortest path, image_size is the size of images used in data, fig_vis is a figure object created
by Python built-in function, figure(), in the matplotlib package and max_row is the maximum
number of images in a row. The usage of this class is as follows:
import m a t p l o t l i b . p y p l o t as p l t
data = . . . # data po i n t s i n the o r i g i n a l space
i m a g e _ s i z e = [ 6 4 , 6 4 ]
s t a r t _ i d x = 1
e n d _ i d x = 100
path = g e t _ s h o r t e s t _ p a t h ( p r e d e c e s s o r s , s t a r t _ i d x , e n d _ i d x )
f i g = p l t . f i g u r e ( )
i m g _ v i e w e r = ImageViewer ( data , path , i m a g e _ s i z e , f i g , 5 )
i m g _ v i e w e r . show ( )
where get_shortest_path is provided in manifold.ipynb for Assignment 5 and predecessors
is returned from the isomap function.
VIS_Bars allows you to display the bar images in the dataset, bars.npz, and its result yielded by
the lle function. Its constructor is as follows:
VIS_Bars(data, proj, fig_vis, color=’r’, image_size=(40,40), both=True)
where data are points in the source space, proj are the embedded points yielded by lle, fig_vis
is a figure object created by figure() in the matplotlib package, color is the value of colour to
represent the embedded points in this colour (e.g. ’r’ for red, ’b’ for blue), image_size is the size of
images specified in data, and both is the flag to indicate whether both horizontal bars and vertical
bars appear in data or not. If the last parameter, both, is set as True, the colour parameter, color,
will be ignored. The usage of this class is as follows:
Case 1: set both=True
from Code . d a t a s e t import b a r s
data_bar , c e n t e r s = b a r s ( )
d a t a _ b a r = d a t a _ b a r . T
c e n t e r s = c e n t e r s . T
i m a g e _ s i z e = [ 4 0 , 4 0 ]
Page 3
COMP61021: Representation Learning Ke Chen
n _ n e i g h b o r s = 5
n_components = 2
Y _ b a r = l l e ( . . . )
f i g _ b a r = p l t . f i g u r e ( )
v i s _ b o t h = V I S _ B a r s ( data = data_bar , p r o j = Y_bar , f i g _ v i s = f i g _ b a r ,
i m a g e _ s i z e = i m a g e _ s i z e , both = True )
Case 2: set both=False
from Code . d a t a s e t import b a r s
data_bar , c e n t e r s = b a r s ( )
d a t a _ b a r = d a t a _ b a r . T
c e n t e r s = c e n t e r s . T
i m a g e _ s i z e = [ 4 0 , 4 0 ]
n _ n e i g h b o r s = 5
n_components = 2
Y _ b a r = l l e ( . . . )
f i g _ b a r = p l t . f i g u r e ( )
v i s _ v = V I S _ B a r s ( data = d a t a _ b a r [ : , : 5 0 0 ] , p r o j = Y _ b a r [ : , : 5 0 0 ] ,
f i g _ v i s = f i g _ v _ b a r , c o l o r = ’ r ’ ,
i m a g e _ s i z e = i m a g e _ s i z e , both = F a l s e )
The dataset.pymodule contains functions for loading datasets given in the Data/directory or for
being used as the built-in functions for data generation.
ten_city contains data regarding the distances between 10 U.S.A. cities. This returns a lower trian-
gle part of the distance matrix. The full distance matrix for this dataset can be achieved by adding
this matrix and its transpose as follows:
from Code . d a t a s e t import t e n _ c i t y
f l y i n g _ d i s t , c i t y = t e n _ c i t y ( )
f l y i n g _ d i s t = f l y i n g _ d i s t + f l y i n g _ d i s t . T
synthetic_spiral generates 3-D spiral dataset. This is a 3× 30 matrix, meaning that there are 30
points in 3-D space. This function can be used as follows:
from Code . d a t a s e t import s y n t h e t i c _ s p i r a l
X _ s p i r a l = s y n t h e t i c _ s p i r a l ( )
Page 4
COMP61021: Representation Learning Ke Chen
bars loads the bar image dataset from Data/bars.npz and returns bar images in row vector and
its center coordinates, and the size of images is 40 × 40. The bar dataset can be loaded and used
as follows:
from Code . d a t a s e t import b a r s
data_bar , c e n t e r s = b a r s ( )
d a t a _ b a r = d a t a _ b a r . T
c e n t e r s = c e n t e r s . T
i m a g e _ s i z e = [ 4 0 , 4 0 ]
face_tenenbaum loads the face dataset from Data/face_tenenbaum.npz. The size of each image
in this dataset is 64 × 64. The images are returned as column vectors, so this dataset can be used
as follows:
from Code . d a t a s e t import face_tenenbaum
d a t a _ f a c e = face_tenenbaum ( )
i m a g e _ s i z e = [ 6 4 , 6 4 ]
1 Multidimensional Scaling
Multidimensional scaling (MDS) is one of manifold learning techniques that learns to preserve the
distance between observations in a high-dimensional source space into a low-dimensional target
space. It has been one of the most commonly used techniques for visualisation.
Given a distance matrix for N points in d-dimensional source space, ∆ = (δij)N×N , MDS is going
to find out low-dimensional representations of N points in a p-dimensional target space (p < d),
Zp×N = {z1, z2, · · · , zN}, such that dij ≈ f(δij), where dij is the distance between points i and j
in the target space and f(·) is a parametric monotonic function, e.g., f(δij) = α + βδij . To solve
the MDS problem, there are several dierent algorithms, e.g., cMDS and stress-based MDS1.
1.1 Classical MDS (cMDS)
For a centralised data matrix, X, its inner-product (Gram) matrix,GN×N = XTX , is expressible by
its distance matrix, ∆2 = (δ2ij)N×N :
G = XTX = −1
2
H∆2H;HN×N = IN×N − 1
N
eeT ,
where IN×N is the identity matrix and e = [11 · · · 1]T
In cMDS, p-dimensional optimal coordinates in the target space can be obtained by conducting
eigen-decomposition on G = XTX . Let Σp is a diagonal matrix consisting of top p eigenvalues
of the Gram matrix, G, and Vp is the matrix of the corresponding N -dimensional eigenvectors,
1For details of the cMDS and stress-based algorithms, see the “Multi-dimensional Scaling (MDS)” lecture note.
Page 5
COMP61021: Representation Learning Ke Chen
v1, v2, · · · , vp. The optimal p-dimensional coordinates ofN data points inX are collected inZ∗p×N
as follows:
Z∗p×N = Σ
1
2
p V
T
p .
Assignment 1 [6 marks] In your answer notebook, complete the function cmds, which imple-
ments cMDS algorithm described above. In your implementation, you can use the built-in func-
tions in Python libraries, e.g., sklearn.metrics.pairwise.euclidean_distances, to calculate
Euclidean distance and numpy.linalg.eigh to conduct eigen decomposition. Apply your com-
pleted cmds code on the ten_city dataset. In your answer notebook, (a) report the first 2 largest
eigenvalues and their corresponding eigenvectors achieved on the dataset, and (b) visualise 1-D
and 2-D embedded points along with the name of 10 cities.
1.2 Stress-based MDS
In stress-based MDS, optimal embedded coordinates are obtained by minimising loss functions
(a.k.a. stress). The Sammon mapping is a well-known stress-based MDS.
Assignment 2 [2 marks] In your answer notebook, implement two functions: loss_sammon and
grad_sammon, which are used to calculate the stress and its gradient in the Sammon mapping al-
gorithm, respectively. In your implementation, you can use the built-in function in scikit-learn,
sklearn.metrics.pairwise.euclidean_distances, to calculate distances between data points.
Assignment 3 [4 marks] Run the provided stress_based_mds function using the two functions
you implement in Assignment 2. In your answer notebook, (a) report the optimal hyperparame-
ters: learning rate (lr) and tolerance (tol) by setting max_iter=6000, (b) explain how you obtain
two optimal hyperparameters with justification, and (c) display 2-D embedding results with the
optimal parameters.
2 Isometric Feature Mapping (ISOMAP)
In the ISOMAP2, geodesic distance is used to overcome the weakness of cMDS where the Euclidean
distance metric does not respect the geometry of a non-linear manifold.
The ISOMAP algorithm consists of two steps:
1. Find out approximate geodesic distances between any points in high-dimensional space.
2. Apply cMDS to the geodesic distance matrix for low-dimensional embedding.
Assignment 4 [4 marks] To gain a geodesic distance matrix, local distances need to be calculated
via one of two ways: i) K-nearest neighbourhood (KNN) or ii) -radius neighbourhood. In your an-
swer notebook, a) implement the fixed_radius_distance, the nearest_neighbour_distance
and isomap functions (where you must re-use your own c-MDS implementation in Assignment 1),
and (b) run your implementedisomap function on the Swiss roll dataset with the given parameters:
2For details of the ISOMAP, see the “Isometric Feature Mapping (ISOMAP)” lecture note.
Page 6
COMP61021: Representation Learning Ke Chen
k=6, epsilon=3.5, target=2-D and display your results. Note that you can use the built-in func-
tion in scikit-learn, sklearn.metrics.pairwise.euclidean_distances, to calculate distances
between data points. However, the use of sklearn.neighbors.NearestNeighbors in your code
is strictly forbidden.
Assignment 5 [2 marks] Run your own isomap code implemented in Assignment 4 on the face
dataset,face_tenenbaum.npz. The routine used for displaying the connectivity between the neigh-
bouring embedded points in low-dimensional space is provided for this dataset in the notebook
file. In the figure showing the connectivity, randomly pick two pairs of start and end points to spec-
ify two shortest paths that reflect meaningful manifold structures underlying this dataset. In your
answer notebook, (a) display the images on the two specific paths you choose with the layout of 5
images in each row, and (b) report the indices of points you choose on each path and explain what
you observe on those points in two paths in terms of manifold learning. To do this assignment, you
may use the provided functions/classes, VIS_Shortest_path_2d for selecting a pair of start and
end points to generate a shortest path, and ImageViewer to display all images on your specified
paths. Nevertheless, you are allowed to show the images with your own display functions.
3 Locally Linear Embedding (LLE)
The LLE3 is yet another method to solve the same problem as ISOMAP encounters. For a given
dataset, Xp×N , a point xi is reconstructed by linear combination of its neighbours xj and optimal
weights,W ∗, can be learned by minimising the following loss function:
L(W ;X) =
N∑
i=1
‖xj −
N∑
j=1
Wijxj‖2 s.t.
N∑
j=1
Wij = 1.
Once the weights are obtained, the points ,xi, can be embedded into target space as p-dimensional
coordinates (p < d), Zp×N = {z∗1, z∗2, · · · , z∗N}, by minimising the loss function with respect to the
embedded coordinates inZ:
L(Z;W ∗) =
N∑
i=1
‖z i −
N∑
j=1
z j‖2 s.t.
N∑
i=1
z i = 0,
1
N − 1
N∑
i=1
z iz
T
i = IN×N .
The p-dimensional optimal embedded coordinates can be obtained by conducting eigen-analysis
onD = (I−W ∗)T (I−W ∗) whereW ∗ is the optimal weight matrix for data reconstruction in high
dimensional source space.
Assignment 6 [4 marks] In the notebook file, you are provided with our LLE implementation in
Python (see Supportive Soware for details):
lle(data, n_components=2, n_neighbors=None, epsilon=None, dist_func=None,
reg_func=None)
3For details of the LLE, see the “Locally Linear Embedding (LLE)” lecture note.
Page 7
COMP61021: Representation Learning Ke Chen
In this assignment, you are asked to apply this function to the S-Curve dataset provided in the
scikit-learn library, sklearn.datasets.make_s_curve, which has been included in the notebook
file. In your experiment, you need to use bothKNN and the fixed radius methods to decide local
neighbourhood of a point. Thus, you need to find proper values for n_neighbors and epsilon, re-
spectively. As an exploratory exercise, you are asked to figure out a criterion that can guide you to
find out the optimal hyperparameters, K and (Note that any trial-and-test criteria are unaccept-
able). In your experiment, apply your criterion to investigate the value ofK taken in the range from
5 to 50 with the increment by 1 forKNN neighbourhood and the value of in the range from 0.1 to
0.8 with the increment by 0.1. In your answer notebook, (a) describe a criterion that works eec-
tively in finding out the optimal hyperparameters,K and ; (b) provide the computational evidence
based on your criterion described in (a) to find out the optimalK and on the S-Curve dataset. (c)
display 2-D embedded coordinates of the S-Curve dataset with the optimal parameters. You can
reuse the distance functions: fixed_radius_distance and nearest_neighbour_distance, you
implement in Assignment 4.
Assignment 7 [3 marks] In this assignment, you are asked to apply the provided LLE function
with KNN neighbourhood to the bar dataset, bars.npz, where there are 1,000 images; 500 ver-
tical and 500 horizontal bars. For this dataset, you must use the provided regularisation function
reg_func and the nearest_neighbour_distance, you implement in Assignment 4 in the lle
function (Note that failing to use these two functions may result in incorrect results). To display
2-D embedding coordinates, you can use the provided VIS_Bars class. In your answer book, (a)
applying the criterion you described in Assignment 6(a), report the optimalK in the range (40 < K
< 60) with computational evidence, (b) display 2-D embedded coordinates of 1,000 bar images us-
ing the optimalK, and (c) describe what you observe from those embedded coordinates in terms
of manifold learning.
Requirement: Before starting working on this assessed coursework, you need to
1. download all the files required by this coursework from Blackboard as specified at the be-
ginning of this document;
2. unzip the file then you should be see a Jupyter notebook file named manifold.ipynb and
two sub-directories named Data and Code, respectively (you must keep this directory/sub-
directory structure and their names unchanged when you work on this coursework);
3. rename manifold.ipynb in the directory as yourfullname_manifold.ipynb. For instance,
if your name is “John Smith”, your filename should be john_smith_manifold.ipynb. This
file will be your answer notebook to be submitted for marking, so you must include every-
thing required by the coursework in this Jupyter notebook.
Deliverable: Only your answer notebook, yourfullname_manifold.ipynb, which should include
all your code, output, answers and your interpretation/justification. In this Jupyter notebook, all
assignments have been separated with the clear delimiters. You must put your stu regarding an
assignment in those cells related to this assignment and, if necessary, create new cells within the
delimiters of this assignment.
Your answer notebook, yourfullname_manifold.ipynb, must be submitted via the Black-
Page 8
COMP61021: Representation Learning Ke Chen
board.
Marking: Marking is on the basis of (1) correctness of results and quality of comments on your
code; (2) rigorous experimentation; (3) how informative and clear your description/answers pre-
sented in your answer book; and (4) your knowledge exhibited, interpretation and justification.
Late Submission Policy: The default university late submission policy (for details, see the of-
ficial document: http://documents.manchester.ac.uk/DocuInfo.aspx?DocID=29825) is ap-
plied to this coursework.
Extension Policy: The default departmental extension policy is applied to this coursework. That
is, no extension is allowed unless you have a mitigating circumstance. If you have any mitigating
circumstance and want to make an extension, you should submit the completed mitigating cir-
cumstance form to SSO (for details, see the departmental Mitigating Circumstances page: http://
studentnet.cs.manchester.ac.uk/assessment/mitigatingcircumstances.php?view=pgt).
Note: the decision will be made by the departmental mitigating circumstance panel rather than the
lecturer.
Deadline: 18:00 GMT, 2nd December 2021 (Thursday)
Page 9
