Assignment Problems for Optimizing Text Input

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering | Doctoral thesis (article-based) | Defence date: 2018-06-11
Degree programme
182 + app. 56
Aalto University publication series DOCTORAL DISSERTATIONS, 103/2018
Text input methods are an integral part of our daily interaction with digital devices. However, their design poses a complex problem: for any method, we must decide which input action (a button press, a hand gesture, etc.) produces which symbol (e.g., a character or word). With only 26 symbols and input actions, there are already more than 10^26 distinct solutions, making it impossible to find the best one through manual design. Prior work has shown that we can use optimization methods to search such large design spaces efficiently and automatically find the best solution for a given task and objective. However, work in this domain has been limited mostly to the performance optimization of keyboards. The Ph.D. thesis advances the field of text-entry optimization by enlarging the space of optimizable text-input methods and proposing new criteria for assessing their optimality. Firstly, the design problem is formulated as an assignment problem for integer programming. This enables the use of standard mathematical solvers and algorithms for efficiently finding good solutions. Then, objective functions are developed, for assessing their optimality with respect to motor performance, ergonomics, and learnability. The corresponding models extend beyond interaction with soft keyboards, to consider multi-finger input, novel sensors, and alternative form factors. In addition, the thesis illustrates how to formulate models from prior work in terms of an assignment problem, providing a coherent theoretical basis for text-entry optimization. The proposed objectives are applied in the optimization of three assignment problems: text input with multi-finger gestures in mid-air, text input on a long piano keyboard, and -- for a contribution to the official French keyboard standard -- input of special characters via a physical keyboard. Combining the proposed models offers a multi-objective optimization approach able to capture the complex cognitive and motor processes during typing. Finally, the dissertation discusses future work that is needed to solve the long-standing problem of finding the optimal layout for physical keyboards, in light of empirical evidence that prior models are insufficient to respond to the diverse typing strategies people employ with modern keyboards. The thesis advances the state of the art in text-entry optimization by proposing novel objective functions that quantify the performance, ergonomics and learnabilityof a text input method. The objectives presented are formulated as assignment problems, which can be solved with integer programming via standard mathematical solvers or heuristic algorithms. While the work focused on text input, the assignment problem can be used to model other design problems in HCI (e.g., how best to assign commands to UI controls or distribute UI elements across several devices), for which the same problem formulations, optimization techniques, and even models could be applied.
Supervising professor
Oulasvirta, Antti, Prof., Aalto University, Department of Communications and Networking, Finland
text entry, combinatorial optimization, computational interaction, human-computer interaction
Other note
  • [Publication 1]: Anna Maria Feit, Antti Oulasvirta. PianoText: Redesigning the Piano Keyboard for Text Entry. Proceedings of the 2014 Conference on Designing Interactive Systems, June 2014.
    DOI: 10.1145/2598784.2602800 View at publisher
  • [Publication 2]: Srinath Sridhar, Anna Maria Feit, Christian Theobalt, Antti Oulasvirta. Investigating the Dexterity of Multi-Finger Input for Mid-Air Text Entry. Proceedings of the 33rd Annual ACM Conference on HumanFactors in Computing Systems, 3643–3652, May 2015. Full-text in Aaltodoc/Acris:
    DOI: 10.1145/2702123.2702136 View at publisher
  • [Publication 3]: Anna Maria Feit, Daryl Weir, Antti Oulasvirta. How We Type: Movement Strategies and Performance in Everyday Typing. Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems, 4262-4273, May 2016.
    DOI: 10.1145/2858036.2858233 View at publisher
  • [Publication 4]: Vivek Dhakal, Anna Maria Feit, Per Ola Kristensson, Antti Oulasvirta. Observations on Typing from 136 Million Keystrokes. Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems, 646:1–646:12, April 2018.
    DOI: 10.1145/3173574.3174220 View at publisher