1
ELEC-E7851 Computational User Interface Design, Period II/2019
Aalto University

Assignment 5: Probabilistic Decoding
General instructions: There are three tasks in this assignment, each worth 5 points.
Like always, you can choose which tasks you want to return. If in doubt, I recommend
Preparations:
A5.zip from Materials on MyCourses page. Note, this file is slightly different
from the previous one. The right file is DecodingTutorial_assignment.ipynb.
2. Prepare: Read (really, do!) the paper Statistical_Decoding_Kristensson.pdf (in
the folder Materials/Readings on MyCourses page).
3. Choose the tasks you want to attend to. Note that Tasks 5.2. and 5.3. are done
4. Reporting instructions: Same as in previous Assignment.

Task 5.1. Completing the notebook – Pruning, Log Probability and
Language Model (5 points + 2 extra points) [EASY]
Your goal is to learn accomplish the missing pieces of the Jupyter notebook. Note: you
have to submit both PDF file and the notebook file if you pick this task.

5.1(a) - Pruning:
Following the Beam Pruning section, please create a loop for observing how the
beam_width affects number of tokens and computation time. Plot your results in two
figures, then answer the following question.

The task is as described in the ASSIGNMENT 2.1 (a) box in the Jupyter notebook in
section Beam Pruning.

Reporting: In your PDF report, you have to include (1) the program section you wrote
for this task, (2) the two plots, and (3) answer of the two questions. You also have to
submit the notebook file.
Grading: +1 If you write the code and plot results correctly. +1 if the answers to the
questions are both correct.

2
5.1(b) – Log Probability:
Please move on to the “log probability” section, and modify the code so that all the
probability into log probabilities except for printing out the results.

There are four small parts require modification: (1) The beam values store in the Obser-
vationSequence_log class should initialized as log p, (2) in the beam_prune_log func-
tion, all the calculation should be log p, (3) in propagate_log function, acc_prob should
be log p, and (4) the initial seed_token should starts with a log p.
Reporting: In your PDF report, you have to include the printed outcome.
print_sorted_tokens(results) and print_sorted_log_tokens(results) should result in
the same token sequence. You also have to submit the notebook file.
Grading: +1 If you write the code correctly. +1 if the report is correct.

5.1(c) – Recap Probabilistic Decoding:
Consider there’s another deterministic decoder which does NOT contain probability nor
multiple hypotheses, ie, after the decoder receives a single observation (x,y), it calculates
the nearest key, and updates the hypothesis based on that.
Take our four-keys keyboard used in notebook as an example. If two observation
o1(0.1, 0.1) and o2(0.1, 1.1) are received by the deterministic decoder, o1 will be seen as
letter “a” because “a” is the nearest key, and o2 will be seen as “b” for the same reason.
The decoder will generate only one hypothesis “ab” after these two observations.
Question: What are the limitations of such a deterministic decoder?
Please compare the design principles of the deterministic decoder to the statistical de-
coder we implemented in the lecture, and point out at what situations the deterministic
decoder will fail.
Reporting: Provide the answers to the question on the PDF report.

5.1(d) – Implementation of Language Model (extra 2 points):
In the lecture, we didn’t cover the Language Model section due to time limit. There are
two exercises (Exercise 3 and 4) in the remaining parts of the notebook. It’s encouraged
to finish them. You may earn one extra point for each exercise.

3

Reporting: Provide the Jupyter notebook with the corresponding implementation.
Grading: +1 if exercise 3 is done and correct. +1 if exercise 4 is done and correct.

Task 5.2. Key Target Resizing (5 p) [Hard] [MATLAB]
Note that this exercise is NOT done in the Jupyter notebook but in Matlab. You can
however use ideas from the notebook in your solution. In this exercise the task is to im-
plement an autocorrection algorithm using a technique called key target resizing, which com-
bines both language and touch modeling.
Goals: Your goal is to combine a touch model – Gaussian distributions centered on the
key – and a 3-gram language model to predict the entered words for some noisy text da-
ta. This is a simplified version of how modern soft keyboards work. We provide the cen-
tre points of all the keys, and a function language_model that gives the probability of a
string of three characters. You should implement a touch model that computes the char-
acter probabilities, and a correction function that combines the output of the trigram
function and your touch model to predict the correct letter for each key press in the pro-
vided data. The more correct the characters in the testdata set (see below), the better.
Materials: The format of the data is as follows:
• The variable layout contains the keyboard layout. Each row is a single key, de-
scribed as [upper left corner x, upper left corner y, width, height]. The keyboard
has the keys A-Z in standard QWERTY order from an English keyboard. The
last key is the space bar.
• The variable trainingdata is a structure with 75 sentence objects. Each object has
the fields stimulus (the text that was supposed to be entered), entered (what was
actually typed), and touches (an array of x,y positions for the touches the user
gave).
• The variable testdata contains 25 arrays, each one containing (x,y) positions for
touches in a sentence. You should evaluate your algorithm on these sentences
and give the predicted text.
Starting point: A basic key target resizing algorithm works as follows:
1. Keep track of the last two characters you predicted
2. For each touch, compute the language model probability for the two previous
characters plus each possible character (this will give you 27 probabilities)
3. Compute the probability from your touch model for each possible key (another
27)
4. Multiply the language and touch probabilities to get an overall score for each key.
5. Predict the most likely key
Hints: the MATLAB function mvnpdf will help you implement a 2D Gaussian touch
model. Since there is not a lot of training data, it is ok to set the parameter sigma to the
same for each key. Experiment with different values to see how the accuracy changes.
4
Report and submission: You should include all necessary source code to recreate your
output, and a pdf report detailing any important implementation decisions, the error rate
on the training data, the output of your algorithm on the test data provided, and discus-
sion of any limitations of the approach you used.
• A research paper on key target resizing (IUI’10): http://bit.ly/1scfQTS

Task 5.3. Word-Gesture Keyboard (5 p) [Hard] [MATLAB]
Note that this exercise is NOT done in the Jupyter notebook but in Matlab. You can
however use ideas from the notebook in your solution.
Goal: This assignment introduces you to the principles of gestural input on touchscreen
devices. Your task is to construct an algorithm that maps a continuous gesture on a virtual key-
board to a word. The more accurately this can be done, the better.
Materials: We define a “gesture” as a continuous finite-length trajectory on a virtual key-
board. See the materials below for the idea. A gesture is here represented as an array of
x-y positions (no timestamp). We give an English dictionary, center coordinates of each
key, and a set of gestures. Your task is to map given gestures to English words. The ob-
jective is to maximize the accuracy of mapping.
You are given the following:
1) A file main.m that displays a keyboard on the screen. To draw a gesture, move
to the start position, click the mouse once, draw your gesture over the letters,
then click again when you are over the final letter. This will save the recorded
mouse points into a matrix.
2) A function estimation.m that takes the vector trackdata created by the main.m
script and the dictionary and tries to match the gesture to a word. This function is
partially implemented – your task is to fill in the gaps in the file. There are instructions on what
code should be added to finish it.
3) Various supplementary code - you should not need to interact with this.
Hints: The main challenge here is deciding on a way to score words in the dictionary
based on how well they match the gesture. A very basic example is counting the propor-
tion of letters that appear in both the gesture and the word. More complex scoring
methods will likely give better results.
Submission: You should submit:
1. Full implementation including estimation.m and other files if needed.
2. A PDF report showing the output of your algorithm on gestures for the phrase ‘a
force from above’. You should do the gestures one word at a time without in-
cluding space. Include screenshots of the gestures you made, and the top 3 words
from your estimation function for each gesture.  