=Paper=
{{Paper
|id=Vol-2183/paper1
|storemode=property
|title=Computational Layout Design for Keyboards with Multi-Letter Keys
|pdfUrl=https://ceur-ws.org/Vol-2183/paper1.pdf
|volume=Vol-2183
|authors=Ryan Qin,Suwen Zhu,Yu-Hao Lin,Yu-Jung Ko,Xiaojun Bi
}}
==Computational Layout Design for Keyboards with Multi-Letter Keys==
https://ceur-ws.org/Vol-2183/paper1.pdf
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