1 ELEC-E7851 Computational User Interface Design, Period II/2019 Aalto University Yi-Chi Liao (If there’s any question, please contact:
[email protected]) 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 doing Task 5.1. Preparations: 1. Download the notebook (the whole zip file) named ProbabilisticDecoding- 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 with Matlab and are more advanced than Task 5.1. 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. Grading: +1 If the answer is correct. 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. Additional materials: • Word-gesture keyboards review: http://bit.ly/2fg0gqw • Swype keyboard review: http://bit.ly/2e0PkRq • Word-gesture keyboard applied to mid-air text entry: http://bit.ly/2fD3sAQ
