Communications of the ACM
News
Success at 16
Sixteen-year-old Natalie Nash used an algorithm to find the optimal keyboard layout for severely disabled users.
Courtesy of Natalie Nash
Using a sophisticated optimization algorithm, Natalie Nash, a 16-year-old high school junior from Pennsylvania, designed a software interface to help severely disabled users communicate significantly faster than is possible using currently available alternatives. In May, her project, which was Nash's entry in the Intel Science and Engineering competition, wowed the three judges representing ACM, who awarded her the Association's first prize.
"The project was both socially relevantit was clear that it meant something to herand it had some very impressive computer science pieces to it," says one of the judges, Robb Cutler, founding president of the Computer Science Teachers Association and a graduate student in computer science at Purdue University.
People who can't speak use augmentative and alternative communication (AAC) devices that generate speech from users' input. Those who can't type, such as people with cerebral palsy, use AAC devices with a single switch through which they painstakingly make choices via an onscreen keyboard. The computer scans the AAC keyboard, highlighting one row at a time until the user activates the switch (by pressing a button, puffing, or blinking), and the device slowly zeroes in on the desired letter. "Sometimes it will take a good five minutes to type one sentence, and by that time everybody else in the conversation has moved on to another topic," Nash explains. "My project was designed to improve the speed of communication using this single-button method."
The first question Nash tackled was the fastest style of keyboard: the standard QWERTY keyboard; an AAC keyboard, which arranges the 26 letters in a 5x5 grid; or a standard ambiguous keyboard, which has more than one letter per key. Nash wrote a program to compare the three keyboards' efficiency at processing the 20,000 most commonly spoken words in American English. Contrary to her hunch, the AAC keyboard was fastest even though the ambiguous keyboard requires traversing only nine keys instead of 26.
Knowing that the AAC keyboard reduces scanning steps by placing the most commonly used letters, such as A and E, at the top left, Nash suspected she could reduce scanning steps by rearranging the letters on an ambiguous keyboard. What's more, all the devices use word predictionguessing the entire word from partial inputwhich gave Nash an insight that helped her optimize the AAC keyboard. "It's not necessarily the most common letters in the English language [that should be near the front], but the most common letters in the first part of the most common words, because rarely does the user have to type the actual whole word." G, for example, is very common because many words end in -ing, but users never have to enter the final g.
An exhaustive search of all possible keyboard arrangements would take forever, so Nash used the simulated annealing algorithm to find the optimal keyboard layout. "It actually turns out that I was correct. The ambiguous keyboard, when it was optimized, turned out to be a lot better than the other ones," says Nash, who calculated it is about 15% faster than an AAC keyboard.
Always interested in science, Nash got her first taste of computer programming as a third-grader participating in Carnegie Mellon University's (CMU's) C-MITES program for talented students. Soon enough, she was learning from her father, a CMU-educated programmer. By the time Nash could take computer science classes in high school, when she was a sophomore at Vincentian Academy, she was surprised by how much she already knew.
Although users would have to learn a new keyboard layout, an acquaintance with cerebral palsy told Nash the AAC community would embrace the new design. "Their main struggle is to be faster," says Nash, "and if it means memorizing a new keyboard, they would do it."
©2011 ACM 0001-0782/11/1000 $10.00
Permission to make digital or hard copies of part or all of this work for personal or 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 full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.
Comments
Anonymous
I work with students who use AAC. How can one get hold of a copy of the layout?
CACM Administrator
FYI. The keyboard layout is not currently commercially available.
Displaying all 2 comments