Barcelona, Spain | September 3, 2018 MobileHCI 2018 Workshop on Socio-Technical Aspects of Text Entry Computational Layout Design for Keyboards with Multi-Letter Keys Ryan Qin Yu-Jung Ko Abstract Ward Melville High School Computer Science Department Keyboards with multi-letter keys (i.e., a key corresponds East Setauket, NY, USA Stony Brook University to multiple letters) have been commonly used on small Stony Brook University Stony Brook, NY, USA touchscreen devices to mitigate the problem of tapping Stony Brook, NY, USA yujko@cs.stonybrook.edu tiny keys with imprecise finger touch (e.g., T9 keyboard). ryanqin15@gmail.com We have proposed a computational approach to designing optimal multi-letter key layouts by considering three key Suwen Zhu Xiaojun Bi factors: clarity, speed, and learnability. In particular, we Computer Science Department Computer Science Department Stony Brook University Stony Brook University have devised a clarity metric to model the word collisions Stony Brook, NY, USA Stony Brook, NY, USA (i.e., words with identical tapping sequences), used the suwzhu@cs.stonybrook.edu xiaojun@cs.stonybrook.edu Fitts-Digraph model to predict speed, and introduced a Qwerty-bounded constraint to ensure high learnability. Yu-Hao Lin Founded upon rigorous mathematical optimization, our Computer Science Department investigation led to Qwerty-bounded T9-like (i.e., 3 × 3) Stony Brook University layouts optimized for both clarity and speed. A Stony Brook, NY, USA preliminary user study showed promising performance of yuhalin@cs.stonybrook.edu such keyboards. ACM Classification Keywords H.5.2. [Information Interfaces and Presentation]: User Permission to make digital or hard copies of part or all of this work for personal or Interfaces-Input devices and strategies. classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. Author Keywords For all other uses, contact the owner/author(s). Text entry; touchscreen. Copyright held by the owner/author(s). MobileHCI, 2018 Barcelona, Spain. 1 Barcelona, Spain | September 3, 2018 MobileHCI 2018 Workshop on Socio-Technical Aspects of Text Entry Introduction programming [9] have been proposed based on Typing on keyboards supported by small embedded single-letter key layout design. Alphabetically constrained devices such as smartwatches is often extremely keypads [5] and the Qwerty-like 9-key layout [7], a cumbersome. As the finger is inherently inaccurate, the multi-letter key layout optimized with a bias for layout combination of an imprecise input device and tiny adaptability, have also been introduced. Moving forward, congested keys makes typing incredibly error-prone. One we advance the multi-letter layout optimization to of the most popular approaches to combat this input performing Pareto optimization on three critical objectives problem is via a multi-letter key design, in which – speed, accuracy, and learnability. (a) individual letters are amalgamated to enlarge the key size. Past research has also shown that the modern statistical We advocate a novel computational approach for decoding technique worked reasonably well on small designing multi-letter key layouts by considering three keyboards. Gordon et al.’s work [6] revealed that human important factors in layout design: clarity (i.e., reducing motor control adaptability, coupled with modern the number of words with identical tapping sequences), statistical decoding and error correction technologies speed, and learnability. In particular, we have devised a developed for smartphones, can enable a surprisingly clarity metric to model the word collisions (i.e., words effective typing performance for both gesture typing and with identical tapping sequences), used the Fitts-Digraph tap typing on a regular Qwerty keyboard on a watch-sized model [2, 14] to predict speed, and introduced a screen. Inspired by Gordon et al.’s research, we coupled (b) Qwerty-bounded constraint to ensure high learnability. multi-letter key layout design with the modern statistical Based on the proposed models, we applied a rigorous decoding technology and compared the optimized mathematical optimization with a Qwerty-bounded multi-letter key layout with a regular Qwerty keyboard. constraint to search for optimal 3 × 3 multi-letter layouts. To understand to what degree the optimized layout would Optimizing Multi-Letter Key Layouts improve typing performance in realistic text entry tasks, A number of factors must be carefully considered and we conducted a pilot study to evaluate the performance of balanced in the keyboard design task. For a novel layout the optimized layout alongside two de facto standard to flourish, we believe the following factors are key: layouts : Qwerty and T9. clarity, speed and learnability. (c) Clarity defines a multi-letter key layout’s capability of Related Work Various keyboard optimization approaches have been minimizing the potential word collisions (i.e., words Figure 1: (a): the optimized proposed, beginning with improving input speed sharing identical tap sequences because of merged keys). layout that maximizes the average of the clarity and speed exclusively [2] to eventually considering multiple factors We define clarity score to describe how likely layout L can scores. (b): the layout with such as speed, accuracy, and learnability [1, 3, 4] with resolve word collisions: maximum clarity score. (c): the both single-letter and multi-letter key layout design. M X layout with maximum speed Methods including the Metropolis algorithm [13], Pareto C(L) = f (Wj )clarity(Wj ), (1) score. multi-objective optimization [12], and integer j=1 2 Barcelona, Spain | September 3, 2018 MobileHCI 2018 Workshop on Socio-Technical Aspects of Text Entry where M represents the number of words comprising the optimized keyboard is learning the layout. Consequently, corpus, f (Wj ) is the frequency of a given word Wj , and despite numerous layouts having been proposed, very few f (W ) are actually implemented extensively. To achieve superior clarity(Wj ) = PN fj is a value between 0 and 1 for i=1 Wi performance over existing layouts, users likely have to Wj among total number of words N . The corpus for spend a considerable amount of time practicing, and not optimization was taken from American National Corpus every user is willing to make such an effort. For an (ANC) [8]. optimal layout to maintain high learnability, we devise a The typing speed metric estimates how fast expert users strict Qwerty-bounded constraint: we preserve Qwerty’s will be able to tap type on a keyboard layout. We used alphabetical arrangement to ensure that users can the widely known Fitts-Digraph model [2, 14] for speed immediately use this keyboard fluently. Note that the prediction, which shows that the average time (t) for Qwerty-bounded constraint only works for layouts with 3 inputting a letter is: rows. 26 26 X X Multi-Objective Optimization t= Pij Tij , (2) With the two aforementioned objectives (clarity and i=1 j=1 speed) and the Qwerty-bounded constraint (learnability), where Pij is the frequency of the ordered character pair designing a multi-letter key layout is essentially a i, j from 26 Roman characters, and Tij is the movement multi-objective optimization problem: searching for a time for the input finger travelling from key i to key j, layout optimized for both clarity and speed, subject to the which is typically predicted by the Fitts’ law: Qwerty-bounded constraint. Dij Tij = a + b log2 ( + 1), (3) As commonly used in layout optimization research, we Wij adopted the Pareto optimization technique [4, 3] to where Dij is the distance from the center of key i to the address this multi-objective optimization problem. Instead center of key j, and Wij is the key width. Since each key of generating a single optimized layout, Pareto tap action is essentially a 2-dimensional Fitts’ law task, we optimization will lead to a Pareto front, in which each used min(Wij , Hij ) (i.e., the minimum of key width or layout is Pareto optimal, meaning that none of its metric height) as Wij in Equation (3) [11]. Previous research scores can be improved without compromising the other [11] showed it yielded a fairly successful fit for 2D Fitts scores. The designer then later picks layouts from the tasks. In the context of touchscreen typing, Fitts’ law Pareto front, after considering the relative weights parameters were a = 0.083s and b = 0.127s, estimated by between metrics or other factors. Zhai et al. [14]. t has the unit of seconds. t can be converted to input speed (V ) in characters per minute Computationally Designing 3 × 3 Layouts (CPM): V = 60/t. Our algorithmic overview consists of the following three major phases. First, we exhaustively iterate through all Learnability is critical to the success of any new layout layout candidates subject to the Qwerty-bounded design: perhaps the biggest obstacle of any newly 3 Barcelona, Spain | September 3, 2018 MobileHCI 2018 Workshop on Socio-Technical Aspects of Text Entry constraint. Second, we utilize the Pareto optimization Evaluation approach to attain the final optimal configuration. Third, We carried out a preliminary study with 4 users (1 female) to empirically evaluate the proposed computational aged from 25 to 34. The average text entry speed approach, we applied it to design optimal 3 × 3 layouts for following Mackenzie [10] was 18.99 WPM (SD = 4.03) a watch-size multi-letter key layout based on Apple Watch for the optimized keyboard, 14.76 WPM (SD = 0.43) for screen specification (312 pixels (26.15 mm) by 390 pixels T9, and 18.19 WPM (SD = 2.93) for Qwerty. (32.69 mm)). A watch platform was selected as we devise Additionally, the average word error rate was 2.05% this novel computational approach with the aim of (SD = 1.54%) for the optimized keyboard, 2.30% improving text entry specifically on small devices. (SD = 0.64%) for T9, and 1.54% (SD = 1.41%) for Highest clarity Qwerty. At the end of the study, participants were asked 1 Maximum average Figure 2 illustrates the complete Pareto front formed by 71 to give an overall subjective rating for each keyboard on a 0.8 Pareto optimal layouts. As shown, the front approximately continuous scale of 1 (very dislike) to 5 (very like). The forms a curve spanning the top-left and bottom-right average rating was 4.5 for the optimized keyboard, 1.75 0.6 corner, indicating that clarity and speed are conflicting for T9, and 3.75 for Qwerty. Clarity metrics: one metric increases at the expense of the other. 0.4 Figures 1b and 1c display the layouts at two ends of the Overall, the small-scale study results showed the optimized front: the one possessing the highest clarity and the one layout was promising. Its input speed was greater than 0.2 Fastest speed holding the fastest speed. In Pareto optimization, the final original T9 and Qwerty, and the subjective ratings were 0 compromise keyboard proposal is taken to be the also in favor of it. We plan to carry out a more formal and 0.2 0.4 0.6 0.8 1 Speed keyboard that achieves best on average. Thus, as we are large-scale user study to investigate its performance. particularly interested in the layouts with the most Figure 2: The Pareto front. balanced typing clarity and speed, we closely examine the Conclusions and Future Work layouts near the center of the Pareto front. We selected We have proposed a computational approach for designing the layout carrying the maximum average of normalized optimal multi-letter key layouts by taking into clarity and speed as the optimized layout subject to our consideration clarity, speed and learnability. To evaluate specific Qwerty constraints. We referred to this its validity, we have applied it to computationally design configuration as our optimized layout (Figure 1a), which 3 × 3 layouts. Our investigation led to an optimized layout lies on the 55.4 degree line from the origin. The clarity which struck a balance between clarity and speed. Both scores and estimated input speeds are shown in Table 1. the theoretical analysis and a preliminary user study showed such a layout has outperformed the original T9 layout and could be promising for text entry on small Optimized Highest clarity Fastest speed T9 Qwerty Clarity 0.8738 0.9412 0.6519 0.9234 1.0 touchscreen devices (e.g., smart watches). We plan to CPM 309.70 284.27 343.14 278.18 169.74 carry out more formal studies to further investigate the WPM 61.94 56.85 68.63 55.64 33.95 pros and cons of the proposed methods as well as the generated optimal keyboard layouts. Table 1: The clarity and speed (in CPM and WPM) of different 3 × 3 layouts. 4 Barcelona, Spain | September 3, 2018 MobileHCI 2018 Workshop on Socio-Technical Aspects of Text Entry References CHI EA ’05, ACM (New York, NY, USA, 2005), [1] Bi, X., Smith, B. A., and Zhai, S. Quasi-qwerty soft 1479–1482. keyboard optimization. In Proceedings of the SIGCHI [8] Ide, N., and Macleod, C. The american national Conference on Human Factors in Computing corpus: A standardized resource of american english. Systems, CHI ’10, ACM (New York, NY, USA, In Proceedings of Corpus Linguistics, Vol. 3 2010), 283–286. (Lancaster, UK, 2001), 1–7. [2] Bi, X., Smith, B. A., and Zhai, S. Multilingual [9] Karrenbauer, A., and Oulasvirta, A. Improvements to touchscreen keyboard design and optimization. keyboard optimization with integer programming. In Human–Computer Interaction 27, 4 (2012), 352–382. Proceedings of the 27th Annual ACM Symposium on [3] Bi, X., and Zhai, S. Ijqwerty: What difference does User Interface Software and Technology, UIST ’14, one key change make? gesture typing keyboard ACM (New York, NY, USA, 2014), 621–626. optimization bounded by one key position change [10] MacKenzie, I. S. A note on calculating text entry from qwerty. In Proceedings of the 2016 CHI speed, 2015. Conference on Human Factors in Computing [11] MacKenzie, I. S., and Buxton, W. Extending fitts’ Systems, CHI ’16, ACM (New York, NY, USA, law to two-dimensional tasks. In Proceedings of the 2016), 49–58. SIGCHI Conference on Human Factors in Computing [4] Dunlop, M., and Levine, J. Multidimensional pareto Systems, CHI ’92, ACM (New York, NY, USA, optimization of touchscreen keyboards for speed, 1992), 219–226. familiarity and improved spell checking. In [12] Smith, B. A., Bi, X., and Zhai, S. Optimizing Proceedings of the SIGCHI Conference on Human touchscreen keyboards for gesture typing. In Factors in Computing Systems, CHI ’12, ACM (New Proceedings of the 33rd Annual ACM Conference on York, NY, USA, 2012), 2669–2678. Human Factors in Computing Systems, CHI ’15, [5] Gong, J., and Tarasewich, P. Guidelines for handheld ACM (New York, NY, USA, 2015), 3365–3374. mobile device interface design. In In Proceedings of [13] Zhai, S., Hunter, M., and Smith, B. A. The the 2004 DSI Annual Meeting (2004). metropolis keyboard - an exploration of quantitative [6] Gordon, M., Ouyang, T., and Zhai, S. Watchwriter: techniques for virtual keyboard design. In Tap and gesture typing on a smartwatch miniature Proceedings of the 13th Annual ACM Symposium on keyboard with statistical decoding. In Proceedings of User Interface Software and Technology, UIST ’00, the 2016 CHI Conference on Human Factors in ACM (New York, NY, USA, 2000), 119–128. Computing Systems, CHI ’16, ACM (New York, NY, [14] Zhai, S., Sue, A., and Accot, J. Movement model, USA, 2016), 3817–3821. hits distribution and learning in virtual keyboarding. [7] Hwang, S., and Lee, G. Qwerty-like 3x4 keypad In Proceedings of the SIGCHI Conference on Human layouts for mobile phone. In CHI ’05 Extended Factors in Computing Systems, CHI ’02, ACM (New Abstracts on Human Factors in Computing Systems, York, NY, USA, 2002), 17–24. 5