PHYS3888 Take-Home Exam. S2, 2021: Mordor.
How to do this exam
You may use any existing resource to solve the problems in this paper, including the lecture
notes, code you’ve already written, Matlab documentation (e.g., use doc if you are unsure of
syntax), and Google searches.
However, during the period in which this exam is active, YOU MAY NOT have any
communication with any other person about any aspect of it.
Make sure that you have downloaded the code and data that accompanies this exam.
Note that the difficulty of questions is unevenly distributed through the paper. It can be a good
strategy to skip questions you are initially stuck on.
Please leave yourself plenty of time (approximately 1 hour) to upload a pdf containing all of
your answers. You may use a mix of scanned images of pen-and-paper work and any typeset
results, or images.
You are encouraged to provide code where relevant (e.g., which can allow for partial marks to be
awarded when final results are incorrect). To aid readability, please present code in a fixed-width
font (e.g., like Monaco).
You have a total of 24 hours, so do not risk missing the deadline due to scanning/upload issues.
Statement of individual contribution
[Statement] (×0 multiplier on final score if incomplete)
To have a valid exam, you must accurately complete this question:
Copy out and sign the following statement: “The results submitted in this exam are my own
work only. I had no communication with any other person about any aspect of it.”
Setting
We are in Mordor: a land of orcs, ogres, and desolate evil. And yet, amidst the moral devastation,
there is one shining light: interdisciplinary physics.
1
Part A: Nazgul (25 marks)
Nazgul fly about Mordor, searching the land below for The One Ring.
We have obtained a dataset of their flight pattern, which you can load in as:
load('examData.mat','nazgulFlight');
The variable, nazgulFlight, contains x- and y- coordinates (columns 1 and 2, respectively)
corresponding to the set of locations that the Nazgul visited. Coordinates are measured in
kilometers, with Mount Doom at the origin. Locations were visited in the order presented down
the rows (e.g., the first location is the first row of nazgulFlight, the second location the second
row, etc.).
A1: Birds-eye view (5 marks)
[A1.1] (1 mark)
What are the (x, y) coordinates of the first location the Nazgul visited?
[A1.2] (1 mark)
How many other locations did the Nazgul subsequently visit?
[A1.3] (1 mark)
Run:
A = nazgulFlight(1:100,:);
State what the rows and columns of A correspond to.
[A1.4] (2 marks)
Plot the trajectory of Nazgul flight for the first 100 locations visited. Plot each location as its x
and y coordinates. Use a marker to denote locations and use lines to join consecutively visited
locations. Provide your plot.
A2: Power-laws in Nazgul flight (12 marks)
Compute a set of distances, dist, using the computeDistances function provided:
dist = computeDistances(nazgulFlight);
2
[A2.1] (2 marks)
By reading the lines of code in computeDistances, identify what information is stored in dist.
If N locations were visited, state why dist will be a vector of length N − 1.
[A2.2] (1 mark)
Notice the calculation sqrt(sum((y - x).ˆ2)) in computeDistances.m. Write down this
calculation in the form of a mathematical equation: d(x, y) = . . ..
[A2.3] (3 marks)
Using the function provided, binLogLog.m, plot the distribution of dist on logarithmic axes
with 10 bins.
[A2.4] (1 mark)
What feature of your plot indicates that the distances, dist, follow a power-law distribution,
p(x) ∝ x−γ?
[A2.5] (2 marks)
From the logarithmic binning above, estimate the power-law exponent, γ, to two significant
figures. Provide your code with your result.
[A2.6] (3 marks)
Speculate briefly on the scale-free distribution of distances in the context of Nazgul flight:
1. Explain qualitatively what the trajectory of Nazgul flight would look like if the distribution
of dist instead had a characteristic scale (was a unimodal distribution).
2. Speculate about a possible advantage of the scale-free distribution of dist for the Nazgul
to search for The One Ring.
A3: Nazgul are sooo random (8 marks)
In this section we aim to assess the structure of Nazgul flight patterns by comparing the distances,
dist, to those computed from random flights between the same set of locations.
Randomize the ordering of the locations visited as nazgulRand:
rng('default');
N = size(nazgulFlight,1);
nazgulRand = nazgulFlight(randperm(N),:);
[A3.1] (4 marks)
Use computeDistances to compute distances between the randomized locations, nazgulRand,
storing your result in the variable, distRand.
Plot the probability distribution of distRand as a histogram on linear axes, and again on
logarithmic axes.
Explain any relevant features of your plot, focusing on any important differences from the
power-law distribution of dist.
Use your results to assess whether the flight data in nazgulFlight are consistent with random
flights between the same set of locations.
[A3.2] (4 marks)
3
We can further investigate non-random structure in Nazgul flight by analyzing the angular
dependence of successive flight directions. Recall that for a random walk, the direction flown to
next location (from location xi → xi+1) is independent of any prior information, including the
direction from the previous location to the current location (xi−1 → xi).
Extract a vector of angles between successive locations in nazgulFlight, as θi (e.g., using the
atan2 function). Produce a scatter plot of θi+1 as a function of θi.
Provide your code and your plot.
Use your plot to assess whether angles between successive locations are independent.
Part B: Hebbian orc antics (21 marks)
The orcs guarding a key tower in Mordor enter 6× 6 binary patterns into the security control
pad shown below.
Recall that the binary Hopfield network sets network weights according to the Hebbian learning
rule,
wij =
N∑
n=1
x
(n)
i x
(n)
j , (1)
for neural states x ∈ {−1, 1} across a set of N memories.
Note that binary patterns across each key in the 6× 6 grid can be coded as a 36-long binary
vector, allowing passcodes to be represented as memories in a Hopfield network containing 36
neurons. Orcs, being quite forgetful, have trouble remembering their codes and rely on such a
Hopfield network to correct any errors in partial memories of their passcodes.
B1: The Hebbian Learning Rule (7 marks)
The Hebbian learning rule gives high positive weights, wij , to pairs of correlated neurons.
[B1.1] (1 mark)
In this context, describe what it means for two neurons to be correlated.
[B1.2] (1 mark)
Identify what it means about a pair of neurons, i and j, if wij < 0.
4
[B1.3] (2 marks)
If the learning rule, Eq. (1), were modified to take an average rather than a sum, as
wij =
1
N
N∑
n=1
x
(n)
i x
(n)
j ,
what effect would it have on the network weights and resulting behavior? Briefly explain your
answer.
[B1.4] (3 marks)
Recall the rule for updating neural states, x ∈ {−1, 1}, as a function of the neuron activation, a:
x(a) = 1 if a ≥ 0 ,
x(a) = −1 if a < 0.
Consider an alternative rule, in which neural states instead take values x ∈ {−1, 2}, and the
update rule is modified changed to (change shown bold):
x(a) = 2 if a ≥ 0 ,
x(a) = −1 if a < 0.
Briefly explain what effect (if any) this change would have on:
1. The computation of correlations, wij , and
2. The network’s dynamics.
B2: Samwise Sabotage (7 marks)
The hobbit, Samwise, watches carefully as the head orc, Murzush, retrieves his passcode. Samwise
notes down Murzush’s correct passcode as x(Murzush)i , with xi ∈ {−1, 1}. Samwise decides to
sabotage the recall device by entering a new memory that will make Murzush’s passcode less
stable in the network. His aim is to input the most deceptive possible memory using the strategy
of neutralizing any correlations that are informative of Murzush’s passcode, x(Murzush)i .
First consider the case where the network weights have been computed, from Eq. (1), using just
a single memory, x(Murzush)i . Samwise thus aims to construct a second memory, x
(Sam)
i , with the
aim of cancelling out the correlation structure of Murzush’s memory. The optimal such memory
would, after computing Eq. (1) across both memories, result in wij = 0 for all i, j.
[B2.1] (2 marks)
A physicist from UNSW suggests that the problem is trivial. To cancel out Murzush’s memory,
you should construct a new memory, x(Sam)i , that is the opposite of Murzush’s memory, as
x
(Sam)
i = −x(Murzush)i . Briefly explain why this would be a poor strategy. Include in your answer
whether any worse strategies exist (and, if so, describe them).
[B2.2] (3 marks)
Consider the first four elements of Murzush’s memory, shown below. The first two neurons are
‘on’ (x1 = 1, x2 = 1), and the next two neurons are ‘off’ (x3 = −1, x4 = −1). All pairwise
products, xixj , are annotated.
5
We can score the quality, Q, of possible states, x(Sam)i , as the number of unique weights, wij ,
i 6= j, for which wij = 0 (computed after both Murzush and Samwise’s memories).
Write down a set of the four states of x(Sam)i (i.e., for i = 1, . . . , 4), for which Q is maximal.
State whether it is possible to completely neutralize the correlations in this four-state system,
and describe whether your results provide some intuition about how the Hopfield network can
robustly store different memories.
[B2.3] (2 marks)
Consider an alternative setting in which, as well as Murzush’s passcode, the network weights were
computed from the passcodes of many other orcs. Samwise has knowledge of: (i) the resulting
weights, wij , computed from all the passcodes; and (ii) Murzush’s passcode.
Relative to having knowledge of just Murzush’s passcode, qualitatively describe how Samwise
could use knowledge of wij from the full set of orc memories to more effectively sabotage
Murzush’s passcode.
B3: The Weight is Over (7 marks)
Samwise sneaks up to the device and extracts the Hebbian weight matrix, computed using Eq.
(1) from the passcodes of many orcs.
Load the data as:
load('examData.mat','weightMatrix')
[B3.1] (2 marks)
Does weightMatrix encode a directed or undirected network? Briefly state why.
Is your result consistent with the mathematical formulation of the Hebbian rule, Eq. (1)?
[B3.2] (1 mark)
Compute the following:
adjMatrix = (abs(weightMatrix) > 3);
Describe in words what elements labeled 1 in adjMatrix correspond to.
[B3.3] (2 marks)
Compute the minimum degree, kMin, of the neurons represented in adjMatrix, and the index of
the node with minimal degree. State in words what this tells you about this neuron.
[B3.4] (2 marks)
Calculate the number of edges in the network represented by adjMatrix. Provide your code and
its result.
6
Part C: Predicting defectors (14 marks)
When new orcs arrive in Mordor from other parts of Middle Earth, they are checked on entry for
their likelihood of integrating into the Mordor’s evil way of life. The system involves two tests:
(i) a personality test measuring the orc’s propensity for following evil orders (evilness), and (ii)
an index of loyalty by measured as the amount of sweat produced on being shown an image of
Dark Lord Sauron (loyalty). The system aims to classify a new orc as either 'enter' (the orc
can enter Mordor) or 'eliminate' (the orc should be executed).
The mastermind of the entry system, an orc data scientist named Korcaa, uses a single neuron to
map orcs from a two dimensional space (evilness–loyalty) to a predicted outcome ('enter'
versus 'eliminate'), from a training set obtained by analyzing the integration of 100 orcs
recently admitted into Mordor.
C1: Down hill from here (6 marks)
Expressing each training example as {x(n)}100n=1, and each outcome {t(n)}100n=1, the single neuron
outputs a prediction,
y(x;w) = 11 + exp(−w · x) .
[C1.1] (4 marks)
To train the classifier, Korcaa uses the error function we wrote down in lectures:
G(w) = −
∑
n
[
t(n) ln y(x(n);w) + (1− t(n)) ln(1− y(x(n);w))
]
.
Show that
∂G
∂wj
=
∑
n
−(t(n) − y(n))x(n)j .
[C1.2] (2 marks)
Explain what this quantity, ∂G/∂wj , is, and why it is useful to compute.
7
C2: One size fits all (8 marks)
For her training dataset, Korcaa notices that the two types of orcs ('enter' versus 'eliminate')
can be separated perfectly by a single linear boundary. Following the iterative weight update
rule, ∆wi = η(t − y)xi, Korcaa notices that the magnitude of the weights increase with each
iteration, specifying a separation boundary that approaches a step function with increasing
update iterations.
[C2.1] (2 marks)
For the single-neuron classifier, explain why a learning rule that yields weights that grow in
magnitude without bound is an example of over-fitting.
[C2.2] (2 marks)
One way to avoid this over-fitting behavior is to add a new term, E(w), to the previous error
function, G(w), as follows:
M(w) = G(w) + E(w) , (2)
where E(w) = α2
∑
j w
2
j for a constant, α ≥ 0.
Compared to simply minimizing errors (by minimizing G), explain what different behavior
minimizing M will have. Identify why this behavior can be desirable.
[C2.3] (2 marks)
Compute the derivative ∂E/∂wj .
Interpreting your result, describe why M is referred to as a ‘weight decay’ modification of G.
Explain the qualitative effect of setting low versus high values of α.
[C2.4] (2 marks)
In general settings, explain why a learning rule that guards against over-fitting (such as the one
based on M), can produce improved performance on new data.
Part D: We found in love in a hopeless place (19 marks)
D1: Devotion (12 marks)
8
Spathu and Turge are Mordor’s sweetest couple. Their devotion to the Dark Lord Sauron can be
represented as S and T , for Spathu and Turge, respectively. A dynamical model for how S and
T vary over time can be written as:
dS
dt
= aT , (3)
dT
dt
= bS , (4)
for two real-valued parameters, a and b.
Positive values, S > 0 or T > 0, indicate devotion to Dark Lord Sauron, whereas negative values,
S < 0 or T < 0, indicate disapproval of Sauron’s leadership.
Consider the system for a = −4 and b = −1.
[D1.1] (1 mark)
Describe in words what it means to set a < 0.
[D1.2] (1 mark)
Given the specific values of a and b above, does Spathu have a greater impact on Turge’s devotion
to Sauron, or does Turge have a greater impact on Spathu’s devotion?
[D1.3] (3 marks)
Write the dynamics equations in matrix form and compute the trace, τ , and determinant, ∆, for
this system. Use your results to compute the resulting eigenvalues, λ1 and λ2.
What qualitative dynamics will this system display?
[D1.4] (2 marks)
Show that the two eigenvectors are v1 = (1,− 12 ), v2 = (1, 12 ).
Which eigenvector(s) correspond to stable directions of the flow? Briefly justify your answer.
[D1.5] (3 marks)
Plot lines corresponding to v1 and v2 in S–T space. Produce your plot by hand (not as the
output of plotting software).
Include on your plot a trajectory of the system with initial condition S(t = 0) = 1, T (t = 0) = 0.
Interpret this trajectory in words in terms of the interactions defined above. Start your answer
with: “While Turge initially feels neutral towards Sauron, . . . ”
[D1.6] (2 marks)
For S(t = 0) = 1 and T (t = 0) = T0, about what critical value of T0 does the long-term
qualitative behavior of S and T change? Explain your reasoning.
D2: Orcs are sensitive creatures (7 marks)
The love shared between the married couple, Spathu and Turge, x, varies with the pheromone
levels, r, excreted near their home by a local family of Morgai flies.
We can write a dynamical model for x, where x = 0 reflects neutral feelings between Spathu and
Turge, x > 0 reflects a loving relationship, and x < 0 reflects resentment between the couple.
9
The relationship between the equilibrium state of x for a given value of the control parameter, r,
can be represented by the following bifurcation diagram:
[D2.1] (1 mark)
Over what range of r is the system multi-stable?
[D2.2] (2 marks)
Spathu and Turge fell in love (x > 0) during a period of high pheromone levels, r > r2.
Assuming minimal other factors affecting x, explain what this model predicts will happen to
their relationship as r decreases to r ≈ 0.
Assuming a constant rate of decrease, r(t), include a (hand-sketched) plot of x(t) in your answer.
[D2.3] (2 marks)
With pheromone levels staying low, r ≈ 0, Spathu enlists a Cargath marriage counsellor to boost
their relationship. Model the effect of the councillor as a perturbation, x → x + ∆x, where
∆x = x+.
What does the model predict will happen to their relationship?
Assuming an initial x = 0, over what range of r does the model predict that the Cargath
counsellor will save the relationship?
[D2.4] (2 marks)
Pheromone levels start to increase from r ≈ 0 to r > r2, and then decrease back to the range
r1 < r < r2. Spathu and Turge find themselves in constant conflict, x < 0.
They again enlist the Cargath marriage councillor, x→ x+ ∆x.
For what r in this range does ∆x = |x−| guarantee a lasting improvement in x?
Is it possible for more intensive counseling, ∆x > |x−|, to turn the relationship back to a healthy
and happy one (x > 0)?