How to optimize text entry (Assignment Problem)

Thie paper review is written mainly referring to Assignment Problems for Optimizing Text Input (Anna Feit's dissertation).
텍스트 인풋에 최적화에 대한 논문을 영어로 리뷰하여 작성하였습니다.
Feit, A. M. (2018). Assignment Problems for Optimizing Text Input.

01. Introduction (WPM & Usability)

Optimizing Text Input

How to optimize text input has been a long-time concern in the HCI field. Nowadays, The design of the text input methods is still largely the same, characters are spatially arranged into Qwerty. but not suitable for every device and interaction technique, it influences efficiency, ergonomics, and learnability. The following is about WPM(word per minute) in various keyboards.

Qwerty keyboard - 100 WPM
Mini-Qwerty - 60 WPM
Soft keyboards on a smartphone - 30-40 WPM
Smartwatch - 10-20 WPM
Remote pointing on a large screen - 13-19 WPM
Chording keyboard - 180-225 WPM (but intensive training over several years)
Speech - hands-free input is desirable. but cannot be reached in practice.
Via gaze or head tracking - successful in allowing mobility impairments people to interact with computers, but slow and cumbersome.

There are A-Z, and space key. If we think of the assignment of each symbol to input actions, there are about 27! (>10^(27)) possible assignments.
Then, what is the best assignment of symbols to input actions, minimizing the cost of text input among about 10^(27) assignments!
(Actually, there are over 100 special characters...)

02. Challenges

Our goal is to design better text input methods that allow entering text efficiently with little effort.

Optimization is a mathematical or algorithmic method to find the best design in the space. 
1. It requires to search very large design spaces.
2. The process needs to be efficient and rigorous.
3. It also needs quantitative guarantees on the goodness of the outcome.
4. Finally, we need to consider trade-off different criteria and constraints.

Consequently, there are 3 big challenges.
1. Formulation - Establishing the assignment problem as a general model for designing any text input method.
2. Objective function - Formulating objective functions for evaluating the goodness of text input methods beyond keyboard layouts.
3. Optimization - Advancing the empirical understanding of motor behavior during text input in order to formulate and instantiate objective functions.

3 big challenges.

03. Formulation

“ Given a set of N symbols and M input actions, what is the assignment of symbols to actions that maximize the cost of text input? ”

It can be modeled in a linear or a quadratic function. To formulate it, we need to define 3 aspects.
1. The decision variables
2. The constraints that determine which combination of decisions forms a valid solution.
3. The objective functions that determine how to evaluate goodness.

Firstly, formulate decision variables.
Symbol: i / Action: k -> assignment

Formulate decision variables.

Secondly, formulate constraints.

Formulate constraints

Lastly, formulate objective functions.

Formulate objective functions

However, there is not a single globally optimal design but a set of Pareto-optimal solutions.
So, we need to consider multi-objective optimization by creating single F*(x): objective function using F(x) and weight / O: the number of objective functions. (weights: can be tuned by empirical observations or statistics.)

Priori method.

The shortcoming of priori method.
preferences of stakeholders: vague or incomplete. can be changed during the process
normalization does not consider distributions of the scores -> can be biased.

But easy to implement, allows intuitive expression of the tradeoffs between objectives, does not decrease performance, and can be used for Pareto-optimal solutions.

04 Objectives

So far, we could know how to formulate objective functions basically, but we need to study further to get exact objective function on each criterion. However, it requires us to consider a lot of variants because text entry is a complex task involving cognitive and motor processes. For example, fast performance involves more than quickly pointing from one key to another.(Different performance factors / tasks / skill levels / strategies)

Consequently, we need to make objective functions in each criterion and find a Pareto-optimal solution by optimizing such objectives.

Motor Performance –Fitts’ law weighted by letter pair frequency
Learnability - QWERTY similarity [Dunlop & Levine 2012]
Ergonomics – Muscle fatigue or Strain
Noise - Word or gesture clarity [Dunlop & Levine 2012, Smith, Bi & Zhai 2015]

Anna suggests specific approaches and guidelines about the above criteria in her paper.

05 Optimization

There are two ways of optimization. Heuristic approximation algorithms and Mathematical, exact methods.
Let's compare them one by one.

Heuristic approximation algorithms.

Traditional design process: rely on creativity, heuristics, prior experience, subjective feedback. 
-> However, the design space is commonly very large.
ex) Simulated annealing, Genetic algorithms, Biology inspired algorithms etc. 

Pros
- Straightforward to implement and standard implementations available
- Flexible, e.g. combine with simulation models

Cons
No bounds or guarantee to find the global optimum 
Potentially slow
Formulation of design space and constraints

Mathematical, exact methods.

systematic way of automatically creating and evaluating millions of solutions.
-> However, optimization only supplements the manual design process. It relies on designers or researchers to define the design problem(mathematically). Therefore, the definition of work for the design of text input methods is the principal goal behind the thesis.
ex) Linear or Integer Programming, Branch and Bound methods

Pros
Explicit bounds and guarantees on optimality
Fast solvers available, e.g. Gurobi, CPLEX (IBM)

Cons
The objective function in closed mathematical form
Not so flexible (e.g. noisy input data, interactive optimization, multi-objectives, etc. )

 

This is just a summary and review of Anna's paper, I'm really thankful for her super-kind explanation in her dissertation sincerely.