On the building of optimal binary trees for spelling interfaces

Abstract

Accomplishments of surgery and increasing level of efficiency of life-support systems result in the increasing number of patients who survive severe accidents or diseases, such as stroke in the brain stem, tumors, encephalitis, some forms of polyneuritis or brain injuries. Although patients survive, they can suffer from serious injures of the brain and spinal cord, resulting, in the worst case, in paralysis or in the so-called locked-in syndrome - "active mind in a paralyzed body". A very common reason for paralysis and locked-in symptom is amyotrophic lateral sclerosis or ALS.

Locked-in patients remain conscious and can both hear and see their surroundings, although they are unable to use their muscles and, therefore, to communicate with their environment either vocally or manually (using body language, per writing or keyboard etc.). Hence, in order to maintain at least a minimal degree of quality of life they need artificial means for communication. Usually, such communication devices provide a patient with a sequence of letters. Using his remaining motor ability (e.g., finger movements or blinks), the patient tries to choose the correct letters, thereby creating words and phrases. The remaining motor ability can be so scanty that only the binary ("Yes/No") communicational signal could be delivered to a device (for example, to a so-called "head-switch" communication device).

A definite drawback of such communication devices for artificial spelling is their error-proneness. Using such systems for alternative communication with motor response control, a patient very often is not able to produce an absolutely reliable single binary response, especially if suffering from very severe motor paralysis. This means that in many cases the binary signal will be delivered to the device with an error.

As a result, motor communication becomes extremely restricted or even impossible. In order to overcome this problem, direct brain-computer communication devices are being developed. These devices allow muscle-independent communication and create a direct communication channel between the patient's brain and the computer. The first such device, which has been already successfully used for practical communication with ALS-patients, is the TTD (Thought-Translation Device). It was developed by Prof. N. Birbaumer, Dr. J. Perelmouter and their group at the University of Tübingen.

Brain-computer interfaces are even more error-prone than artificial spelling devices based upon movements. Nevertheless, in case of fully locked-in patients brain-computer interfaces represent the only existing possibility of communication with the environment. As the disease is progressing, brain-computer interfaces become a single mean of communication for locked-in patients.

Another concern deals with the error-proneness itself and its psychological consequences. Especially for locked-in patients it is extremely important to have a reliable communication channel. On the other hand, due to non-trivial skills to voluntarily control the brain activity, the communication via brain-computer interfaces is conducted essentially slower and with more errors than verbal or motor communication. Hence, every acceleration of either communication rate or accuracy of communication will lead to an increasing level of quality of life for locked-in patients. This can be achieved through optimization of brain-computer interfaces used for communication in terms of increasing of error-propones and adoption to individual patient's characteristics. These are, first of all, the individual needs of the patient as well as his skills with respect to voluntary control of brain activity.

The initial problem that is covered in this thesis consists of all main concerns presented above and deals primarily with increasing of quality of life for locked-in patients, who are or will be using brain-computer interfaces for communication. We strive to solve this problem through increasing of communication speed and accuracy due to both optimization of interfaces and adoption to individual patient's characteristics. As has been shown, this initial problem leads to a general problem of a non-zero error communication and can be applied to all types of binary communication devices.

In order to solve the problem, we need to set a criterion that matches this problem and to develop a method of creation of optimal brain-computer interfaces, which corresponds to this optimization criterion. Hereby the individual characteristics of the patient need to be taken into account. The aim of this research is to find such criterion, to develop optimization methods for it and to implement these methods in form of mathematical algorithms and of a corresponding computer tool. The results of this work are intended, first and foremost, for the Thought-Translation Device and its applications, but could be also applied to all types of binary augmentative communication devices.

Das "locked-in" Syndrom wird als "Unfähigkeit, sich bei erhaltenem Bewusstsein sprachlich oder durch Bewegungen spontan verständlich zu machen" definiert. Dieses Syndrom wird durch eine vollständige Paralyse, z.B. aufgrund eines Gehirnschadens verursacht. Die meisten Patienten, die darunter leiden, verfügen über keine motorischen Fähigkeiten mehr und sind bei der Kommunikation mit ihrer Umwelt auf Brain-Computer Interfaces angewiesen.

Die Mehrheit der BCI's funktionieren so, dass dem Patienten eine Sequenz von Zeichen angezeigt wird, aus der der Patient bestimmte Buchstaben auswählt. In den meisten Fällen kann der Patient aufgrund seiner Behinderung lediglich angeben, ob er eine bestimmte Sequenz der Buchstaben in betracht ziehen möchte oder nicht, so dass man mit einem binären Signal "Ja/Nein" zu tun hat und in diesem Zusammenhang auch von binären Spelling Interfaces spricht. Eine weitere Herausforderung stellt die Tatsache dar, dass die Patienten aufgrund ihrer Krankheit auch diese eingeschränkte Wahl nicht immer genau treffen, was zu einer hohen Fehleranfälligkeit führt. Die Verbesserung der Kommunikationsmöglichkeiten kann daher zweierlei erreicht werden: zum einen durch Beschleunigung der Kommunikationsgeschwindigkeit und zum anderen durch Erhöhung der Fehlerfreiheit. In dieser Arbeit findet man unter anderem eine Analyse der existierenden binären Spelling Interfaces. Es wird gezeigt, dass ausschließlich der an der Universität Tübingen entwickelte Thought-Translation Device (TTD) praktische Anwendung gefunden hat.

Um die Kommunikation sowohl zu beschleunigen als auch fehlerfreier zu machen, wurde ein Kriterium entwickelt, welches diesem Optimierungsproblem entspricht. Das Kriterium beschreibt die mathematische Erwartung der Anzahl der Schritte, die erforderlich sind, um eine gewünschte Buchstabe zu schreiben, wobei die eventuell gemachten Fehler sowie deren Berichtigung mit Hilfe der sogenannten "delete"-Funktion berücksichtigt wird. Die Sequenz der Buchstaben entspricht einem binären Baum; die "Ja/Nein" Wahl entspricht der Wahl des linken oder des rechten Teibaums.

Um das oben beschriebene Problem hinsichtlich der schnelleren und fehlerfreieren Kommunikation zu lösen, muss man eine Sequenz der Buchstaben aufstellen, bei der das entwickelte Kriterium sein Minimum erreicht. Dieses Optimierungsproblem wird dadurch gelöst, dass man Algorithmen entwickelt, mit dessen Hilfe eine oder mehrere optimalen Sequenzen der Buchstaben durch Synthese aufgebaut werden. Dabei sind zwei folgende Aspekte zu bedenken. Erstens ist es die Tatsache, dass die Kommunikation nicht fehlerfrei abläuft. Der gewünschte Teilbaum wird mit einer Auswahlwahrscheinlichkeit keiner 1 ausgewählt, wobei sich die Wahrscheinlichkeiten für den linken und den rechten Teilbaum voneinander unterscheiden können. Zum anderen muss berücksichtigt werden, dass diese Wahrscheinlichkeiten für unterschiedliche Patienten verschieden sind.

Die entwickelten Algorithmen tragen diesen beiden Anforderungen Rechnung. Als erstes wurde ein Algorithmus entwickelt, welches die Darstellung der binären Bäume in Form der P-Sequenzen ermöglicht. Als nächstes wurde ein "Full-Search"-Algorithmus entwickelt, welches die Erstellung aller möglichen binären Bäume für ein bestimmtes Alphabet, verknüpft mit bestimmten Auftritthäufigkeiten der einzelnen Buchstaben, sowie für bestimmte, patientenspezifische Werte der Auswahlwahrscheinlichkeiten für das "Ja/Nein"-Signal ermöglicht.

Da dieses Algorithmus das Optimierungsproblem zwar löst, für die praktische Anwendung jedoch aufgrund der langen Rechenzeiten weniger geeinigt ist, wurden zwei weitere Algorithmen entwickelt, die sich mit dem stark inhomogenen Fall und mit dem homogenen Fall befassen. Diese Algorithmen ermöglichen erhebliche Beschleunigung hinsichtlich der Rechenzeit im Vergleich zu dem "Full-Search"-Algorithmus. Alle drei Algorithmen ermöglichen die Synthese der optimalen binären Bäume, also Bäume, die hinsichtlich der Kommunikationsgeschwindigkeit und Fehlerfreiheit nach dem oben aufgeführten Kriterium am besten geeignet sind. Zusammen decken sie die komplette Bandbreite an möglichen Fällen ab und stellen in Kombination die einzige bekannte universelle Methode dar, bestehend aus Kriterien und Algorithmen, die eine Synthese der individuell passenden Spelling Interfaces ermöglicht, denn sie berücksichtigt individuelle Auswahlwahrscheinlichkeiten eines bestimmten Patienten. Dadurch kann sichergestellt werden, dass ein Spelling Interface, welches mit Hilfe dieser Methode erstellt wurde, ein aus der Sicht der Patienten optimales Interface darstellt und ermöglicht, die schnellstmögliche und möglichst fehlerfreie Kommunikation zu führen.

Darüber hinaus wurde ein integriertes Computertool für Erzeugung der binären Bäume für die Verwendung durch Patienten entwickelt, welches sowohl die neu entwickelten als auch die bestehenden Algorithmen (wie z.B. das Perelmouter-Birbaumer Algorithmus) berücksichtigt.