3.2.1 Nature of Speech

Speech is uniquely human, optimized to allow people to communicate complex thoughts and feelings (apparently) effortlessly. Thus the ‘speech channel’ is heavily optimized for the task of human-to-human communication. The atomic linguistic building blocks of spoken utterances are called phonemes. These are the smallest units that, if changed, can alter the meaning of a word or an utterance. The physical manifestations of phonemes are “phones”; but a speech signal is not simply a sequence of concatenated sounds, like Morse code. We produce speech by moving our articulators (tongue, jaw, lips) in an incredibly fast and well-choreographed dance that creates a rapidly shifting resonance structure. Our vocal cords open and close between 100–300 times a second, producing a signal called the fundamental frequency or F0, which excites vocal tract resonances, resulting in a high bandwidth sound (e.g. 0–10 kHz).

At other times, the resonances are excited by turbulent noise created at constrictions in the vocal tract, such as the sound of [s]. The acoustic expression of a phoneme is not fixed but, rather, the realization is influenced by both the preceding as well as the anticipated subsequent phoneme – a phenomenon called coarticulation. Additional variability is introduced when speakers adjust their speech to the current situation and the needs of their listeners. The resulting speech signal reflects these moving articulators and sound sources in a complex and rapidly varying signal. Figure 3.2 shows a speech spectrogram of a short phrase.

Advances in speech recognition accuracy and performance are the result of thousands of person-years of scientific and engineering effort. Hence state-of-the-art recognizers include many carefully optimized, highly engineered components. From about 1990 to 2010, most state-of-the-art systems were fairly similar, and showed gradual, incremental improvements. In the following we will describe the fundamental components of a “canonical” voice recognition system, and briefly mention some recent developments.

The problem solved by canonical speech recognizers is typically characterized by Bayes' rule:

3.1

That is, the goal of speech recognition is to find the highest probability sequence of words, , given the set of acoustic observations, . Using Bayes' rule, we get:

3.2

Note that does not depend on the word sequence , so we want to find:

3.3

We evaluate using an acoustic model (AM), and () using a language model (LM).

Thus, the goal of most speech recognizers is to find the sequence of words with the highest joint probability of producing the acoustic observation, given the structure of the language.

It turns out that the system diagram for a canonical speech recognition system maps well onto this equation, as shown in Figure 3.3.

The evaluation of acoustic probabilities is handled by the acoustic front-end and an acoustic model; the evaluation of probabilities of word sequences is handled by a language model; and the code which finds the best scoring word sequence is called the search component. Although these modules are logically separate, their application in speech recognition is highly interdependent.

3.2.2 Acoustic Model and Front-end

1. Front-end: Incoming speech is digitized and transformed to a sequence of vectors which capture the overall spectrum of the input by an “acoustic front-end”. For years, the standard front-end was based on using a vector of mel-frequency cepstral coefficients (MFCC) to represent each “frame” of speech (of about 25 msec) [1]. This representation was chosen to represent the whole spectral envelope of a frame, but to suppress harmonics of the fundamental frequency. In recent years, other representations have become popular [2] (see below).
2. Acoustic model: In a canonical system, speech is modeled as a sequence of words, and words as sequences of phonemes. However, as mentioned above, the acoustic expression of a phoneme is very dependent on the sounds and words around them, as a result of coarticulation. Although the context dependency can span several phonemes or syllables, many systems approximate phonemes using “triphones”, i.e., phonemes conditioned by their left and right phonetic context. Thus, a sequence of words is represented as a sequence of triphones. There are many possible triphones (e.g. ), and many of them occur rarely. Therefore the standard technique is to cluster them, using decision trees, [3], then create models for the clusters rather than the individual triphones.

The acoustic features observed when a word contains a particular triphone are modeled as a Hidden Markov Model (HMM), [4] – see Figure 3.4. Hidden Markov models are simple finite state machines (FSMs), with states, transitions, and probabilities associated with the transitions. Also, each state is associated with a probability density function (PDF) over possible front-end vectors.

The probability density function is usually represented as a Gaussian Mixture Model (GMM). GMMs are well studied, easily trained PDFs which can approximate arbitrary PDF shapes well. A GMM is a weighted sum of Gaussians; each Gaussian can be written as:

3.4

Where is an input vector, is a vector of means, and is the covariance matrix. and are vectors of length , and is a square matrix of dimension and each GMM is a simple weighted sum of Gaussians, i.e.,

3.5

3.2.3 Aligning Speech to HMMs

In the speech stream, phonemes have different durations, so it's necessary to find an alignment between input frames and states of the HMM. That is, given input speech frames, and a sequence of HMM states , an alignment maps the frames monotonically into the states of the HMMs. So the system needs to find the optimal (i.e. highest probability) alignment A between the frames and the HMM states.

3.6

This is often done using a form of the Viterbi algorithm [5].

For each hypothesized word sequence, the system looks up the phonemes that make up the pronunciation of each word from the lexicon, and then looks up the triphone for each phoneme in context, using decision trees. Then, given the sequence of triphones, the system looks up the sequence of HMM states. The acoustic probability of that hypothesis is the probability of the optimal alignment of these states with the input. An example of such an alignment is shown in Figure 3.5.

3.2.4 Language Model

The language model computes the probability of various word sequences and helps the recognition system propose the most likely interpretation of input utterances. There are two fundamentally different types of language models used in voice recognition systems: grammar-based language models, and stochastic language models.

Grammar-based language models allow some word sequences, but not others. Often, these grammars are application-specific, and support utterances relevant to some specific task, such as making a restaurant reservation or issuing a computer command. These grammars specify the exact word sequences which the user is supposed to utter in order to instruct the system. For example, a grammar for a reservation system might recognize sequences like “find a Chinese restaurant nearby”, “reservation for two at seven”, or “show me the menu”. The same grammar would probably not recognize sequences like “pepperoni pizza”, “economic analysis of the restaurant business”, or “colorless green ideas sleep furiously”.

The set of word-sequences recognized by a grammar is described by a formal grammar, e.g. a finite-state machine, or a context-free grammar. Often, these grammars are written in formalism like Speech Recognition Grammar Specification (SRGS) (see [6]). While it is easy to construct simple example grammars, writing a grammar that covers all the ways a user might like to specify an input can be difficult. Thus, one might say “nearby Chinese restaurant”, “please find a nearby Chinese restaurant”, “I'd like to eat Chinese”, or “Where can I find some dim sum?” All these sentences mean the same thing (to a restaurant ordering app), but writing a grammar that can cover all the choices can be onerous because of users' creative word choices.

Stochastic language models (originally used for free-text dictation) estimate the probability of any word sequence (but some are much more likely than others.) Thus, “Chinese restaurant” would have a reasonable probability; “restaurant Chinese” would have a somewhat smaller probability; and “nearby restaurant Chinese a find” would have a much lower probability. Attempts to write grammar-based language models to cover all the ways a user could generate English text have not been successful; so for general dictation applications, stochastic language models have been preferred. It turns out that it is much easier to make a robust, application-specific language model by using a stochastic LM, followed by NLU processing even for quite specific applications.

The job of stochastic language modeling is to calculate an approximation to , which is, by definition:

3.7

A surprising development in speech recognition was that a simple approximation (the trigram approximation) works very well:

3.8

The trigram approximation holds that the likelihood of the next word in a sentence depends only on the previous two words, (and an n-gram language model is the obvious generalization for longer spans). Scientifically and linguistically, this is inaccurate: many language phenomena span more than two words [7]! Yet it turns out that this approximation works very well in speech recognition [8].

3.2.5 Search: Solving Crosswords at 1000 Words a Second

The task of finding the jointly optimal word sequence to describe an acoustic observation is rather like solving a crossword, where the acoustic scores constrain the columns, and LM scores constrain the rows. However, there are too many possible word sequences to evaluate directly (a 100,000 word vocabulary generates ten-word sentences). The goal of the search component is to identify the correct hypothesis, and evaluate as few other hypotheses as possible. It does this using a number of heuristic techniques. One particularly important technique is called a beam search, which processes input frames one by one, and keeps “alive” a set of hypotheses with scores near that of the best hypothesis.

How much computation is required? For a large vocabulary task, on a typical frame, the search component might have very roughly 1000 active hypotheses. Updating the scores for an active hypothesis involves extending the alignment by computing acoustic model (GMM) scores for the current HMM state of that hypothesis, and the next state, and then updating the alignment. If the hypothesis is at the end of a word, (about 20 word-end hypotheses per frame), then the system also needs to look up LM scores for potential next words (about 100 new words per word ending). Thus, we need about 2000 GMM, 1000 alignment computations, and 2000 LM lookups, per frame. At a typical frame rate of 100 Hz, we are computing about 200 k GMMs, 200 k LM lookups, and 100 k alignment updates per second.

3.2.6 Training Acoustic and Language Models

The HMMs used in acoustic models are created from large datasets by an elaborate training process. Speech data is transcribed, and provided to a training algorithm which utilizes a maximum likelihood objective function. This algorithm estimates acoustic model parameters so as to maximize the likelihood of observing the training data, given the transcriptions. The heart of this process bootstraps an initial approximate acoustic model into an improved version, by aligning the training speech against the transcriptions and re-training the HMMs. This process is repeated many times to produce Gaussian mixture models which score the training data as high likelihood.

However, the goal of speech recognition is not to represent the most likely sequence of acoustic states, but rather to give correct word sequence hypotheses higher probabilities than incorrect hypotheses. Hence, various forms of discriminative training have been developed, which adjust the acoustic models so as to decrease various measures related to the recognition error rate [9–11].

The resulting acoustic models routinely include thousands of states, hundreds of thousands of mixture model components, and millions of parameters. Canonical systems used “supervised” training, i.e. used both speech and the associated transcriptions for training. As speech data sets have grown, there has been substantial effort to find training schemes using un-transcribed or “lightly labeled” data.

Stochastic language models are trained from large text datasets containing billions of words. Large text databases are collected from the World Wide Web, from specialized text databases, and from deployed voice recognition applications. The underlying training algorithm is much simpler than that used in acoustic training (it is basically a form of counting), but finding good data, weighting data carefully, and handling unobserved word sequences require considerable engineering skill. The resulting language models often include hundreds of thousands to billions of n-grams, and have billions of parameters.

3.2.7 Adapting Acoustic and Language Models for Speaker Dependent Recognition

People speak differently. The words they pick, and the way they say words is influenced by their anatomy, accent, education, and the intentional style of speaking (e.g., dictating a formal document vs. an informal SMS message).

The resulting differences in pronunciation may confuse a speaker-independent voice recognition system, which may not have encountered training exemplars with these particular combinations of characteristics. In contrast, a speaker dependent system which models a single speaker might achieve a higher accuracy than a speaker-independent system. However, users are not inclined to record thousands of hours of speech in order to train a voice recognition system, and it is thus highly desirable to produce speaker-dependent acoustic and language models by adapting speaker-independent models utilizing limited data from a particular user.

There are many kinds of adaptation for acoustic models. Early work often used MAP (maximum posteriori) training, which modifies the means and variances of the GMMs used by the HMMs. MAP adaptation is generally “data hungry”, since it needs to utilize training examples for most of the GMMs used in the system. More data-efficient alternatives modify GMM parameters for whole classes of triphones (e.g. MLLR, maximum likelihood linear regression [12]). Transformations can be applied either to the models or to the input features. While “canonical” adaptation is “supervised” (i.e. uses speech data with transcriptions), some forms of adaptation now are unsupervised, using the input speech data and recognition hypotheses without a person checking the correctness of the transcriptions.

Language models are also adapted for users or tasks. Adaptation can modify either single parameters (i.e. adjust the counts which model data for a particular n-gram, analogous to MAP acoustic adaptation), or can effectively adapt clusters of parameters (analogous to MLLR). For instance, when building a language model for a new domain, one can use interpolation weights to combine n-gram statistics from different corpora.

3.2.8 Alternatives to the “Canonical” System

In the previous paragraphs, we have outlined the basics of a voice recognition system. Many alternatives have been proposed; we mention a few prominent alternatives in Table 3.1.

Technique	Explanation	Reference
Combining AM and LM scores
Weighting AM vs. LM	Instead of the formula in equation II, with is used because the AM observations across frames are not really independent.	[8]
Alternative front ends
PLP	Perceptual linear predictive analysis: find a linear predictive model for the input speech, using a perceptual weighting.	[2]
RASTA	“Relative spectra”: a front end designed to filter out slow variations in channel and background noise characteristics.	[13]
Delta and double delta	Given a frame based front-end, extend the vector to include differences and second order differences between frames around the frame in question.	[14]
Dimensionality reduction	Heteroscedastic linear discriminant analysis (HLDA): given MFCC or other speech features, along with delta and double delta features, or “stacked frames” (i.e. a range of frames), using a linear transformation to decrease the dimension of the front end feature.	[15]
Acoustic modeling
Approximations to full covariance	Using the full covariance matrixes in HMM requires substantial computation and training data. Earlier versions of HMM used simpler versions of covariance matrixes such as “single variance”, diagonal covariance.	[16]
Vocal Tract Length Normalization	VTLN is a speaker-dependent technique which modifies acoustic features in order to take into account differences in the length of speakers' vocal tracts.	[17]
Discriminative training
MMIE	Maximum Mutual Information Estimation: a training method which adjusts parameters of an acoustic model so as to maximize the probability of a correct word sequence vs. all other word sequences.	[9]
MCE	Minimum classification error: a training method which adjusts parameters of an acoustic model to minimize the number of words incorrectly recognized.	[10]
MPE	Minimum phone error: a training method which adjusts parameters of an acoustic model to minimize “phone errors”, i.e., the number of phonemes incorrectly recognized.	[11]
LM
Back-off	In a classic n-gram model, it is very important to predict not only the probability of observed n-grams, but also n-grams that do not appear in the training corpus.	[18]
Exponential models	Exponential models (also known as maximum entropy models) estimate the probability of word sequences by multiplying many different probability estimates and other functions and weigh these estimates in the log domain. They can include longer range features than n-gram models.	[19]
Neural Net LMs	Neural network language models extend exponential models by allowing the indicator functions to be determined automatically via non-linear transformations of input data.	[20]
System organization
FSTs	In order to reduce redundant computation, it is desirable to represent the phonetic decision trees which map phonemes to triphones, the phoneme sequences that make up words, and grammars as finite state machines (called weighted finite state transducers, WFSTs), then combine them into a large FSM and optimize this FSM. Compiling all the information into a more uniform data structure helps with efficiency, but can have problems with dynamic grammars or vocabulary lists.	[21]

3.2.9 Performance

Speech recognition accuracy has steadily increased in performance during the past several decades. When early dictation systems were introduced in the late 1980s, a few early adopters eagerly embraced them and used them successfully. Many others found the error rate too high and decided that speech recognition “wasn't really ready yet”. Speech recognition performance had a bit of a breakthrough in popular consciousness in 2010, when David Pogue, the New York times technology reporter, reported error rates on general dictation of less than 1% [22]. Most speakers do not yet show nearly this level of performance, but performance has steadily increased each year through a combination of better algorithms, more computation, and utilization of ever-larger training corpora. In fact, on one specialized task, recognizing overlapping speech from multiple speakers, a voice recognition system was able to perform better than human listeners [23].

Over the past decade, the authors' experience has been that the average word error rate on a large vocabulary dictation task has decreased by approximately18% per year. This has meant that each year, the proportion of the user population that experiences acceptable performance without any system training has increased steadily. This progress has allowed us to take on challenging applications such as voice search, but also more challenging environments, such as in-car voice control. Finally, improving accuracy has meant that voice recognition has now become a viable front end for sophisticated natural language processing, giving rise to a whole new class of interfaces.

3.4.1 Lower Power Wake-up Computation

This has led to a need to reduce power consumption on mobile devices. Software can disable temporarily unused capabilities (Bluetooth, Wi-Fi, Camera, GPS, microphones) and quickly re-enable them when needed. Devices may even put themselves into various low-power modes, with the system able to respond to fewer and fewer actions. Think of Energy Star compliant TVs and other devices, but with more than just three (On-Off-Standby) states. How, then, does the system “wake up”? A physical action by the user, such as pressing a power key on the device, is the most common means today.

However, devices today have a variety of sensors that can also be used for this purpose. An infrared sensor can detect a signal from a remote control. A light sensor can trigger when the device is pulled out of a pocket. A motion sensor can detect movement. A camera can detect people. A microphone voice wakeup can detect voice activity or a particular phrase.

This is accomplished through low-power, digital signal processing (DSP)-based “wake-up-word” recognition, which allows users to speak to devices without having first to turn them on, further reducing the number of steps separating user intent and desired outcome. For instance, the Intel-inspired Ultrabook is integrating these capabilities, responding to “Hello Dragon” by waking up and listening to a users' command or taking dictation.

The security aspect starts to loom large here. A TV responds to its known signals, regardless of the origin of the signal. Anyone who has the remote control is able to operate it – or, indeed, anyone with a compatible remote control. While a living room typically has at most one TV in it, a meeting room may have 20 people, all with mobile phones. For a person to attempt to wake up his or her phone and actually wake up someone else's would be most unwelcome! Hence, there needs to be an element of security through personalization. The motion sensor may only respond to certain motions. The camera sensor may only respond to certain user(s), a technology known as “Facial Recognition”, and the voice wakeup may only respond to a particular phrase as spoken by a particular user – “Voice Biometrics” technology.

3.4.2 Hardware Optimization for Specific Computations

These sensors all draw power, especially if they are always active, and when the algorithms are run on the main CPU they incur a substantial drain on the battery. Having a full audio system running, with multiple microphones, acoustic echo cancellation and beam forming, draws significant amounts of power. Manufacturers are thus developing specialized hardware for these sensor tasks to reduce this power load, or are relying on DSPs, typically running at a much lower clock speed than the main CPU, say at 10 MHz, rather than 1–2 GHz.

The probability density function (pdf) associated with a single n-dimensional Gaussian Model is shown above in equation (1.4) The overall pdf of a Gaussian Mixture Model is a weighted sum of such pdfs, and some systems may have 100,000 or more of these pdfs, potentially needing to be evaluated 100 times a second. Algorithmic optimizations (only computing “likely” pdfs) and model approximations (such as assuming the covariance matrix is diagonal) are applied to reduce the computational load. The advent of SIMD (single-instruction, multiple data) hardware was a big breakthrough, as it enabled these linear algebra computations to be done for four or eight features at a time.

The most recent advance has been the use of Graphical Processing Units (GPUs). Initially GPUs were used to accelerate 3D computer graphics (particularly for games), which make extensive use of linear algebra. GPUs help with the pdfs such as those described above, but have proved particularly effective in the computation of DNNs.

As discussed above, DNNs have multiple layers of nodes, and each layer of nodes is the output from a mostly linear process applied to the layer of nodes immediately below it. Layers with 1000 nodes are common, with 5–10 layers, hence applying the DNN effectively requires the calculation of 5–10 matrix-vector multiplies, where each matrix is on the order of , and this occurs many times per second. Training the DNN is even more computationally expensive. Recent research has shown that training on a very small amount of data could take three months, but that using a GPU cut the time to three days, a 30-fold reduction in time [28].

3.5.1 Robust Voice Recognition

Noise robustness can be achieved by modifying the voice recognition process, or by using a dedicated speech enhancement front end. Today's systems typically use a combination of both.

State-of-the-art techniques in robust voice recognition include using noise robust features such as MFCCs or neural networks, and training the acoustic models with noisy speech data that is representative of the kinds of noise present in normal use of the application. However, due to the large diversity of acoustic environments, it is impossible to cover all possible noise situations during training. Several approaches have been developed for rapidly adapting the parameters of the acoustic models to the noise conditions which are momentarily present in the input signal. These techniques have been successfully applied – for instance to enable robust distant-talk in varying reverberant environments.

Speech enhancement algorithms can be roughly grouped into single- and multi-channel methods. Due to the specific statistical properties of the various noise sources and environments, there is no universal solution that works well for all signals and interferers. Depending on the application, the speech enhancement front-end therefore often combines different methods. Most common is the combination of single-channel noise suppression with multi-channel techniques such as noise cancellation and spatial filtering.

3.5.2 Single-channel Noise Suppression

Single-channel noise suppression techniques are commonly based on the principle of spectral weighting. In this method, the signal is initially decomposed into overlapping data blocks with a duration of about 20–30 milliseconds. Each of these blocks is then transformed to the frequency or subband domain using either a Short-Term Fourier Transform (STFT) or a suitable analysis filterbank. Next, the spectral components of the noisy speech signal are weighted by attenuation factors, which are calculated as a function of the estimated instantaneous signal-to-noise ratio (SNR) in the frequency band or subband. This function is chosen so that spectral components with a low SNR are attenuated, while those with a high SNR are not. The goal is to create a best estimate of the spectral coefficients of the clean speech signal. Given the enhanced spectral coefficients, a clean time domain signal can be synthesized and passed to the recognizer. Alternatively, the feature extraction can be performed directly on the enhanced spectral coefficients, which avoids the transformation back into the time-domain.

A large variety of linear and non-linear algorithms have been developed for calculating the spectral weighting function. These algorithms mainly differ in the underlying optimization criteria, as well as in the assumptions about the statistical characteristics of speech and noise. The most common examples for weighting functions are spectral subtraction, the Wiener filter, and the minimum mean-square error (MMSE) estimator [29]. The single-channel noise suppression scheme is illustrated by the generalized block diagram in figure 3.8. Figure 3.9 shows a spectrogram of the noisy phrase ‘Barbacco has an opening’ and the spectrogram of the enhanced signal after applying the depicted spectral weighting coefficients.

Single-channel noise suppression algorithms work well for stationary background noises like fan noise from an air-conditioning system, a PC fan, or driving noise in a vehicle, but they are not very suitable for non-stationary interferers like speech and music. In a single-channel system, the background noise can mostly be tracked in speech pauses only, due to the typically high frequency overlap of speech and interference in the noisy speech signal. This limits the single-channel noise reduction schemes mainly to slowly time-varying background noises which do not significantly change during speech activity.

Several optimizations have been proposed to overcome this restriction. These include model-based approaches which utilize an explicit clean speech model, or typical spatio-temporal features of speech and specific interferers in order to segregate speech from non-stationary noise. Efficient methods have been developed to reduce fan, wind-buffets in convertibles [30], and impulsive road or babble-noise.

Another drawback of single-channel noise suppression is the inherent speech distortion of the spectral weighting techniques, which significantly worsens at lower signal-to-noise ratios. Due to the SNR-dependent attenuation of the approach, more and more components of the desired speech signal are suppressed as the background noise increases. This increasing speech distortion degrades recognizer performance.

3.5.3 Multi-channel Noise Suppression

Unlike single-channel noise suppression, multi-channel approaches can provide low speech distortion and a high effectiveness against non-stationary interferers. Drawbacks are an increased computational complexity, and that additional microphones or input channels are required. Multi-channel approaches can be grouped into noise-cancellation techniques which use a separate noise reference channel, and spatial filtering techniques such as beamforming (discussed below).

3.5.4 Noise Cancellation

Adaptive noise cancellation [31] can be applied if a correlated noise reference is available. That means that the noise signals in the primary channel (i.e. the microphone) and in the reference channel are linear transforms of a single noise source. An adaptive filter is used to identify the transfer function that maps the reference signal to the noise component in the primary signal. By filtering the reference signal with the transfer function, an estimate for the noise component in the primary channel is calculated. The noise estimate is afterwards subtracted from the primary signal to get an enhanced speech signal. The principle of adaptive noise cancellation is illustrated in figure 3.10. As signal and noise components superpose linearly at the microphone, the subtraction of signal components does not lead to any speech distortion, provided that uncorrelated noise components and crosstalk of the desired speech signal into the reference channel are sufficiently small.

The effectiveness of noise cancellation is, in fact, highly dependent on the availability of a suitable noise reference which is, in turn, application-specific. Noise cancellation techniques are successfully applied in mobile phones. Here, the reference microphone is typically placed as far as possible from the primary microphone – typically on the top or the rear of the phone – to reduce leakage of the speech signal into the reference channel. Noise cancellation techniques are, on the other hand, less effective in reducing background noise in vehicle applications, due to diffuse characteristics of the dominating wind and tire noise. As a result, the correlation rapidly drops if the primary and reference microphone are separated more than a few centimeters, which makes it practically impossible to avoid considerable leakage of the speech signal into the reference channel.

3.5.5 Acoustic Echo Cancellation

A classic application for noise cancellation is the removal of interfering loudspeaker signals, which is typically referred to as Acoustic Echo Cancellation (AEC) [32]. This method was originally developed to remove the echo of the far end subscriber in hands-free telephone conversations. In voice recognition, AEC is used to remove the prompt output of the speech dialog system or the stereo entertainment signal from a TV or mobile application.

Analogously to the noise canceller described above, the electric loudspeaker reference is filtered by an adaptive filter to get an estimate of the loudspeaker component in the microphone signal. The adaptive filter has to model the room transfer function, including the loudspeaker and microphone transfer functions. As the acoustic environment can change quickly – for instance due to movements of persons in the room – fast tracking capabilities of the adaptive filter are of major importance to remove loudspeaker components effectively.

Due to its robustness and simplicity, the so-called Normalized Least Mean Square (NLMS) algorithm [33] is widely used to adjust the filter coefficients of the adaptive filter. A drawback of the algorithm is that it converges slowly if the interference has a high spectral dynamic, as in the case of speech or music. For this reason, the NLMS is often implemented in the frequency or subband domain. As the spectral dynamic in the individual frequency subbands is much lower than over the complete frequency range, the tracking behavior is significantly improved. Another advantage of working in the subband domain is that AEC and spectral weighting techniques like noise reduction can be efficiently combined.

3.5.6 Beamforming

When speech is captured with an array of microphones, the resulting multi-channel signal also contains spatial information about the sound sources. This facilitates spatial filtering techniques such as beamforming, which extract the signal from a desired direction while attenuating noise and reverberation from other directions. The application of adaptive filtering techniques [34] allows adjusting the spatial characteristics of the beamformer to the actual sound-field, thus enabling effective suppression, even of moving sound sources. The directionality of such an adaptive beamformer, however, depends on the number of microphones, which are often limited in practical devices to 2–3 due to cost reasons.

To improve the directionality the adaptive beamformer can be combined with a so called spatial post-filter [35]. The spatial post-filter is based on the spectral weighting techniques also applied for noise reduction, but uses a spatial noise estimate of the adaptive beamformer. Although spatial filtering can significantly reduce interfering noise or competing speakers, it can also be harmful if the speaker is not at the specified location. This makes it imperative to have a robust speaker localization system, especially in the mobile context, where the direction of arrival changes if the user moves or tilts a device.

A simple approach is to perform the localization acoustically, by simply selecting the direction in which the sound level is strongest [36]. This works reasonably well if there is a single speaker at a relatively close distance to the device, such as when using a tablet. A more challenging scenario arises in the context of smart TVs, or smart home appliances in general, where there may be several competing speakers at a larger distance. Such conditions prevent acoustic source localization from working reliably. In this situation, it may be preferable to track the users visually with the help of a camera and to focus on the speaker that is, for instance, facing the device. An alternative is to use gestures to indicate who the device should listen to.

As mentioned above, the speech enhancement front-end often combines several techniques to cope effectively with complex acoustic environments. Figure 3.11 shows an example of a speech enhancement front end enabling far-talk operation of a TV. In this system, acoustic echo cancellation is applied to remove the multi-channel entertainment signal, while beamforming and noise reduction are used to suppress interfering sources such as family members and background noises.

3.6.1 Introduction

Many voice-driven applications on a mobile device need to verify a user's identity. This is sometimes for security purposes (e.g. allowing a user to make a financial transaction) or to make sure that a spoken command was issued by the device's owner.

Voice biometrics recognizes a person based on a sample of their voice. The primary use of voice biometrics in commercial applications is speaker verification. Here, a claimed identity is validated by comparing the characteristics of voice samples obtained during a registration phase and validation phase. Voice biometrics is also used for speaker identification where a voice sample is matched to one of a set of registered users. Finally, in cases where a recording may include voice data from multiple people, such as during a conversation between an agent and customer, “speaker diarization” extracts the voice data corresponding to each speaker. All of these technologies can play a role in human-machine interaction and, particularly, when security is a requirement.

Voice biometrics will be a key component of mobile user interfaces. Traditional security methods have involved tedious measures based on personal identification numbers, passwords, tokens, etc., which are particularly awkward when interacting with a mobile device. Voice biometrics provides a much more natural and convenient method of validating the identity of a user. This has numerous applications, including everyday activities such as accessing email and waking up a mobile device. For “seamless wakeup”, not only must the phrase be correct, but it must be spoken by the owner of the device. This can preserve battery life and prevent unauthorized device access. Other applications include transaction validation for mobile banking and purchase authorization.

Research dedicated to developing and improving technologies for performing speaker verification, identification, and diarization has been making progress for the last 50 years. Whereas early technologies focused mainly on template-based approaches, such as Dynamic Time Warping (DTW) [37], these have evolved towards statistical models such as the GMM (discussed above in Section 1.5.2 [39]). More recent speaker recognition technologies have used the GMM as an initial step towards modeling the voice of a user, but then apply further processing in the form of Nuisance Attribute Projection (NAP) [40], Joint Factor Analysis (JFA) [41], and Total Factor Analysis (TFA) [42]. The TFA approach, which yields a compact representation of a speaker's voice known as an I-vector (or Identity vector) represents the current state of the art in voice biometrics.

3.6.2 Existing Challenges to Voice Biometrics

One of the primary challenges in voice biometrics has been to minimize the error rate increase attributed to mismatch in the recording device between registration and validation. This can occur, for example, when a person registers their voice with a mobile phone, and then validates a web transaction using their personal computer. In this case, there will be an increase in the error rate due to the mismatch in the microphone and channel used for these different recordings. This specific topic has received a great deal of attention in the research community, and has been addressed successfully with the NAP, JFA, and TFA approaches. However, new scenarios are being considered for voice biometrics that will warrant further research. Another challenge is “voice aging”. This refers to the degradation in verification accuracy as the time elapse between registration and validation increases [43]. Model adaptation is one potential solution to this problem, where the model created during registration is adapted with data from validation sessions. Of course, this is applicable only if the user accesses the system on a regular basis.

Another challenge to voice biometrics technology is to maintain acceptable levels of accuracy with minimal audio data. This is a common requirement for commercial applications. In the case of “text-dependent” speaker verification – where the same phrase must be used for registration and validation – two to three seconds (or ten syllables) can often be enough for reliable accuracy. Some applications, however, such as using a wakeup word on a mobile device, require shorter utterances for validating a user.

Whereas leveraging the temporal information and using customized background modeling improve accuracy, this topic remains a challenge. Similarly, with “text-independent” speaker verification – where a user can speak any phrase during registration or validation – typically 30–60 seconds of speech is sufficient for reasonable accuracy. However, speaker verification and identification capabilities are often desired, with much shorter utterances, such as when issuing voice commands to a mobile device, having a brief conversation with a call-center agent, etc. The National Institute of Standards and Technology (NIST) has sponsored numerous speaker recognition evaluations that have included verification of short utterances [44], and this is still an active research area.

3.6.3 New Areas of Research in Voice Biometrics

Voice biometrics technologies have advanced significantly since their inception; however a number of areas require further investigation. Countermeasures for “spoofing” attacks (orchestrated with recording playback, voice splicing, voice transformation, and text-to-speech technology) provide new challenges. A number of such attacks have been recently covered in an international speech conference [45]. Ongoing work assesses the risk of these attacks and attempts to thwart them. This can be accomplished through improved liveness detection strategies, along with algorithms for detecting synthesized speech.

Voice biometrics represents an up-and-coming area for interactive voice systems. Whereas speech recognition, natural language understanding, and text-to-speech have had more deployment history, voice biometrics technology is rapidly growing in the commercial and Government sectors. Voice biometrics provides a convenient means of validating an identity or locating a user among an enrolled population, which can reduce identity theft, fraudulent account access, and security threats. The recent algorithmic advances in the voice biometrics field, as described in this section, increase the number of use-cases and will facilitate adoption of this technology.

3.8.1 Mixed Initiative Conversations

In [56], Walker & Whitaker observed that more natural conversations display mixed initiative. In human-to-human dialogs, one person may offer additional relevant information beyond what was asked, or else may ask the other person to change away from the current task. Dialog systems hoping to perform in a mixed-initiative setting must therefore prepare for utterances that do not directly provide the expected information. A restaurant system might ask “where do you want to eat?” when the user is focusing on the time and instead replies with “We want a reservation at 7.” The utterance is relevant to one of the restaurant-reservation slots, but not the one that the system was expecting. This requires an NLU component that can decode and interpret more complex inputs than simple direct-answer phrases.

There are also many ways in which a user can give a direct answer to a slot-filling question. For example, the user could respond to the question “where do you want to eat?” with a variety of restaurant characteristics, as illustrated in the first column of the following table:

The system needs to fill a high-level slot that identifies a particular restaurant, but the information may be provided indirectly from a collection of lower-level slot-values that narrow down the set of possibilities. Note that the responses can express different slots in different orders, with variation in the natural language phrasing. The last expression shows that a single response can provide fillers for multiple slots in a fairly elaborate natural language description. The target slot names are domain-specific; they typically correspond to column names in a back end database. Given a set of slot-value pairs, application logic can retrieve results from the back-end database.

The task of the NLU module is to map from utterances in the first column to their slot-value interpretations in the second column. The NLU module must handle the variations in phrasing and ordering, if it is to find the meaning with a high level of accuracy. A simple strategy for NLU is to match the utterance against a template pattern that instantiates the values for the slots:

In this simple approach, every phrase variation would require its own template. A more sophisticated pattern matcher could use regular expressions, context-free grammars, or rules in more expressive linguistic formalisms, so that a few rules could cover a large number of variations. In any case, these approaches need to resolve ambiguities that arise in the matching.

The templates or rules give the context in which specific entities or key phrases are likely to occur. The Named Entity Recognition (NER) task is often a separate processing step that picks out the substrings that identify particular entities of interest (the restaurant name and cuisine-type in this example). Machine learning approaches like the one in [57] are typically used for named entity detection. These techniques have been designed to handle variations in phrasing and ambiguities in the matching, but they require a large set of example utterances marked up with the correct slot-value pairs. The marked-up utterances are then converted into IOB notation, where each word is given one of the following kinds of tags:

The and tags have a slot name associated with them. An example of an IOB-tagged utterance is:

The IOB-tagged utterances comprise the training data for the machine learning algorithm. At this point, the task can be regarded as a sequence classification problem. A common approach for sequence classification is to predict each label in the sequence separately. For each word, the classifier needs to combine features from the surrounding words and the previous tags to best estimate the probability of the current tag. A well-studied approach for combining evidence in a probabilistic framework is the conditional maximum entropy model described in [58]:

where and are the tag and available context (resp.) for the word at position . The denote features that encode information that is extracted from the available context, which typically consists of a few previous tags, the current word, and a few surrounding words. The are the parameters of the model; they effectively weight the importance of each feature in estimating the probability. A search procedure (e.g., Viterbi) is then used to find the maximum probability tag sequence.

It is not desirable to collect training data that mentions every possible value for the slots. Furthermore, features that include explicit words do not directly generalize to similar words. For these reasons, machine-learned approaches often use external dictionaries. If a word or phrase exists as a known value in a dictionary, the model can use that knowledge as a feature. Both [57] and previously [59] use maximum entropy models to combine contextual features and features from external resources such as dictionaries. More generally, words can automatically be assigned to classes based on co-occurrence statistics as shown in [60], and features based on these word classes can improve the generalization capability of the resulting model, as shown in [61].

Recent neural net approaches such as [62] attempt to leverage an automatically derived mapping of words to a continuous vector space where similar words are expected to be “close”. Features in this approach can then directly make use of particular coordinates of these vector representations.

The conditional random field (CRF), described in [63] is another model for sequence classification that produces a single probability for the entire sequence of labels, rather than one label at a time. See [64] for an example of CRFs applied to named entity detection.

3.8.2 Limitations of Slot and Filler Technology

A mobile assistant can complete many tasks successfully, based only on values that the NER component identifies for the slots of an action template. Regarding the slot values as a set of individual constraints on elements in a back-end database, systems often take their conjunction (e.g. “Cuisine: Italian” and “Location: San Francisco”) as a constraint on the appropriate entries (“Zingari's”, “Barbacco”) to extract from the back-end. This rudimentary form of natural language understanding is not enough if the user is allowed to interact with more flexible utterances and more general constraints.

Consider the contrast between “an Italian restaurant with live music” and “an Italian restaurant without live music”. These mention the same attributes, but because of the preposition they describe two completely different sets of restaurants. The NLU has to recognize that the prepositions express different relations, that “without” has to be interpreted as a negative constraint on the fillers that can fill the Name slot and not a specific set of restaurants. Prepositions like “with” and “without”, and other so-called function words, are often ignored as stop-words in traditional information retrieval or search systems, but the NLU of a mobile assistant must pay careful attention to them.

Natural languages also encode meaning by virtue of the way that the particular words of an utterance are ordered. The description “an Italian restaurant with a good wine list” does not pick out the same establishments as “a good restaurant with an Italian wine list”, although presumably there will be many restaurants that satisfy both descriptions. Here the NLU must translate the order of words into a particular set of grammatical relations or dependencies, taking into account the fact that adjectives in English typically modify the noun that they immediately precede. These relations are made explicit in the following dependency diagrams.

Figure 3.13 represents the output of a dependency parser, a stage of NLU processing that typically operates on the result of a name-entity recognizer. A dependency parser detects the meaningful relationships between words, in this case showing that “Italian” is a modifier of “restaurant”, that the preposition “with” introduces another restriction on the restaurant, and that “good” modifies “wine list”.

Dependency parsers also detect relationships within full clauses, identifying the action of an event and the participants and their specific roles. The subject and object labels shown in the Figure 3.14 restrict the search for movies to those in which Harry is saved by Ron and not the other way around. The grammatical patterns that code dependencies can be quite complicated and can overlap in many ways. This is a potential source of alternative interpretations in addition to the ambiguity of named-entity recognition, as shown in Figure 3.15.

According to the grammatical patterns of English, the “after” prepositional phrase can be a modifier of either “book” or “table”. The interpretation in the first case would be an instruction to do the booking later in the day, after the meeting. The second and more likely interpretation in this context is that the booking should be done now for a table at the later time. A dependency parser might have a bias for one of the grammatical patterns over the other, but the most plausible meaning might be based on information available elsewhere in the dialog system – for example, in an AI and reasoning module that can take into account a model of this particular's past behavior or knowledge of general restaurant booking conventions.

Machine learning approaches have also been defined for dependency parsing [65, 66]. As for named entity recognition, the task is formulated as a classification problem, driven by the information in a large corpus annotated with dependency relations. One technique considers all possible dependencies over the words of the sentence and picks the maximum spanning tree, the collection of dependencies that scores best against the training data [67]. Other techniques process a sentence incrementally from left to right, estimating at each point which of a small set of actions will best match the training data [68]. The actions can introduce a new dependency for the next word or save the next word on a stack for a later decision.

There are also parsers that produce dependency structures or their equivalent by means of large-scale manually written grammars [69–71]. These are based on general theories of language and typically produce representations with much more linguistic detail. Also, they do not require the construction of expensive annotated corpora and are therefore not restricted by the phenomena that such a corpus exemplifies. However, they may consume more computational resources than statistically trained parsers, and they require more linguistic expertise for their development and maintenance. These considerations may dictate which parsing module is most effective in a particular mobile assistant configuration.

Dependency structures bring out the key grammatical relations that hold among the words of a sentence. But further processing is necessary for the system to understand the concepts that the words denote and to translate them into appropriate system actions. Many words have multiple and unrelated senses that the NLU component must be able to distinguish. It is often the case that only one meaning is possible, given the tasks that the mobile assistant can perform. The word “book” is ambiguous even as a verb (make a reservation vs. put someone in jail), but the first sense is the only plausible one for a reservation-making assistant. It takes a little more work to disambiguate the word “play”:

• Who played Serena Williams?
• Who played James Bond?

The same word has the “compete-with” sense in the first question and the “act-as” meaning in the second. Which sense is selected depends on the type of the object. The compete-with sense applies if the object is an athlete, the act-as is selected if the object denotes a theatrical character. Disambiguation thus depends on named entity recognition (to find the names), reference resolution (to identity the entities that the names refer to), and parsing (to assign the object grammatical relation). In addition, disambiguation depends on ontological reasoning: the back-end knowledge component knows that Serena Williams is a tennis player, tennis players are classified as athletes, and that category matches the object-type condition only of the compete-with sense.

The reasoning needed for disambiguation is not tied to just looking up the categories of names. Category information for definite and indefinite descriptions is also needed for disambiguation, as in:

• Who played the winner of the French Open?
• Who played a Stradivarius?

The first case needs information about what sorts of entities are winners of sporting events, namely athletes; the second case requires information about what a Stradivarius is, namely a stringed instrument. This information can then be fed into a module that can traverse the ontology to reason, for example, that stringed instruments are objects that make sounds and thus match the object-type condition for play in the sense of making music.

These examples fit within RDFS [72], a small ontology language used in conjunction with RDF, the “resource description framework” [73] for representing simple information about entities in the Semantic Web. RDFS permits representation of types of object (as in Serena Williams is a tennis player and a person), generalization relationships between these types (as in a tennis player is an athlete), and typing for relationships (as in a winner is a person).

More complex chains of reasoning can also be required for disambiguation, including combining information about multiple entities or descriptions. In these more complex cases, a more powerful ontology language may be required, such as the W3C OWL Web Ontology Language [74]. OWL extends RDFS with the ability to define categories (such as defining a man as a male person) and providing local typing (such as the child of a person being a person). Ontological reasoners are a special case of the more general knowledge representation and reasoning capabilities that may be needed not only to resolve more subtle cases of ambiguity, but also for the planning and inferences that underlie more flexible dialog interactions (see section 3.10.6). These may require the ability to perform more intricate logical deductions (e.g., in first-order predicate logic) at a much higher computational cost than relatively simple ontology-based reasoning.

Certain words in a user input take their meaning from the context in which they are uttered. This is the case for pronouns and other descriptions that refer to entities mentioned earlier in the conversation. If the system suggests a particular restaurant that satisfies all of the requirements that the user has previously specified, the user may further ask “Does it have a good wine list?” The system then must recognize (through a process called anaphora resolution – see Mitkov, [75]) that the intended referent of the pronoun “it” is the just-suggested restaurant. The user may even ask “What about the wine list?”, a question that does not contain an explicit pronoun but yet is still interpreted as a reference to the wine list of the suggested restaurant. The linkage of the definite description (“the wine list”) to the particular restaurant depends on information from an ontology that lists the parts and properties of typical restaurants.

There are other words and expressions that do not refer to entities previously mentioned in the conversation. Rather, they point directly to objects or aspects of the situation in which the dialog takes place. Demonstrative pronouns (this, that, those …) and other so-called indexical expressions (now, yesterday, here, there …) fall into this class. If the dialog takes place while the user is driving in a car, the user may point to a particular restaurant and ask, “Does that restaurant have a good wine list?” In this case the dialog system must recognize that the user is making a pointing gesture, identify the target of that gesture as the indicated restaurant, and offer that information to the NLU component so that it can assign the proper referent to the “that” of the user's utterance.

Other aspects of the dialog context (e.g., current location and time) must similarly be taken into account if the user asks “Are there any good restaurants near here?” or “What movies are starting an hour from now?” These examples show that a dialog system must be able to manage and correlate information of different modalities coming in from different channels. One tool for handling and synchronizing multi-modal information is EMMA, the W3C recommendation for an extensible multi-modal annotation mark-up language [76].

3.10.1 Technical Challenges

Consider the following mock dialog with an automated Virtual Assistant (VA) of the future:

1. Bob> Book a table at Zingari's after my last meeting and let Tom and Brian know to meet me there.
2. VA> Sorry, but there aren't any tables open until 9 pm. Would you like me to find you another Italian restaurant in the area at about 6:30 pm?
3. Bob> Can you find a table at a restaurant with a good wine list?
4. VA> Barbacco has an opening. It's in the Financial District but the travel time is about the same.
5. Bob> Ok. That sounds good.

Utterance (1) is ambiguous in terms of the time of the requested reservation: should it take place after the meeting or should it be performed now? Resolution of this ambiguity requires background commonsense knowledge that needs to be represented by the system: reservations should be done as early as possible, otherwise the space in a restaurant might fill up. There are default assumptions that are also necessary to correctly interpret this exchange: the referenced “last meeting” is today's last meeting and not tomorrow's.

The reasoning here involves an appeal to general principles of communication [96]. People tend to be as informative as needed; if the person wanted the dinner tomorrow, he would have said so. However, this is again no more than a defeasible assumption, as it need not always hold; imagine the dialog having been prefaced with some discussion about what the person had planned for tomorrow. Similarly, the interpretation of the prepositional phrase, “after my last meeting” must be handled in a similar fashion, as tomorrow or the day after, for example, would also satisfy that constraint.

Of course, the above inferences regarding the time of the planned dinner are only approximate; a scheduler will need more exact information. The system could explicitly ask for the time, but a truly helpful assistant should make an effort to “fill in the blanks” as much as possible; here, the system should attempt to create some reasonable expectation regarding the best time for the dinner. Toward that end, the VA can try to base its reasoning on knowledge of past behavior; it may know that Bob works until 5 pm and that he typically spends 30 minutes on email before leaving work. Such information would reside in a user model of typical behavior that, as we shall see, should likely also include information about the user's desires or preferences. In addition, the system should factor in travel time based on possible locations of whatever restaurant is chosen. Finally, the identity of Tom and Brian must be ascertained. This is information that, again, would be kept in a user model of friends and phone numbers.

It is worth highlighting the important general principle that this utterance illustrates – the dialog system must be able to take a variety of contextual factors into account as it engages with the user. These include elements of the conversational history, as we have indicated before, but also many non-conversational aspects of the user and the situation in which the dialog takes place. Appropriate system behavior in different settings may depend, for example, on the time of day, the user's physical location, current or anticipated traffic conditions, music that the user has recently listened to or movies that have been recently watched. The dialog system must receive and interpret signals from a variety of sensors and must maintain a history not only of the conversation, but also of previous events and actions.

In utterance (2), we see that the initial search for a restaurant satisfying the expressed and implied constraints fails. An uninformative response such as “No” or “I could not find a restaurant for you” would hardly be helpful. A pragmatically more informative response is provided here in terms of a gloss of the reasons for the failure, and then an attempt to propose alternatives. Alternatives can be sought by relaxing some of the less important constraints; in this case, the specification of the type of restaurant and the time of the dinner are relaxed. This activity should be the responsibility of a dialog management module that guides the system and user to reach agreement on an executable set of constraints, while accessing the user model as much as possible to capture the relative importance of the constraints.

In utterance (3), we have what is known in the literature as an indirect speech act [97–99], which is discussed in more detail in section 3.13.3. If we take the utterance literally, it can be answered with a simple yes or no. However, neither would be very satisfying; the utterance, in fact, is a disguised request to perform an action. The action implicitly referred to is the dinner reservation. With respect to management of the dialog, notice that the user himself has implicitly responded to the question posed in (2). This again falls out of general principles of communication having to do with conciseness of expression. Since the user does not disagree, there is an implicit confirmation and, in the process, a new constraint is exposed by the user – the availability of a good wine list. At some point, these constraints must be collected to drive a search. This requires that the interpretation of utterances should be properly constrained by the relevant previous utterances. In (3), it means that the request should be interpreted as a request to find an Italian restaurant with a good wine list. At this point, a number of relevant databases and websites can be brought to bear on the search.

As the dialog progresses to (4), the VA informs the user that it has dropped one of the earlier constraints (“restaurant in the area”) in preference to others, such as “the same travel time”, “Italian restaurant”, and “tonight”, through the same sort of process employed during the processing of utterance (2). Bob then confirms the proposal in (5) and the dialog ends. The VA can now go to an appropriate online website to make the reservation and send the requested emails to Tom and Brian. However, the duties of a good assistant are not yet complete. It must be persistent and proactive, monitoring the plan for unexpected events such as delays and responding in a helpful manner.

Given these technical challenges, what follows is an overview of some of the most common approaches found in the literature to address these problems.

3.10.2 Semantic Analysis and Discourse Representation

Much of the dialog that involves virtual assistance is about actions that need to be taken in the world. From the perspective of semantic and discourse levels of analysis, one approach is to reify events and map the syntactic structure into a first order logical representation in which constant symbols stand for particular events (say, the assassination of Kennedy) that can have properties (e.g., a “killing”) and relations to other events. Consider the fragment, “Can you find me a restaurant”, of utterance (3). The following formula represents such a translation:

This can be glossed as saying that the variable represents a surface request (see below) whose agent is Bob and the request is in terms of , an event of type “find” performed by agent VA(a virtual assistant is also sometimes called a Personal Assistant, PA). The object of the “finding” event is , which is a restaurant. The advantage of such a representation is that one can conjoin additional properties of an event in a declarative fashion: for example, one can add additional constraints, such as that the restaurant be Italian: italian . One problem, however, is that from a logical perspective the addition of such a constraint must be done by re-writing the entire formula, as the constraint must occur within the scope of the existential quantifiers.

One solution to this problem has been proposed by Discourse Representation Theory (DRT), according to which a dynamic model of the evolving discourse is maintained in structures that can be augmented with new information. The figure below shows such a Discourse Representation Structure (DRS) for the complete utterance (3). The “box” illustrated in Figure 3.16 lists a set of reference markers corresponding to the variables that we have mentioned: , and , followed by a set of conditions involving those variables. Such structures can be augmented with new information and then, if desired, translated into a first order logic form for more general reasoning (as shown to the right).

3.10.3 Pragmatics

There are many pragmatic issues that arose during the analysis of our target user-VA interaction. One particularly succinct expression of a set of general maxims that conversational agents should adhere to was proposed by the philosopher Grice [96]. These maxims state that a speaker should:

1. Be truthful.
2. Be as informative (but not more so) as necessary.
3. Be relevant.
4. Be clear, brief and, in general, avoid ambiguity.

How these maxims are to be captured computationally is, of course, a major challenge. They also represent only desirable default behavior; agents can violate them and, in the process, communicate something by doing so [100]. These maxims also reflect the efficiency of language – the fact that one can communicate much more than what is explicitly said. We saw an example of this in that utterance (3) needed to be interpreted relative to the prevailing context, in order to correctly ascribe to the user a request to find an Italian restaurant with a good wine list (and at the desired time and date).

The proper treatment of speech acts is also a central topic in pragmatics. Speech acts are utterances that are best interpreted as actions that can change the world somehow (specifically, the beliefs and intentions of other agents) as opposed to having a truth value based relative to a state of affairs. In the case of our VA, speech acts must be translated into intentions or commitments on the part of the VA to do something for the user. Often, the intention is not explicit but must be inferred. A simple example of the need for such inferences can be found in the above exchange; it probably escaped the reader that nowhere in the dialog does the user specify that he or she wants to eat dinner at the restaurant. This might appear to be a trivial observation, but if the VA decided to make a reservation at a restaurant which, for example, only served meals during the day or drinks at night, that choice would not satisfy the user's desires.

In the initial DRS for utterance (3), we have that the utterance was interpreted as a request to find a restaurant but, through a process of intention recognition, this is transformed to the structure shown in Figure 3.17. This represents a request to reserve the restaurant, the actual intent of the utterance. The plan recognition process works backwards from the find action and reasons that if a user wants to find a restaurant, it is probably because he wants to go to the restaurant, and if he wants to go to the restaurant a plausible precondition is having a reservation. In the helpful role that the VA plays, that translates to a task for the system to reserve the restaurant for the user.

In additional to logic-based approaches to plan recognition [91, 92], probabilistic methods have been developed which can explicitly deal with the uncertainty regarding the system's knowledge of the (inner) mental state of the user [80].

3.10.4 Dialog Management as Collaboration

Many approaches have been put forward for managing a dialog and providing for assistance. Most approaches are grounded in the observation that dialogs commonly involve some associated task. A dialog, then, is a collaborative activity between two agents: a give-and-take in which the agents are participating in a task and, in the process, exchange information that allows them to jointly accomplish the task. The major approaches might be divided in the following way:

• Master-slave sorts of approaches, in which the interaction is tracked and managed relative to a set of pre-defined task hierarchies (which we will call recipes), sometimes with the speech acts represented explicitly.
• Plan-based approaches, which model the collaboration as a joint planning process in which a plan is a rich structure in which a recipe might not be defined a priori but constructed at run time.
• Learning approaches that attempt to acquire prototypical dialog interactions.

We will expand a bit on plan-based approaches, as they provide an attractive approach for also modeling the collaborative support that a VA needs to provide.

Plan-based models to dialog understanding architect an agent – be it a human, a computer system or a team – in terms of the beliefs, desires and intentions of an agent. Without going into philosophical details, it is enough to think of beliefs as capturing the information that a user has in a particular situation (for example, the availability of a table at a particular restaurant or the route to a particular location). Of course, an agent's beliefs can be wrong, and one of the responsibilities of the VA is to try to detect any mis-information that the user might have (e.g., he might incorrectly think that a particular restaurant is in another part of town). In a dialog setting, the agent's beliefs might reference those objects that are most “salient” or currently under discussion (e.g., “the Italian restaurant” that I am going to is “Zingari”).

Desires reflect the user's preferences (e.g., the user might prefer Italian over Chinese food; or the user might prefer to travel by freeway whenever possible). Intentions capture what the agent is committed to. For example, the system might be committed to making sure that the user gets to the restaurant in time for the reservation. It will therefore persistently monitor the status of the user's progress toward satisfying that intention.

One important role of a virtual assistant is to assist a user in elaborating the high-level intentions or plans that the user has communicated to the VA, using elements from a library of task recipes. Once a plan is elaborated upon, the resulting set of potential options (if there is more than one) are examined, and the one that has higher payoff (or utility, for example, get the user to the restaurant on time) is chosen for action.

3.10.5 Planning and Re-planning

Planning makes use of recipes that, as we said, encodes alternative means for performing actions. In our mock dialog, suppose that are three ways of making a reservation: online by going to Opentable, going to the restaurant website, or calling the restaurant directly. The user and the system would then jointly try to fill in the details to those recipes or compose them in some way. Each agent brings with it complementary capabilities and responsibilities. The dialog, then, captures the contributions that each makes or proposes to make toward advancing that joint goal.

Recipes include logical constraints on constituent nodes. They can be either deep structures defined a priori and instantiated for a particular goal, or they can be shallow decompositions which can be composed during the planning process. Figure 3.18 illustrates examples of the latter type in the context of our example. Building a complex structure out of these at planning time allows for more flexibility in accommodating unexpected contingencies.

3.10.6 Knowledge Representation and Reasoning

The system's knowledge about, for example, types of restaurants, travel times, and beverages and menus for restaurants are stored in a knowledge representation. First order logic, a very expressive knowledge representation, is one of the many options. For tractability, alternatives include ontology-based description logics that have been explored in connection with the Semantic Web. These are particularly effective for many examples of word-sense disambiguation, as mentioned in section 3.8.2. In some cases, specialized knowledge representations might be needed for temporal relations, default knowledge, and constraints, and these may require specialized reasoners.

Throughout, we have been referring to a user model of preferences. Preferences are directly related to the agent's desires. Preferences can be offered by a user, elicited by the VA, or learned by observation. They can be expressed either qualitatively, in terms of an ordering on states of the world, or numerically in terms of utilities. For example, we might have a simple user model that states that a user likes Peet's coffee. However, more interesting are statements which express comparative preferences, as in preferring Peet's over Starbucks. These are often called ceteris paribus preferences, as they are meant to capture generalizations, all other things being equal. Exceptions need to be dealt with, however. For example, one might also prefer espresso over American drip coffee, and from that one might want to be able to conclude that one would prefer Starbucks over a café (such as Peet's) with a broken espresso machine, that being the exceptional condition. As these preferences are acquired from the user, they must be checked for consistency, as the user might accidentally state circular or inconsistent preferences. If so, the system should engage the user in a dialog to correct such problems.

3.10.7 Monitoring

Let us continue the above scenario as follows.

1. [VA notices that it is: 5:30 pm and Bob has not left the office, cannot get to the restaurant on time. MA phones Bob, via TTS]
2. VA> Bob, you're running late. Should I change the reservation?
3. Bob> Yes, I'll leave in about 30 minutes.
4. [VA replans: Barbacco is not available later. Based on stored preferences, VA reserves at another similar restaurant.]
5. VA> Barbacco could not extend your reservation, so I reserved a table for you at Capannina. They have a good wine list. I'll also let Tom and Brian know. Is that OK?
6. Bob> Yes. Thanks.
7. [VA sends text messages to Tom and Brian, sets up another monitor]

At the end of the original scenario, the VA sets up a monitor (a conditional intention) to make sure that the plan involving the choice of restaurant, reservation and dinner attendance can be completed. The intention is relative to the VA's beliefs. The conditional intention should be checked at every time step to see if it is triggered by some changing circumstances. In this case, if the VA comes to believe that Bob has not left his meeting by the expected time, then it should form the intention to replan the reservation activity.

In the remainder of the scenario, that is exactly what happens: the VA notices that Bob has not left the meeting. It checks the restaurant and finds that the reservation cannot be extended and so, as part of helpful collaborative support, it looks for alternative restaurants based on its knowledge of Bob's requirements for dinner and his preferences: the area of the restaurant, the type of food and the wine list. It locates a substitute, Capannina, which, although not in the same area, has the same travel time. It goes ahead and drops the location constraint, goes ahead and books the restaurant and lets Brian and Tom know about the changes.

3.10.8 Suggested Readings

This section has provided only a cursory overview of the relevant areas of research. The interested reader can refer to the following for supplementary information.

1. A good overview of commonsense reasoning, first order logic, techniques such as reification and alternative event representations can be found in the text of Davis (1990) [101]. In addition, the proceedings of the bi-annual conference on Logical Formalizations of Commonsense Reasoning will provide the reader with the most current work in this area [102].
2. A Good presentation of DRT can be found in Kamp and Reyle (1993) [103] and Gamut (1991) [104]. A related approach is Segmented Discourse Representation Theory, SDRT [105]. A good overview of the field of pragmatics can be found in Levinson (1983) [106], including detailed discussions on Grice's Maxim's of conversation [96]. Details on speech acts can be found in [97, 99]. The proceedings of the annual conferences on plan recognition provide a good overview of alternative approaches.
3. Good introductions to the field of knowledge representation can be found in introductory texts [107, 101]; more recent research in this area, including default reasoning, can be found in the proceedings of the annual KR conferences [108]. An overview of description logics can be found in [109]. Utility theory as related to the representation of preferences is also discussed in [107]. A number of tools have been developed for representing preferences [110].
4. Seminal papers on plan-based approaches to dialog processing include [111, 112]. The information-based approach to dialog processing is presented in [113]. Recent work in dialog processing can be found in [114]

3.11.1 Question Analysis

Analysis of a question may involve not only determining what the question is asking, but also why the question is being asked. “Are there any restaurants that serve vegetarian food near here?” is technically a question with a yes or no answer, but a useful answer would provide some information about what restaurants are available. “Useful answer” depends on the asker's intent (if all they are trying to do is confirm previous information, then “yes” is the appropriate answer, not a complete description of the information). Determining the asker's intent depends on the conversation, the domain, and knowledge of the world (in this case, it is necessary to know the asker's location).

Question analysis typically determines the key terms in the question and their relations. The key terms (entities) are usually the nouns. Relations can be the main predicate (which largely signals the asker's intent) or constraints on the answer. For example, for “Are there any restaurants that serve vegetarian food near here?” the intent is a list of restaurants that meet the constraints of serving vegetarian food and are near the asker's current location; “restaurants”, “vegetarian food” and “here” are the entities.

Common simple questions can be handled with patterns (“What time is <event>?”), but are not robust to variations and less common linguistic patterns. Parsing (see Section 3.8.2) is a common approach but subtle constructions of language can be hard to parse accurately, and thus parsing is typically complemented by statistical entity- and intent-detection (see Section 3.8.1). Dictionaries of known entities (such as lists of movie actors, medication names, book titles, political figures, …) can also be effective to locate common types of entities, particularly for specific domains.

3.11.2 Find Relevant Information

Once the intent(s) and the entities have been determined, we locate information that might be relevant to the intent. For the example, for “Are there any restaurants that serve vegetarian food near here?” we could look in databases of restaurants, look in a business directory based on the asker's location, or do a general Internet search. From those results, we can compile a list of restaurants that meet the constraints (“have vegetarian dishes on the menu” and “near current location”).

Much information exists only in structured form (tables or databases, such as historical player information for baseball teams, while other kinds of information exists only in unstructured form (documents in natural language, such as movie plot summaries). Accessing information in structured sources requires precise question analysis (the asker may not know how the database designer created the field names, so the question analysis needs to map the semantics of the question to the database fields). Accessing unstructured information with search (either on the Internet or in a specific set of source documents) requires less precision, but leads to many more potential items that could be answers, making it harder to select the correct answer.

3.11.3 Answers and Evidence

Most work on QA has focused on “factoid” answers, where the answer to a question is succinctly encapsulated in a single place in a document (e.g. What is the capital of Peru? “Lima is the Peruvian capital.”) There has been less work on non-factoid answers [118], especially ones that have to be put together from evidence coming from more than one place (e.g., text passages from different parts of the same document, text passages from different documents, combinations of structured data and raw text).

The evidence supporting both factoid and non-factoid answers may differ substantially from the language of the user's question, which has led to recent interest in acquiring paraphrase information to drive textual inference [119]. Non-factoid answers arise either from inherently complex questions (Why is the sky blue, but often red in the morning and evening?), or from qualified answers to simple questions (When can I reserve a table at Café Rouge: if it's a table for 2, at 7 pm; a table for 4 at 7:30; at table for more than 4 at 8:30; or, Café Rouge is closed today).

3.11.4 Presenting the Answer

Having assembled the evidence needed to provide an answer, the system must find a way of presenting it to the user. This involves strategic decisions about how much of the evidence to present, and tactical decisions about the best form of presenting it [120]. These decisions are informed by the answer medium (spoken, text on a mobile display). However, for QA embedded in dialog applications, the background goals (question under discussion) have a significant impact on strategic decisions. At the tactical level for generating NL, possibly dispersed text passages must be stitched together in a coherent and natural way, while NL answers from structured data must either be generated from the data, or textual search carried out to find text snippets to present or support the answer.

Since machine learning systems can potentially benefit and adapt from getting feedback on their actions, capturing user reactions to system answers is desirable. However, this is not likely to succeed if the feedback has to be given in an unnatural and obtrusive way (e.g., thumbs up/down on answers). Instead, more subtle clues to success or failure need to be detected (e.g., the user repeating /reformulating questions, abandoning tasks, the number of steps required to complete a task [121]).

3.12.1 Distributed User Interfaces

Devices like phones or TVs often form hubs for other mobile devices, which may have less computational capacity, but which may provide a more effective and direct interface to the user, supplementing or replacing the UI of the hub device. For example, a phone may be connected to smart glasses, a connected watch, and a wireless headset, distributing the task of channeling information between the user and the device making more effective, natural, and pleasant use of the peripherals.

As discussed earlier in section 3.8.2, the various modalities may overlap and complement one another. Consider for instance a graphical representation on a map of all towns named ‘Springfield’, displayed in response to the user entering a navigation destination. Pointing to the correct target, she specifies “this one”, with gesture recognition identifying the position of the target, and the spoken command conveying the nature of the directive and the time at which the finger position is to be measured.

As the manufacturers of these devices vie for predominance of their particular platforms, users are dividing their attention and interact with multiple devices every day. This has exacerbated the need for a ‘portable’ experience – a continuity of the functionality, the interaction model, the user's preferences and interaction history across these devices.

A pan-device user profile will soon become essential. This stored profile will contain general facts learned about the user, such as a preference for a specific music style or news category, information relevant in the short term such as the status of an ongoing airline reservation and booking dialogue, and also information relevant to voice recognition, such as acoustic models. Devices will use voice biometrics to recognize users, access a server-based user profile, adapt it during use, and update it back on the server after the session ends, making it available for access from the next device with which the user interacts.

A user might search for restaurants on his smartphone, which would then be stored in his or her user profile. Later, on a desktop PC, with a larger screen available, he or she might choose one venue. Getting into his or her car, this location would be retrieved by the onboard navigation from the user profile and, as the recent dialogue context is also available via the profile, a simple command like ‘drive to the restaurant’ is sufficient to instruct the navigation system.

In this model, the human-machine interface design no longer focuses on the interaction between the human and a particular machine. The machine's role is turning into a secondary one: it becomes one of many instantiations of a common, multi-device strategy for directly linking the user to data and services.

A common construct for this type of abstracted interface is the ‘virtual assistant’, which mediates between the user and information and services. Such an assistant has access to a server-based user profile which aggregates relevant information from all devices favored by the user. The manifestation of the assistant may itself be personalized, so that it exhibits the same TTS voice, speaking style and visual guise, to ensure the cross-device dialog forms a continuous, personalized experience. The user thus no longer focuses on interacting with hardware, but on being connected to the desired information, either directly or through the virtual assistant. The interaction model shifts from the use of a human-machine interface to a personalized human-service interface.

Just as the UI can be distributed across multiple interaction sessions on multiple devices, the services may also be spread out across multiple devices and sources. Again, the hardware moves to the background as the UI groups functionality and data by domains, not by device.

Consider, for example, an automotive music app that has access to music on the car's hard drive juke box, an SD memory card, a connected phone, and internet services. A user experience designer may elect to make content from all these sources available in one homogeneous set, so a request “play some jazz” yields matching music from all the sources.

3.12.2 Distributed Speech and Language Technology

For speech and language UIs, the location of the processing is largely determined by the following considerations:

• Capacity of the platform: CPU, memory, and power profile.
• Degree of connectivity: the speed, reliability and bandwidth of the connection, and additional costs for connectivity, e.g., data plan limits.
• The type and size of models needed for voice recognition and understanding of the application's domains. For example, are there 100,000 city names that need to be recognized in a variety of contexts, or only a few hundred names in a user's contact list?

The following device classes exemplify the spectrum of different platforms:

• PCs: ample CPU and memory, continuous power supply. Typically connected to the internet. Native domains: commands to operate software and PC, text dictation.
• Mobile phones and tablets: limited CPU and memory, battery-driven. Often connected to the internet, connection may be more costly and not stable (e.g., when coverage is lost).
• Cars: limited CPU and memory, continuous power supply. Often connected to the internet, connection may be more costly and not stable.
• TVs: limited CPU and memory, continuous power supply. Often connected to the internet, not every user might connect the TV.
• Cloud servers – vast CPU and memory resources feeding multiple interactions at the same time. Connected to the internet and other large data sources.

Increased connectivity has given rise to hybrid architectures that blur the lines between traditional embedded versus server-based setups and also lead to a number of functions and domains that are expected on all personal devices – for instance, information search, media playback, and dictation.

When considering how to allocate tasks in a distributed architecture, the mantra used to be do the processing where the data is – which, with growing connectivity bandwidth, is no longer a requirement but still a good guideline. UI consistency is also an essential aspect; say the natural language or dialogue components run entirely on a remote server. If a data connection is lost, it is easy for the user to understand that connected data services like web search are interrupted, but it may not be clear that the capacity to converse in a natural language dialogue is also no longer available.

In a speech and language UI, the embedded, “on-board” speech recognition typically handles speech commands to operate the given device. This may be using a grammar-based command-and-control type recognizer or a small statistical language model (SLM) enabling natural language processing. Contemporary mobile platforms, however, reach their limits when attempting to recognize speech with SLMs filled with large slot lists with tens of thousands of city names. This task would thus be carried out by a server-based recognizer. In many cases, it is advisable to perform recognition both on the embedded platform and on the server at the same time, compare the confidences of the results, and then select the best one, to avoid latencies one would incur if only triggering the server speech recognition after a low-confidence onboard outcome.

Other tasks that may reside on the onboard recognizer are wake-up-word detection, possibly in combination with voice biometrics – to activate a device and authenticate the user, respectively, speech activity and end point detection to segment the audio, and speech recognition feature extraction, so that only the features rather the full audio need to be transferred to the recognition server.

The user profile is beneficial for storing personal preferences relevant for dialogue decisions, speaker characteristics and vernacular for acoustic and language modeling. It can also hold biometrics information so that the user's identity can be verified to authorize use of a service or access of data. This is most powerful if the profile is available to the user from any device, but it should also be functional if the device loses connectivity, e.g., when a car drives through a tunnel. This is solved by a master user profile in the Cloud with synchronized copies on local devices, or by making the phone the hub for the profile, as it accompanies the user at most times.

Storing such a profile on a server also offers the advantage that the group of these profiles forms an entity of its own containing a vast amount of information, and allows deriving statistics of the user population or parts thereof. A news service may be interested in finding the trending news search keywords found in all logs connected to the group of profiles. A music web store could query the group of profiles for the artists most commonly requested by male listeners aged 18–25 in the state of California.

Often, profiles of different users are connected to each other, say, because users A and B are in each other's email address book or linked via a social network. If this information is stored in the user profile, the group of connected profiles spans a large graph that, for instance, could allow a user's virtual assistant to conduct queries such as, “do I have any friends or friends of friends that are in the town I'm currently visiting?” or “what music are my friends listening to?” Even more so than with server-based recognition and logging, when storing data in user profiles, privacy and data security are a key matter for designing and operating the server infrastructure.

Lastly, on the output side, the TTS (text-to-speech) and language generation usually run on the user's device, unless a high-quality voice requires more memory than available locally, or if an entire app is hosted and a server solution is more convenient to develop and maintain.