# Cortical Surface Diffusion Generative Models

###### Abstract

Cortical surface analysis has gained increased prominence, given its potential
implications for neurological and developmental disorders. Traditional vision
diffusion models, while effective in generating natural images, present
limitations in capturing intricate development patterns in neuroimaging due to
limited datasets. This is particularly true for generating cortical surfaces
where individual variability in cortical morphology is high, leading to an
urgent need for better methods to model brain development and diverse
variability inherent across different individuals. In this work, we proposed a
novel diffusion model for the generation of cortical surface metrics, using
modified surface vision transformers as the principal architecture. We
validate our method in the developing Human Connectome Project (dHCP) with
results suggesting that our model demonstrates excellent performance in
capturing the intricate details of evolving cortical surfaces. Furthermore,
our model can generate high-quality realistic samples of cortical surfaces
conditioned on postmenstrual age (PMA) at scan.

Index Terms—  Diffusion models, cortical surface, generation models

##  1 Introduction

The human cerebral cortex is a highly-convoluted sheet of grey matter that is
best modeled as a surface [1, 2, 3]. As one of the most highly evolved areas
of the brain relative to non-human primates, cortical function underpins many
aspects of higher-order cognition and is implicated in many neurological and
psychiatric disorders [4, 5]. Unfortunately, localising signs of pathology in
individual brains can be extremely challenging due to the scale of variation
of human cortical organisation [6, 7, 8], which obscures subtle disease.
Therefore, a primary goal of translational neuroimaging is to develop methods
that accurately disentangle healthy variation from pathology.

One approach that has gained recent prominence is normative modeling. Here the
objective is to learn a generative model that encodes how brains vary normally
relative to continuous phenotypes such as age or behavioural scores, from
which signs of disease may be detected as outliers from the model [9, 10].
Classically normative models of cortical variation have been fit with Gaussian
Process Regression (GPR) [9, 10] or Generative Additive Models of Location
Scale and Shape (GAMLSS) [11]. However, these require hand engineering of
imaging features, generally using traditional image processing pipelines that
combine diffeomorphic image registration with label propagation of cortical
areas from population average templates. Approaches that have been shown
repeatedly to under-estimate the full scale of cortical variation [3].

A potentially more powerful approach is to use deep generative models to
encode normal brain variation and disentangle it from disease [12]. To this
end, denoising Diffusion Probabilistic Models (DDPM) [13] have recently
emerged as extremely powerful generators of natural images. Several works [14,
15] have already gained great success in adapting diffusion models to non-
Euclidean data, using Stochastic Differential Equations (SDE) to approximate
samples on manifolds, but focusing on simple mesh and manifolds generation.
However, modeling cortical surfaces requires using high-resolution grids which
are not feasible with current methodologies.

To address this problem, we chose to build from recent work on the development
of surface vision transformers (SiT) [16]. These have been validated as
powerful encoders of cortical feature maps, outperforming surface
convolutional approaches to demonstrate state-of-the-art performance of
cortical phenotype regression tasks [16]. In this paper we demonstrate that,
with the use of an SiT as a backbone for DDPM generation, it is possible to
conditionally generate feature maps that accurately simulate cortical
neurodevelopment.

Fig. 1: The directed graphical model of diffusion process on cortical surface

##  2 Method

###  2.1 DDPM formulation

The basis of a DDPM [13] is a sequential diffusion model. This is essentially
a forward diffusion process that operates as a Markov chain, incrementally
applying Gaussian noise with variance $\beta_{t}\in(0,1)$ to the original data
distribution $q\left(x_{0}\right)$. The forward transformation can be
represented as follows:

$q\left(x_{1:T}\mid x_{0}\right)=\prod_{t=1}^{T}q\left(x_{t}\mid
x_{t-1}\right)$ (1) $q\left(x_{t}\mid
x_{t-1}\right)=\mathcal{N}\left(x_{t};\sqrt{1-\beta_{t}}x_{t-1},\beta_{t}\boldsymbol{I}\right)$
(2)

With $x_{0}$ representing the initial data, and
$x_{1:T}=\\{x_{1},x_{2},\ldots,x_{T}\\}$ representing the latent variables,
generated from incremental addition of Gaussian noise (Eq 2). Generation of
the diffusion model is learning to reverse the process by using a neural
network ($\epsilon_{\theta}$) to iteratively denoise samples over time-steps
$t$. The output of the model is a prediction of the statistics of the
distribution: $p_{\theta}\left(x_{t-1}\mid x_{t}\right)$:

$p_{\theta}\left(x_{t-1}\mid
x_{t}\right)=\mathcal{N}\left(\mu_{\theta}\left(x_{t}\right),\Sigma_{\theta}\left(x_{t}\right)\right)$
(3)

This model is trained with the variation lower bound of the log-likelihood of
$x_{0}$, reducing:

$\displaystyle\mathcal{L}(\theta)=$ $\displaystyle-p\left(x_{0}\mid
x_{1}\right)+$ (4) $\displaystyle\sum_{t}\mathcal{D}_{KL}$
$\displaystyle\left(q\left(x_{t-1}\mid
x_{t},x_{0}\right)||p_{\theta}\left(x_{t-1}\mid x_{t}\right)\right)$

As both $q$ and $p_{\theta}$ are Gaussian noise, $\mathcal{D}_{KL}$ can be
evaluated from the mean and covariance of two distributions. So the noise
prediction network $\epsilon_{\theta}$ can be trained easily from the mean-
squared error between the predicted noise
$\epsilon_{\theta}\left(x_{t}\right)$ and the sampled Gaussian noise
$\epsilon_{t}$. To generate a sample through the process, an initial point is
drawn from $p\left(x_{T}\right)$ with the same dimensions as the original
training data $x_{0}$. Then samples $\\{x_{T-1},x_{T-2}...{x_{1}}\\}$ are
sequentially denoised by the $\epsilon_{\theta}$ until the model approximates
the original data point $x_{0}$.

###  2.2 Surface Diffusion Model

In this paper, samples $x_{0}\in\mathbb{R}^{40962\times 1}$ represent cortical
curvature maps, projected to a regular, sixth-order icospheric grid 40962
regularly spaced vertices.

Fig. 2: The figure shows the architecture of the cortical surface diffusion
model. First, the flattened input will be projected by linear embedding. Then,
positional embedding and condition embeddings (class embedding and time
embedding) would be added to the input tokens. After N transformer blocks, the
prediction of noise would be projected out by the linear decoding layer.

####  2.2.1 Surface Vision Transformer

The SiT [16] translates surface understanding to a sequence-to-sequence
learning paradigm by tessellating cortical feature maps (sampled on a regular
high resolution spherical icosahedral grid) according to regular triangular
subdivisions of a lower resolution icosahedron. In this paper, we use ico6 to
represent the data, and ico2 ($I_{2}=(V_{2},F_{2})$, $|V_{2}|=162$ vertices
and $|F_{2}|=320$) for sampling. Each patch is generated from the intersection
of vertices ($V_{p}$) from ico6 that overlap with each face of ico2, which
results in a sequence of 320 patches, each of $V_{p}=153$ vertices. This
generates a sequence of $|F_{2}|$ flattened patches of length $V_{p}$:
$\widetilde{X}=\left[\widetilde{X}_{1}^{(0)},\ldots,\widetilde{X}_{|F_{2}|}^{(0)}\right]\in
R^{|F_{2}|\times V_{p}}$, which is first projected onto a D-dimensional
sequence of tokens
$X^{(0)}=\left[X_{1}^{(0)},\ldots,X_{|F_{2}|}^{(0)}\right]\in R^{|F_{2}|\times
D}$, using a trainable linear layer (see Figure 2). Positional embedding is
then added to encode spatial information about the sequence of tokens. The
data is then passed through $N$ vision transformer blocks, each composed of a
multi-head self-attention layer and a feed-forward network (for more details
of implementation see [16]).

####  2.2.2 Decoding

In its original form, the SiT was designed for classification or regression
[16]. To support iterative prediction of noise and diagonal covariance, at the
same resolution as the original data, we extend the network with a layer norm
(adaptive if using adaLN) and a standard linear layer to decode each token
into $N\times(2V_{p})$. Finally, the decoded tokens are rearranged into their
original spatial layout to regenerate surface maps.

####  2.2.3 Conditioning

Following the DDPM formulation in the previous section, samples are
iteratively denoised through the SiT, with noise at each iteration
parametrized by iteration parameter $t$. At the same time, we seek to further
condition the model on the postmentrual age of our samples $a$. This is
achieved by appending $a$ and $t$ as additional tokens in the input sequence:
adding them into both surface input tokens before the SiT (see Figure 2).

Conditional generation of new samples is supported through use of classifier-
free guidance [17]. This approach requires both conditioned
$p_{\theta}(\mathbf{x}\mid c)$ and unconditioned $p_{\theta}(\mathbf{x})$
predictions to be generated from the same network (i.e. parametrized as
$\boldsymbol{\epsilon}_{\theta}\left(\mathbf{x}_{t},t,c\right)$ and
$\boldsymbol{\epsilon}_{\theta}\left(\mathbf{x}_{t},t\right)$) allowing the
gradient of an implicit classifier to be represented as follows:

$\nabla_{\mathbf{x}_{t}}\log
p\left(c\mid\mathbf{x}_{t}\right)=\nabla_{\mathbf{x}_{t}}\log
p\left(\mathbf{x}_{t}\mid c\right)-\nabla_{\mathbf{x}_{t}}\log
p\left(\mathbf{x}_{t}\right)$ (5)

In this setting, classifier-free guidance can be used to encourage the
sampling procedure to find $x$ such that $\log p(c\mid x)$ is high. This
method enables the surface diffusion model to generate target samples without
module modification and the results have shown its performance on surface
data.

##  3 Experiments and Results

###  3.1 Data

Data from the developing Human Connectome Project (dHCP) consists of cortical
surface meshes and metrics (sulcal depth, curvature, cortical thickness, and
T1w/T2w myelination) derived from T1- and T2-weighted magnetic resonance
images (MRI) using the dHCP structural pipeline [18]. We use 530 scans from
term (born after $37$ weeks gestation) and preterm neonates (born before $37$
weeks), covering postmenstrual age (PMA) at scan between 24 to 45 weeks. In
this experiment, we only use the curvature map. Training, test, and validation
sets were allocated in the ratio of 423:54:53 examples.

Fig. 3: Unconditional generated curvature surface compared with real sample

###  3.2 Implementation Details

Training The SiT transformer backbone was implemented with the same size of
SiT-small from [16], 12 layers, 6 heads, 384 hidden sizes, and 768 Multi-Layer
Perception(MLP) sizes. We train both unconditional and conditional diffusion
models with AdamW [19, 20] using standard weight initialization techniques
from SiT, except for the final linear (decoding) layer, which is initialised
with zeros. Training was implemented with a constant learning rate of $1\times
10^{-4}$, no weight decay, and a batch size of 180 on NVIDIA 3090 with 24 GB
memory. Following common practice in the generative modeling literature, we
maintain an exponential moving average (EMA) of surface diffusion weights with
a training decay of 0.9999.

###  3.3 Evaluation of Conditional Generation

The model was validated through visual inspection and training of an
independent SiT regression model which evaluated whether the generated samples
convincingly represent curvature maps of a specific PMA. This regression model
was trained on the same data set used for generation, with PMA as the target
variable. The proposed surface DDPM was used to generate 20 synthetic examples
for each week, from 27 weeks to 44 weeks. The results in table 1 report mean
absolute error for PMA predictions obtained on ground truth testing data and
on synthetic data. Visual examples are shown in Fig 4. Together these results
suggest that the proposed model is generating highly realistic cortical
curvature maps that can be realistically conditioned on PMA.

| Ground Truth | Synthetic
---|---|---
MAE | $0.59\pm 0.51$ | $0.80\pm 0.50$
r2 | $0.96$ | $0.96$
Table 1: Prediction results on dHCP test and synthetic data for the PMA
regression task. Mean Absolute Error (MAE) with standard deviation are
reported, as well as $R^{2}$ score. Fig. 4: Samples of cortical surfaces
generated by surface diffusion model conditioned on birth age of 30, 34, 38
and 42 weeks, compared to the real samples in dHCP dataset(First line)

##  4 Conclusion

This paper presents a general cortical surface diffusion generative model
validated on conditioned generation of cortical curvature maps across
neurodevelopment. The generated samples demonstrate that surface diffusion can
capture expressive features on the surface sufficiently well to sensitively
model the rapid changes in cortical curvature that occur across late
gestation. One major contributing factor is the incorporation of a surface
vision transformer model, which has previously been shown to outperform
surface convolution for cortical phenotype regression. While the results
demonstrate considerable potential, the model in its current form is limited
to synthesis of entirely novel samples and cannot intervene, or translate the
class of individual examples. Future work will look at the towards frameworks
for image-to-image translation [12, 21, 22] and deep causal modelling [23].
This would create opportunities for the development of networks suited to
anomaly detection of focal cortical malformations (such as epileptogenic
lesions [24]), modelling of cortical atrophy in dementia [12], or
investigation of the subtle impacts of preterm birth on cortical development
[21, 22].

##  5 Acknowledgments

We would like to acknowledge funding from King’s-China Scholarship(K-CSC) PhD
Scholarship program. Data were provided by the developing Human Connectome
Project. We are grateful to the families who generously supported this trial.

## References

  * [1] Bruce Fischl, Martin I Sereno, Roger BH Tootell, and Anders M Dale,  “High-resolution intersubject averaging and a coordinate system for the cortical surface,”  Human brain mapping, vol. 8, no. 4, pp. 272–284, 1999.
  * [2] Emma C Robinson, Saad Jbabdi, Matthew F Glasser, Jesper Andersson, Gregory C Burgess, Michael P Harms, Stephen M Smith, David C Van Essen, and Mark Jenkinson,  “Msm: a new flexible framework for multimodal surface matching,”  Neuroimage, vol. 100, pp. 414–426, 2014.
  * [3] Matthew F Glasser, Stephen M Smith, Daniel S Marcus, Jesper LR Andersson, Edward J Auerbach, Timothy EJ Behrens, Timothy S Coalson, Michael P Harms, Mark Jenkinson, Steen Moeller, et al.,  “The human connectome project’s neuroimaging approach,”  Nature neuroscience, vol. 19, no. 9, pp. 1175–1187, 2016.
  * [4] Tomáš Paus, Matcheri Keshavan, and Jay N Giedd,  “Why do many psychiatric disorders emerge during adolescence?,”  Nature reviews neuroscience, vol. 9, no. 12, pp. 947–957, 2008.
  * [5] James M Roe, Didac Vidal-Piñeiro, Øystein Sørensen, Andreas M Brandmaier, Sandra Düzel, Hector A Gonzalez, Rogier A Kievit, Ethan Knights, Simone Kühn, Ulman Lindenberger, et al.,  “Asymmetric thinning of the cerebral cortex across the adult lifespan is accelerated in alzheimer’s disease,”  Nature communications, vol. 12, no. 1, pp. 721, 2021.
  * [6] Matthew F Glasser, Timothy S Coalson, Emma C Robinson, Carl D Hacker, John Harwell, Essa Yacoub, Kamil Ugurbil, Jesper Andersson, Christian F Beckmann, Mark Jenkinson, et al.,  “A multi-modal parcellation of human cerebral cortex,”  Nature, vol. 536, no. 7615, pp. 171–178, 2016.
  * [7] Ru Kong, Jingwei Li, Csaba Orban, Mert R Sabuncu, Hesheng Liu, Alexander Schaefer, Nanbo Sun, Xi-Nian Zuo, Avram J Holmes, Simon B Eickhoff, et al.,  “Spatial topography of individual-specific cortical networks predicts human cognition, personality, and emotion,”  Cerebral cortex, vol. 29, no. 6, pp. 2533–2551, 2019.
  * [8] Evan M Gordon, Timothy O Laumann, Adrian W Gilmore, Dillan J Newbold, Deanna J Greene, Jeffrey J Berg, Mario Ortega, Catherine Hoyt-Drazen, Caterina Gratton, Haoxin Sun, et al.,  “Precision functional mapping of individual human brains,”  Neuron, vol. 95, no. 4, pp. 791–807, 2017.
  * [9] Andre F Marquand, Iead Rezek, Jan Buitelaar, and Christian F Beckmann,  “Understanding heterogeneity in clinical cohorts using normative models: beyond case-control studies,”  Biological psychiatry, vol. 80, no. 7, pp. 552–561, 2016.
  * [10] Saige Rutherford, Seyed Mostafa Kia, Thomas Wolfers, Charlotte Fraza, Mariam Zabihi, Richard Dinga, Pierre Berthet, Amanda Worker, Serena Verdi, Henricus G Ruhe, et al.,  “The normative modeling framework for computational psychiatry,”  Nature protocols, vol. 17, no. 7, pp. 1711–1734, 2022.
  * [11] Richard AI Bethlehem, Jakob Seidlitz, Simon R White, Jacob W Vogel, Kevin M Anderson, Chris Adamson, Sophie Adler, George S Alexopoulos, Evdokia Anagnostou, Ariosky Areces-Gonzalez, et al.,  “Brain charts for the human lifespan,”  Nature, vol. 604, no. 7906, pp. 525–533, 2022.
  * [12] Cher Bass, Mariana Da Silva, Carole Sudre, Logan ZJ Williams, Helena S Sousa, Petru-Daniel Tudosiu, Fidel Alfaro-Almagro, Sean P Fitzgibbon, Matthew F Glasser, Stephen M Smith, et al.,  “Icam-reg: Interpretable classification and regression with feature attribution for mapping neurological phenotypes in individual scans,”  IEEE Transactions on Medical Imaging, vol. 42, no. 4, pp. 959–970, 2022.
  * [13] Jonathan Ho, Ajay Jain, and Pieter Abbeel,  “Denoising diffusion probabilistic models,”  Advances in neural information processing systems, vol. 33, pp. 6840–6851, 2020.
  * [14] Zhen Liu, Yao Feng, Michael J Black, Derek Nowrouzezahrai, Liam Paull, and Weiyang Liu,  “Meshdiffusion: Score-based generative 3d mesh modeling,”  arXiv preprint arXiv:2303.08133, 2023.
  * [15] Chin-Wei Huang, Milad Aghajohari, Joey Bose, Prakash Panangaden, and Aaron C Courville,  “Riemannian diffusion models,”  Advances in Neural Information Processing Systems, vol. 35, pp. 2750–2761, 2022.
  * [16] Simon Dahan, Abdulah Fawaz, Logan Z. J. Williams, Chunhui Yang, Timothy S. Coalson, Matthew F. Glasser, A. David Edwards, Daniel Rueckert, and Emma C. Robinson,  “Surface vision transformers: Attention-based modelling applied to cortical analysis,” 2022.
  * [17] Jonathan Ho and Tim Salimans,  “Classifier-free diffusion guidance,”  arXiv preprint arXiv:2207.12598, 2022.
  * [18] Antonios Makropoulos, Emma C. Robinson, Andreas Schuh, Robert Wright, Sean Fitzgibbon, Jelena Bozek, Serena J. Counsell, Johannes Steinweg, Katerina Vecchiato, Jonathan Passerat-Palmbach, Gabriel Lenz, Filippo Mortari, Tihomir Tenev, Eugene P. Duff, Matteo Bastiani, Lucilio Cordero-Grande, Emer Hughes, Nora Tusor, J. Donald Tournier, Jana Hutter, Anthony N. Price, Rui Pedro A. G. Teixeira, Maria Murgasova, Sarah Victor, Christopher Kelly, Mary A. Rutherford, Stephen M. Smith, A. David Edwards, Joseph V. Hajnal, Mark Jenkinson, and Daniel Rueckert,  “The developing human connectome project: A minimal processing pipeline for neonatal cortical surface reconstruction,”  Neuroimage, vol. 173, pp. 88–112, 2018.
  * [19] Ilya Loshchilov and Frank Hutter,  “Decoupled weight decay regularization,”  arXiv preprint arXiv:1711.05101, 2017.
  * [20] Diederik P Kingma and Jimmy Ba,  “Adam: A method for stochastic optimization,”  arXiv preprint arXiv:1412.6980, 2014.
  * [21] Abdulah Fawaz, Logan ZJ Williams, A David Edwards, and Emma C Robinson,  “A deep generative model of neonatal cortical surface development,”  in Annual Conference on Medical Image Understanding and Analysis. Springer, 2022, pp. 469–481.
  * [22] Abdulah Fawaz, Saga NB Masui, Logan Zane John Williams, Simon Dahan, David Edwards, and Emma Claire Robinson,  “Surface generative modelling of neurodevelopmental trajectories,”  bioRxiv, pp. 2023–10, 2023.
  * [23] Pedro Sanchez and Sotirios A Tsaftaris,  “Diffusion causal models for counterfactual estimation,”  arXiv preprint arXiv:2202.10166, 2022.
  * [24] Hannah Spitzer, Mathilde Ripart, Abdulah Fawaz, Logan ZJ Williams, MELD project, Emma C Robinson, Juan Eugenio Iglesias, Sophie Adler, and Konrad Wagstyl,  “Robust and generalisable segmentation of subtle epilepsy-causing lesions: A graph convolutional approach,”  in International Conference on Medical Image Computing and Computer-Assisted Intervention. Springer, 2023, pp. 420–428.


# The Power of the Noisy Channel: Unsupervised End-to-End Task-Oriented
Dialogue with LLMs

Brendan King  Jeffrey Flanigan
University of California, Santa Cruz
<EMAIL_ADDRESS>
###### Abstract

Training task-oriented dialogue systems typically requires turn-level
annotations for interacting with their APIs: e.g. a dialogue state and the
system actions taken at each step. These annotations can be costly to produce,
error-prone, and require both domain and annotation expertise. With advances
in LLMs, we hypothesize unlabelled data and a schema definition are sufficient
for building a working task-oriented dialogue system, completely unsupervised.
Using only (1) a well-defined API schema (2) a set of unlabelled dialogues
between a user and agent, we develop a novel approach for inferring turn-level
annotations as latent variables using a noisy channel model. We iteratively
improve these pseudo-labels with expectation-maximization (EM), and use the
inferred labels to train an end-to-end dialogue agent. Evaluating our approach
on the MultiWOZ benchmark, our method more than doubles the dialogue success
rate of a strong GPT-3.5 baseline.111Our code will be available at
https://github.com/jlab-nlp/nc_latent_tod

The Power of the Noisy Channel: Unsupervised End-to-End Task-Oriented Dialogue
with LLMs

Brendan King and Jeffrey Flanigan University of California, Santa Cruz
<EMAIL_ADDRESS>

##  1 Introduction

Task-oriented dialogue systems, which use APIs to complete tasks on behalf of
users, have been a longstanding challenge within conversational AI. Recent
advances in large language models (LLMs) have further stimulated interest in
task-oriented systems and LLMs which can use APIs as tools. To facilitate API
use, successful task-oriented dialogue systems usually employ a modular
approach: predicting a dialogue state which includes arguments to API calls,
and dialogue acts for planning an appropriate response, before finally
producing a natural language reply. Training such systems typically requires
expert annotation of these structured intermediates for every dialogue turn.
Even in settings where human-human dialogues are abundantly available, the
high cost and expertise required to annotate the dialogues poses a significant
hurdle to system development.

Figure 1: An overview of our unsupervised dialogue problem. We assume 1)
unlabelled goal-oriented dialogues between a user and agent and 2) a well-
defined schema $\mathcal{S}$ with APIs suitable for fulfilling goals. We infer
the unseen interactions between the agent and API, and use this to produce an
end-to-end dialogue agent.

Recent work has shown that LLMs can accomplish a broad set of useful tasks
without any structured labels for a task Brown et al. (2020). These include
‘zero-shot’ approaches to task-oriented dialogue sub-tasks such as Dialogue
State Tracking (DST) Hu et al. (2022); King and Flanigan (2023); Heck et al.
(2023), intent detection Pan et al. (2023), grounded response generation Li et
al. (2023b), and even zero-shot end-to-end dialogue systems Hudeček and Dusek
(2023). Still, existing approaches generally do not perform well enough for
real-world use, and none are able to make effective use of in-domain
unlabelled dialogues.

We ask: can we use existing unlabelled dialogues (without any labels or API
calls annotated) along with an API specification, to build a working dialogue
agent, without needing an expert to annotate data? This addresses a common
real-world scenario. Many high value dialogue tasks are currently carried out
by human agents, who interface a user with some software system. These
conversations can be recorded and transcribed, and the API(s) supporting the
agent typically have well-formed specifications. However, annotating the API
calls and system acts needed for aligning the two is time consuming and
requires annotation expertise. In lieu of this, ‘zero-shot’ systems have been
proposed, but these still require an expert to annotate a ‘formatting example’
Hu et al. (2022); King and Flanigan (2023), or a more detailed ‘policy
skeleton’ Zhang et al. (2023).

We instead propose the following setting: we assume an API schema definition
$\mathcal{S}$, and plenty of available human-human dialogues in natural
language, but no annotations on these dialogues (Fig. 1). To the best of our
knowledge, we are the first to consider this setting. We demonstrate that one
can develop a conversational agent for the API schema in this setting without
any assistance from an expert annotator. Our contributions are as follows:

  * •

We construct an end-to-end task-oriented dialogue agent with an LLM solely
from unlabelled dialogues and an API definition, without any turn-level labels
or supervision from de-lexicalized utterances.

  * •

We accomplish this by inferring all the pseudo-labels necessary (API calls,
system actions) to train a traditional end-to-end dialogue system from
unlabelled dialogues, using prompts which are automatically generated from the
API schema.

  * •

We propose a noisy-channel ‘code-to-text’ re-ranking method, which is
instrumental to our pseudo-label quality and final system.

  * •

We devise a novel Hard-EM Dempster et al. (1977) approach which uses
predictions as in-context examples for the LLM, and additionally as data for
iteratively fine-tuning a final model.

##  2 Preliminaries

A task-oriented dialogue consists of turns of utterances between a user and an
agent which interfaces the user with a programmable system or API to
accomplish a task. Typically the system response utterance follows the user’s
utterance. We denote $u_{t}$ as the user’s utterance at turn $t$, and $r_{t}$
as the system’s response. We assume the APIs supported by the system are
defined in a schema $\mathcal{S}$, which gives names and descriptions for all
arguments supported in each API, as well as the possible values any
categorical arguments may take Rastogi et al. (2020). This is analogous to
standardized formats for API documentation, many of which could be easily
converted to a schema definition.

Task-oriented systems require some method for interacting with the APIs in
$\mathcal{S}$. Modular approaches use a Dialogue State Tracking (DST) module,
which predicts a belief state $b_{t}$: a collection of arguments to API
call(s) needed to satisfy the user’s goal. A belief state is commonly
represented with a set of slot-value pairs:

$b_{t}=\\{(s_{1},v_{1}),(s_{2},v_{2}),...(s_{n},v_{n})\\}$

For example, if a user says ‘I’m looking for a restaurant south of town’, a
DST system might produce the belief state {(restaurant-area, south)}, which
can be used to query a restaurant API. We assume zero labeled belief states
and infer them from unlabelled dialogues using the space of possible states
supported by the schema definition $\mathcal{S}$.

We also make use of system dialogue acts to structure our agent’s
communicative intents with a policy module. Given a dialogue state and context
for a turn $t$, the policy predicts set of dialogue acts to be communicated in
the system response $r_{t}$. For instance, the policy might determine that we
should ask the user to narrow their search to a price range:
$A_{t}=\\{\text{Request(restaurant-area=?)}\\}$. An appropriate system
response might be: “Sure, are you looking for a particular price range?" Like
belief states, we assume zero supervised examples of $A_{t}$ and infer them
from unlabelled dialogues.

##  3 Method Overview

Figure 2: An overview of the latent variables annotated in our unsupervised
labeling process which are used to train the dialogue model. Our DST Module (§
4.1) infers the API call(s) with arguments at each turn, from which we can
derive the dialogue state change. Our DAT or Act Tagging module (§ 4.2)
predicts the dialogue acts communicated in the observed system response, which
can be used to infer de-lexicalized responses for training a response
generator.

We treat the turn-level labels needed for training an end-to-end dialogue
system as a latent variables, and infer them from unlabelled dialogues. We
assume only the fully-lexicalized sequence of user and system utterances
$u_{1},r_{1},...u_{T},r_{T}$, and the schema $\mathcal{S}$ defining the
system’s capabilities, which defines the space of valid dialogue state and act
labels. Importantly, our prompts are automatically generated from the API
schema.

In § 4, we outline our noisy-channel prompting method for inferring the turn-
level labels necessary for training our dialogue agent. We give an overview of
the latent variables we infer in Fig. 2. We assume we cannot query the APIs or
observe results while labeling dialogues offline, as the obtained API results
may have changed. In § 5, we train a complete dialogue agent by fine-tuning on
prompts derived from our inferred pseudo-labels.

##  4 Inferring Latents via Noisy Channel

In this section, we present our method for inferring latent annotations for
the dialogue states $b_{1}...b_{T}$ and dialogue acts $A_{1}...A_{T}$ for each
dialogue turn $t$ given only the unlabelled user and system utterances
$(u_{1},r_{1},u_{2},r_{2},...u_{T},r_{T})$. To do this, we devise a noisy-
channel prompting approach for DST and dialogue act tagging (DAT) using
StarCoder Li et al. (2023a), a code-based LLM. First, we use a text-to-code
prompt to infer the API call(s) made by the system in each dialogue, and build
the dialogue state from inferred API call arguments (§ 4.1). We use a similar
text-to-code prompt to infer the latent act(s) communicated in each agent
response, so that we can reverse-engineer an agent’s policy (§ 4.2). For both
tasks, we find much better performance when re-ranking latent predictions
according to a noisy-channel model, in which we condition the observed
utterance on a predicted latent in a code-to-text prompt (§ 4.3). Finally, we
leverage the in-context learning ability of LLMs by re-using our predictions
as exemplars (§ 4.4). Given these initial pseudo-labels, we iteratively
improve their quality using Hard-EM Dempster et al. (1977) (§ 4.5).

###  4.1 Inferring API Calls and Dialogue State

We prompt the LLM with a text-to-code prompt for inferring the latent dialogue
state as an API call. 5(a) in App. A gives an example of our prompt. We
generate a prompt enumerating the intents available in the schema
$\mathcal{S}$ as APIs callable by our agent. Following Hu et al. (2022), we
predict the appropriate function call conditioned on the prior system response
$r_{t-1}$, the current user utterance $u_{t}$, and the previous belief state
prediction $\hat{b}_{t-1}$. We then extract a dialogue state change
$\Delta\hat{b}_{t}$ from the arguments to the call, and compute the next
dialogue state as $\hat{b}_{t}=\Delta\hat{b}_{t}+\hat{b}_{t-1}$. While used
offline here, this DST method is causal with respect to dialogue inputs and is
the same as our method in online inference.

###  4.2 Inferring System Acts

For inferring system acts, we use a similar text-to-code prompt for predicting
the set of dialogue acts $A_{t}$ communicated in a given system response
$r_{t}$. See 5(b) in App. A for an example of our prompt. We define each act
our system could take in the prompt instructions. For input from each turn, we
find best performance when conditioning only on the response to tag, $r_{t}$.
For our set of supported acts, we use a subset of the universal dialogue acts
proposed in Paul et al. (2019), where some acts such as “Inform” or “Offer”
may use slots defined in $\mathcal{S}$. For example, an agent choosing to
offer to book a user at a hotel named ‘acorn guest house’ might be represented
as Offer(hotel_name=‘acorn guest house’). See App. C for our complete dialogue
act set. Importantly, we use the schema definition $\mathcal{S}$ and our act
set to validate each act prediction, removing predicted keys which do not
belong to $\mathcal{S}$, or acts which are not in the set. For example, the
‘text’ key is not valid for a ‘ThankYou’ act, so a prediction of
“ThankYou(text=‘thanks, have a good day’)" would be normalized to only
“ThankYou()”. Using the inferred system acts, we use a rule-based method to
delexicalize the system responses for training the response generator (Fig. 2,
right).

###  4.3 Noisy Channel LLM Prompting

We find that a noisy channel prompting method Min et al. (2022) significantly
the quality of our inferred dialogue states and acts. Here we describe noisy
channel prompting using a simple example, and then describe its application to
dialogue state tracking and system act tagging.

A typical prompt for machine reading comprehension might be:

<Optional in-context examples (c)> Passage: <Passage (z)> Question: <Question
(x)> Answer:

Given this prompt of the in-context examples $c$, passage $z$, question $x$,
an answer $y$ completion is found with the language model by maximizing or
sampling from $Pr(y|x,z,c)$. We call this the direct prompt.

The “noisy channel” prompt is:

<Optional in-context examples (c)> Passage: <Passage (z)> Answer: <Answer (y)>
Question: <Question (x)>where the likelihood of the question now depends on
the answer. To use the noisy channel LLM prompt, we first sample $k$ samples
from the direct prompt, and then pick the best output answer $y$ according to
the noisy channel prompt probability. One can choose to score the joint
probability of the answer followed by the question, i.e.
$Pr(x|y,z,c)Pr(y|z,c)$, or only the conditional $Pr(x|y,z,c)$, following Min
et al. (2022).222In the latter case, the prior $Pr(y|z,c)$ is uniformly
$\frac{1}{k}$ for the $k$ samples from the direct prompt.

To apply this method to inferring dialogue states, we first sample a set of
possible belief state changes using top-$p$ sampling Holtzman et al. (2020)
from the direct DST prompt, and then pick the best dialogue state according to
the noisy channel prompt (see Fig. 3). We use an analogous procedure for
inferring system acts. For DST, we find scoring with the joint
$Pr(x|y,z,c)Pr(y|z,c)$ to perform best, and scoring with the conditional
$Pr(x|y,z,c)$ best for act tagging.

###  4.4 Retrieval-Augmented In-context Learning

To leverage the in-context learning abilities of LLMs, we retrieve from a pool
of examples from our predictions. Because we assume no labeled examples, this
pool starts with zero examples and is filled incrementally. We retrieve up to
$k$ examples for in-context learning from this pool using an unsupervised
dense retriever, with examples ranked by embedding cosine distance.333We use
MPNet Song et al. (2020), available on Huggingface as sentence-
transformers/all-mpnet-base-v2 We use $k=8$ and $k=6$ for DST, DAT
respectively. For retriever inputs, we use $(\hat{b}_{t-1}\cdot r_{t-1}\cdot
u_{t})$ and $(u_{t}\cdot r_{t})$ for DST and DAT respectively, where $\cdot$
indicates concatenation. Applied naively, this in-context learning approach
can suffer a majority label bias Zhao et al. (2021). We adjust for biases
introduced in the initially small example pool by 1) not using any in-context
examples until we have a minimum of $n=32$ examples in the pool and 2) using
our API schema $\mathcal{S}$ to require at least $4$ distinct labels in each
set of in-context examples.444We consider two dialogue state change labels to
be distinct if they update different slots, and two act labels to be distinct
if they embody different acts or different slots Our algorithm for producing
initial pseudo-labels is in App. D.

Figure 3: Instances from our ‘direct’ and ‘noisy channel’ prompts for DST.
Best viewed in color. After sampling a DST completion from the ‘direct’
prompt, we score it by the likelihood of the input user utterance conditioned
on it in the ‘noisy channel’ prompt.

###  4.5 Refining the Labels with Hard-EM

While the labels we produce in § 4.1-§ 4.4 can be used directly for training
an end-to-end dialogue system, we find their quality can be improved through
expectation-maximization Dempster et al. (1977). For every dialogue turn in
our dataset, our initial pseudo-labels provide the expected dialogue state and
system dialogue acts according to our zero-shot system. We then jointly fine-
tune an LLM as a noisy-channel DST & DAT system to maximize the likelihood of
these expected labels. We use smaller version of our prompted LLM, StarCoder
3B Li et al. (2023a).

For each turn, we derive (prompt, completion) pairs for ‘direct’ text-to-code
and ‘channel’ code-to-text DST and DAT modules, as defined in § 4. We then
combine and shuffle these pairs into a single training set for joint fine-
tuning. For efficient training, we shorten our prompts by removing in-context
examples as well as the function definitions used in the in-context learning
setting. We find up-sampling the ‘channel’ prompts so that there is a 2:1
ratio of ‘channel’ to ‘direct’ instances for training improves performance.

After fine-tuning, the model can be used to produce improved pseudo-labels by
re-labeling each dialogue, using the same noisy-channel inference methods.
Following this, we can repeat the fine-tuning process. This train and re-label
process can be repeated for any number of iterations, though we find a single
re-labeling is sufficient.

##  5 End-to-End System

Following Su et al. (2022), we utilize a multi-task fine-tuning method for
training a single LLM as a complete dialogue system, consisting of a dialogue
state tracker, policy, and response generator.

#### DST

For the DST sub-task, we again use both ‘direct’ and ‘channel’ (prompt,
completion) pairs. This allows us to use the same noisy-channel inference
method presented in § 4.

#### Policy

For the Policy sub-task, we use a text-to-code prompt where we simply
condition on the $k$=5 most recent utterances in the dialogue history:
$H_{t}=(u_{t-2},r_{t-2},u_{t-1},r_{t-1},u_{t})$. The completion is the current
turn’s system acts $A_{t}$, which will be used to ground the next response
$r_{t}$. We do not use a noisy-channel variant for Policy, and greedily decode
an act prediction at inference time:

$\hat{A}_{t}=\underset{A_{t}\in\mathcal{V}^{*}}{\mathrm{argmax}}\;P(f_{\text{prompt}}(H_{t})))$

#### Response Generation

For Response Generation, we condition on the turn’s observed system and user
utterances $(r_{t-1},u_{t})$ and our policy’s act prediction $\hat{A}_{t})$.
The completion is the observed system response $r_{t}$. We also do not use a
noisy-channel variant for response generation, and greedily decode the
response:

$\hat{r}_{t}=\underset{A_{t}\in\mathcal{V}^{*}}{\mathrm{argmax}}\;P(f_{\text{prompt}}(r_{t-1},u_{t},A_{t})))$

Following prior works, we predict delexicalized responses, where values for
slots in the system response are replaced with placeholders for the slot name.
For example, instead of generating “The phone number for acorn guest house is
555-5309" directly, we would predict “The phone number for the [hotel_name] is
[hotel_phone]”, where values could be filled in. Importantly, we never presume
access to gold delexicalized responses. Instead, we use our predicted acts,
e.g. “Inform(name=‘acorn guest house’, phone=‘555-8309’)”, to delexicalize the
observed response for training.

#### End-to-end Training

For each turn, we derive (prompt, completion) pairs for ‘direct’ and ‘channel’
DST, and direct Policy, and Response Generation prompts. We then combine and
shuffle these pairs into a single training set for joint fine-tuning. For
efficient training, we shorten our prompts by removing in-context examples as
well as the function definitions used in the in-context learning setting. We
find up-sampling the ‘channel’ prompts so that there is a 2:1 ratio of
‘channel’ to ‘direct’ instances for training improves performance. Finally, we
fine-tune StarCoder 3B using cross-entropy loss and AdamW with default
hyperparameters.

Model | Schema? | Labels? | Dialogues? | Inform | Success | BLEU | Combined
---|---|---|---|---|---|---|---
Supervised Results
PPTOD Su et al. (2022) | ✓ | ✓ | ✓ | 82.6 | 72.2 | 18.2 | 95.6
DiactTOD Wu et al. (2023) | ✓ | ✓ | ✓ | 89.5 | 84.2 | 17.5 | 104.4
Our (supervised) | ✓ | ✓ | ✓ | 67.9 | 61.7 | 14.6 | 79.4
Zero-Shot with Formatting Example(s)
SGP-TOD-GPT3.5 Zhang et al. (2023) | ✓ | Few (‡) | ✗ | 82.0 | 72.5 | 9.22 | 86.5
Fully Unsupervised Results
Sees gold delexicalized conversation history
LLaMa† | ✓ | ✗ | ✗ | - | 4 | 1.61 | -
GPT 3.5 Turbo† | ✓ | ✗ | ✗ | 44.8 | 31.2 | 3.3 | 41.3
Sees only fully-lexicalized dialogues
GPT 3.5 Turbo ($-$ gold delex.) | ✓ | ✗ | ✗ | 40.7 | 26.7 | 3.7 | 37.4
Ours (StarCoder 15B - no EM) | ✓ | ✗ | ✗ | 50.0 | 19.6 | 3.2 | 38
Ours (StarCoder 3B - w/ EM) | ✓ | ✗ | ✓ | 78.1 | 68.3 | 13.6 | 86.8

Table 1: Unsupervised end-to-end results in MultiWOZ 2.2. (†) indicates models
from Hudeček and Dusek (2023). Results for LLaMa are from Hudeček and Dusek
(2023), which does not report the Inform rate. (‡) SGP-TOD uses a prompt with
both a formatting example and a “Policy Skeleton”, which contains an
additional 10-20 hand-crafted instances of the correct system acts and
response for an input user utterance or returned DB result. For fairer
comparison in our fully unsupervised setting, we re-run the GPT 3.5 baseline
without the supervision of de-lexicalized responses provided in the
conversation history ($-$ gold delex.). Despite far fewer parameters, we find
substantial improvements in our methods which leverage unlabelled dialogues

##  6 Experiments

We conduct unsupervised end-to-end dialogue (E2E) and dialogue state tracking
(DST) experiments on the MultiWOZ 2.2 dataset Zang et al. (2020); Budzianowski
et al. (2018), containing over ten thousand multi-domain task-oriented
dialogues crowd-sourced in a wizard-of-oz setup. We use the fully lexicalized,
unlabelled dialogues from the training set to build our system, and evaluate
on the test set. First, we demonstrate the value of our approach in an end-to-
end dialogue evaluation, following prior works on task-oriented dialogue (§
6.1). Second, we conduct a dialogue state tracking evaluation to more
carefully evaluate the quality of our pseudo-annotations (§ 6.2).

###  6.1 End-to-End (E2E) Experiments

In E2E experiments, we use our complete system to both predict API call
arguments and generate a next system response in natural language. We evaluate
our generated responses with Inform rate, Success rate, and BLEU, as well as a
Combined score of $0.5(\text{Inform}+\text{Success})+BLEU$, following prior
works. We provide details on these metrics in App. B.

We compare our approach to the previous state-of-the-art unsupervised methods,
a GPT-3.5 zero-shot baseline Hudeček and Dusek (2023), and SGP-TOD Zhang et
al. (2023). Where possible, we report results for both the original approach
and modifications required to fit our fully unsupervised setting. For
reference, we also run our own method in the fully-supervised setting. We
train a model using the procedure in § 5 using the annotations sourced from
crowd-workers in the MultiWOZ 2.2 corpus Budzianowski et al. (2018); Zang et
al. (2020), rather than the pseudo-labels predicted in § 4. We also compare
with existing supervised approaches as a reference point. We include DiactTOD
Wu et al. (2023), which to our knowledge is the supervised state-of-the-art,
and PPTOD Su et al. (2022), which uses a multi-task fine-tuning approach
similar to our own in § 5, for T5 encoder-decoder models Raffel et al. (2020).

###  6.2 DST Experiments

We conduct multi-domain DST experiments on the MultiWOZ Dataset in order to
evaluate the quality of our pseudo-annotations. We use our DST Module to
predict and evaluate only latent dialogue states, which collect the arguments
required for unseen API calls.

Following prior works, we evaluate DST performance with joint-goal accuracy
(JGA), or whether a given dialogue state is completely accurate. More details
are available in App. B.

We compare to our ChatGPT 3.5 Turbo baseline Hudeček and Dusek (2023), as well
as prior zero-shot DST methods. These include IC-DST Hu et al. (2022), which
re-frames DST as text-to-SQL, and RefPyDST which re-frames DST as text-to-
python King and Flanigan (2023). By default, both of these works use OpenAI
Codex Chen et al. (2021), and we apply their prompting approaches to StarCoder
15B for clearer comparison.

With One Formatting Example
---
IC-DST (StarCoder 15B) | 24.58
RefPyDST (StarCoder 15B) | 17.17
IC-DST (Codex) | 35.02
RefPyDST (Codex) | 40.88
Fully Unsupervised
IC-DST (StarCoder 15B) | 15.66
RefPyDST (StarCoder 15B) | 13.88
GPT 3.5 Turbo Hudeček and Dusek (2023) | 13.05
Ours (StarCoder 15B $\rightarrow$ 3B) | 39.70

Table 2: Joint Goal Accuracy (JGA) of our method’s dialogue state predictions
and zero-shot baselines

##  7 Results

#### E2E Performance

We present E2E results for our unsupervised dialogue agent in § 5. We find
that our method achieves state-of-the-art performance in our fully
unsupervised setting, more than doubling the Success Rate and Combined score
of the GPT 3.5 Turbo baseline of Hudeček and Dusek (2023). When we remove the
supervision of delexicalization for fairer comparison ($-$ gold delex.), we
find even greater improvement across all end-to-end metrics. As discussed in §
9, SGP-TOD uses both a supervised formatting example and a ‘Policy Skeleton’,
containing additional supervision for Policy and Response Generation. With no
implementation publicly available, we were unable to run a modified version of
their experiments without this supervision for fair comparison. Despite a
less-supervised setting, our method is able to perform comparably, even
slightly out-performing SGP-TOD in Combined score. Remarkably, our
unsupervised EM approach also outperforms the supervised variant of our model
due to improvements in Inform and Success rate, suggesting the Dialogue acts
we infer are of high quality.

#### DST Performance

Our DST results are shown in Table 2. Where possible, we distinguish between
‘zero-shot’ results which include a hand-engineered formatting example, and
the same method applied without the formatting example.555Due to the
deprecation of OpenAI Codex, we were unable to run experiments for IC-DST or
RefPyDST without a formatting example on the original Codex model We find that
our method significantly outperforms our GPT 3.5 Turbo baseline by 26% joint
goal accuracy. Our approach performs nearly as well as the best method using
OpenAI Codex with a supervised formatting example, using less than 10% of the
parameters at any time (175B vs. 15B). When applying the IC-DST and RefPyDST
prompting methods to StarCoder, our method significantly outperforms both,
with and without a formatting example.

#### Ablations

In Fig. 4, we conduct an ablation to evaluate both the impact of our noisy
channel modeling and the value of iterative re-labeling in our EM approach. We
compare our proposed system to one in which each module is replaced by only
greedily sampling from its ‘direct’ variant, at both labeling and end-to-end
inference time. We plot our Combined end-to-end performance across iterations
of EM, with ‘0’ indicating our zero-shot system. We find that EM improves our
end-to-end performance in both our noisy-channel approach and greedy ablation,
and that our noisy-channel inference methods are important to dialogue
success, with a 30 and 33 point improvement over our greedy baseline with 1
and 2 EM steps, respectively. Ablations across Inform, Success, BLEU, and
joint goal accuracy are in App. E.

Figure 4: Combined score ($0.5(\text{Inform}+\text{Success})+BLEU$) vs. the
number of steps of expectation-maximization in our Noisy Channel method vs. a
Greedy Ablation. ‘0’ is zero-shot inference

##  8 Contamination Analysis

Evaluation of unsupervised methods, such as ours, that use LLMs has the
potential issue of task contamination, where supervised examples are seen in
pretraining data Li and Flanigan (2024). Inclusion of supervised examples of
the task in LLM pretraining data would render the model no longer unsupervised
and the evaluation potentially biased: tasks for which the training data has
been seen may have a higher performance than truly unsupervised tasks.

To address this issue, we quantify the presence of contamination in LLM pre-
training data, and then estimate the potential impact on our results.
Fortunately, the StarCoder family of models that we use has the complete pre-
training corpus publicly available for
analysis.666https://huggingface.co/datasets/bigcode/starcoderdata

Task | Turns | Correct | Authentic
---|---|---|---
Act Tagging | 42 | 21 | 5
DST | 42 | 36 | 19
Table 3: Number of discovered contaminated turns per task, as well as the
number which are correct or verified as being in the MultiWOZ dataset.

We conduct an exhaustive search for supervised pairs of our dialogue subtasks
in the StarCoder pretraining data using a semi-automated search with manual
review. Details of our search procedure are in App. F. We find no complete
dialogues with supervised labels. We do find 42 turns labeled with act
tagging, and 42 turns labeled with DST in the pre-training corpus, categorized
in Table 3.777The average dialogue length in MultiWOZ is 13.9 turns. Put
together, the set of contaminated turns would be roughly the length of 6
dialogues We consider a $(x,y)$ pair to be ‘Correct’ if the state
change/dialogue act $y$ is actually correct for the utterance $x$, and to be
‘Authentic’ if the $(x,y)$ pair is found verbatim in the MultiWOZ corpus.888A
‘Correct’ pair might arise from printing training data, and an incorrect pair
from discussion of a failure case. Astonishingly, we find half of the found
Act Tagging pairs are incorrect, and could possibly mislead a pre-trained
model if the model learned from them. We also find that less than half of the
turns are authentic for either task, and find a number of them derive from
Github issues discussing problems with dialogue simulators.

Additionally, we estimate the degree to which the contamination we discover
could exaggerate expected performance of our method on an unseen schema, by
using contaminated $(x,y)$ pairs as in-context examples.999Ideally, one would
pre-train an identical StarCoder model on a corpus without contamination, this
is computationally impractical. Additionally, we are not aware of any
available LLM that can be verified as not contaminated for this task.

In Table 4, we compare our zero-shot prompt, which receives no examples of any
kind, with a ‘contaminated’ variant which uses $k$=3 in-context examples
derived from contamination in the pre-training corpus. The ‘contaminated’
model retrieves the most relevant contaminated fragments from a pool using the
dense retrieval approach described in § 4.4. These are inserted as a triple-
quoted string block, so that the prompt remains syntactically valid python. By
leaving contaminated examples in their original format, we test whether their
inclusion elicits memorized knowledge rather than providing guidance on
input/output formatting. Surprisingly, we find including this supervision via
contaminated fragments hurts performance, indicating that these examples do
not provide meaningful supervision for our task. Further, the substantial
gains in our noisy-channel EM approach suggest our method is doing more than
simply eliciting schema-specific knowledge memorized in pre-training.

Method | Inform | Success | BLEU | Combined
---|---|---|---|---
Ours (zero-shot) | 49.0 | 15.0 | 3.0 | 35.0
Ours (k=3 contam ex.) | 44.5 | 14.0 | 3.8 | 33.1
Ours (Full EM) | 80.5 | 69.0 | 13.7 | 88.5

Table 4: Performance comparison when we include contaminated in-context
examples. We find including this supervision hurts performance, and does not
explain the strong performance of our noisy-channel EM approach

##  9 Related Work

#### Zero-shot Dialogue

A few recent works have proposed zero-shot approaches to dialogue problems
using LLMs. Hu et al. (2022) and King and Flanigan (2023) propose DST methods
which prompt code based LLMs in a text-to-SQL or text-to-program format,
respectively. These methods rely on prompts tailored to the schema and the use
of a supervised ‘formatting’ example, which requires annotation expertise.
Zhang et al. (2023) extends this approach to end-to-end task-oriented dialogue
by adding a policy prompter for GPT 3.5. In addition to a formatting example,
their policy prompt requires a hand-crafted ‘policy-skeleton’ consisting of
examples of the appropriate system act and reply in response to different user
utterances or database results. Our approach differs in that we require zero
labeled examples of any kind. Hudeček and Dusek (2023) propose a zero-shot
end-to-end method for prompting instruction-tuned LLMs like GPT 3.5. However,
this method presumes delexicalized system responses $r_{1}...r_{t-1}$ in the
conversation history as input, where entities are replaced with placeholders.
Producing these inputs requires ground-truth annotations and gives a form of
supervision about the entities and their attributes within a dialogue (see § 5
for a comparison for GPT 3.5 Turbo with and without delex supervision). In
contrast, we only assume fully-lexicalized dialogues, which do not provide
this supervision and require no human annotation. We adapt the method of
Hudeček and Dusek (2023) to use lexicalized dialogues as inputs, and use this
approach as our baseline. Chung et al. (2023) propose an end-to-end method
which prompts GPT-4 for interactions with a knowledge base before producing a
response, however it generalizes poorly to the multi-domain setting.

#### Semi-supervised TOD

Some works propose semi-supervised approaches to end-to-end task-oriented
dialogue. Zhang et al. (2020) propose an end-to-end sequence-to-sequence model
where the dialogue state is a latent variable. Liu et al. (2021a) adapt this
approach for use with pre-trained language models, fine-tuning GPT-2. While
successful, these approaches require a non-trivial amount of supervised data.
Other semi-supervised works also evaluate their method in an unsupervised
setting Jin et al. (2018); Liu et al. (2023). However, these works also assume
delexicalized training dialogues, which requires ground-truth annotation and
gives a form a supervision to the model.

#### Noisy channel and re-ranking methods

A few previous works have utilized noisy channel methods for task-oriented
dialogue or prompting methods. Liu et al. (2021b) pre-train a noisy channel
for task-oriented dialogues as a sequence to sequence model, however their
method requires significant labelled training data. Min et al. (2022) propose
noisy channel prompting for few-shot classification tasks, which inspires our
generalization to the generative setting.

##  10 Conclusion

We present a novel approach for constructing an end-to-end task-oriented
dialogue system by leveraging pre-trained language models to infer labels from
unlabeled dialogues.

##  11 Limitations

Data contamination in LLM pre-training poses a hurdle for accurate
benchmarking across NLP, and particularly for unsupervised methods. In an
idealized setting, there would be a suitably strong task-oriented dialogue
benchmark that could be verified as not belonging to the pre-training corpus
of each new and more capable LLM. This is not the case for our setting or for
many others, and warrants careful attention from the NLP community. For our
setting, we were able to properly define problematic contamination and search
for it in our LLM’s pre-training corpus, thanks to the open release of the
pre-training data. We found limited contamination and demonstrated that the
contamination we found was not helpful in eliciting task knowledge that might
have been memorized in pre-training.

All experiments in this paper were conducted on pre-existing public dialogue
corpora, collected explicitly for training task-oriented dialogue agents with
the knowledge of all participants Budzianowski et al. (2018). Our use of the
StarCoder model also falls within the terms of it’s Responsible AI License. It
is important that subsequent applications of our method also adhere to any
fair-use policies governing collected dialogues or transcripts.

## References

  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners.  _arXiv:2005.14165 [cs]_.  ArXiv: 2005.14165.
  * Budzianowski et al. (2018) Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Ultes Stefan, Ramadan Osman, and Milica Gašić. 2018.  Multiwoz - a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021.  Evaluating Large Language Models Trained on Code.  ArXiv:2107.03374 [cs].
  * Chung et al. (2023) Willy Chung, Samuel Cahyawijaya, Bryan Wilie, Holy Lovenia, and Pascale Fung. 2023.  InstructTODS: Large Language Models for End-to-End Task-Oriented Dialogue Systems.  ArXiv:2310.08885 [cs].
  * Dempster et al. (1977) A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977.  Maximum likelihood from incomplete data via the em algorithm.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , 39(1):1–38.
  * Heck et al. (2023) Michael Heck, Nurul Lubis, Benjamin Ruppik, Renato Vukovic, Shutong Feng, Christian Geishauser, Hsien-chin Lin, Carel van Niekerk, and Milica Gasic. 2023.  ChatGPT for zero-shot dialogue state tracking: A solution or an opportunity? In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 936–950, Toronto, Canada. Association for Computational Linguistics.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The Curious Case of Neural Text Degeneration.  ArXiv:1904.09751 [cs].
  * Hu et al. (2022) Yushi Hu, Chia-Hsuan Lee, Tianbao Xie, Tao Yu, Noah A. Smith, and Mari Ostendorf. 2022.  In-Context Learning for Few-Shot Dialogue State Tracking.  Number: arXiv:2203.08568 arXiv:2203.08568 [cs].
  * Hudeček and Dusek (2023) Vojtěch Hudeček and Ondrej Dusek. 2023.  Are large language models all you need for task-oriented dialogue? In _Proceedings of the 24th Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 216–228, Prague, Czechia. Association for Computational Linguistics.
  * Jin et al. (2018) Xisen Jin, Wenqiang Lei, Zhaochun Ren, Hongshen Chen, Shangsong Liang, Yihong Zhao, and Dawei Yin. 2018.  Explicit State Tracking with Semi-Supervision for Neural Dialogue Generation.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , pages 1403–1412.  ArXiv:1808.10596 [cs].
  * King and Flanigan (2023) Brendan King and Jeffrey Flanigan. 2023.  Diverse retrieval-augmented in-context learning for dialogue state tracking.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 5570–5585, Toronto, Canada. Association for Computational Linguistics.
  * Li and Flanigan (2024) Changmao Li and Jeffrey Flanigan. 2024.  Task Contamination: Language Models May Not Be Few-Shot Anymore.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 38(16):18471–18480.
  * Li et al. (2023a) Raymond Li, Loubna Ben allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia LI, Jenny Chim, Qian Liu, Evgenii Zheltonozhskii, Terry Yue Zhuo, Thomas Wang, Olivier Dehaene, Joel Lamy-Poirier, Joao Monteiro, Nicolas Gontier, Ming-Ho Yee, Logesh Kumar Umapathi, Jian Zhu, Ben Lipkin, Muhtasham Oblokulov, Zhiruo Wang, Rudra Murthy, Jason T Stillerman, Siva Sankalp Patel, Dmitry Abulkhanov, Marco Zocca, Manan Dey, Zhihan Zhang, Urvashi Bhattacharyya, Wenhao Yu, Sasha Luccioni, Paulo Villegas, Fedor Zhdanov, Tony Lee, Nadav Timor, Jennifer Ding, Claire S Schlesinger, Hailey Schoelkopf, Jan Ebert, Tri Dao, Mayank Mishra, Alex Gu, Carolyn Jane Anderson, Brendan Dolan-Gavitt, Danish Contractor, Siva Reddy, Daniel Fried, Dzmitry Bahdanau, Yacine Jernite, Carlos Muñoz Ferrandis, Sean Hughes, Thomas Wolf, Arjun Guha, Leandro Von Werra, and Harm de Vries. 2023a.  Starcoder: may the source be with you! _Transactions on Machine Learning Research_.  Reproducibility Certification.
  * Li et al. (2023b) Zekun Li, Baolin Peng, Pengcheng He, Michel Galley, Jianfeng Gao, and Xifeng Yan. 2023b.  Guiding large language models via directional stimulus prompting.  _arXiv preprint arXiv:2302.11520_.
  * Liu et al. (2021a) Hong Liu, Yucheng Cai, Zhenru Lin, Zhijian Ou, Yi Huang, and Junlan Feng. 2021a.  Variational Latent-State GPT for Semi-Supervised Task-Oriented Dialog Systems.  ArXiv:2109.04314 [cs].
  * Liu et al. (2021b) Qi Liu, Lei Yu, Laura Rimell, and Phil Blunsom. 2021b.  Pretraining the Noisy Channel Model for Task-Oriented Dialogue.  _Transactions of the Association for Computational Linguistics_ , 9:657–674.
  * Liu et al. (2023) Qing-Bin Liu, Shi-Zhu He, Cao Liu, Kang Liu, and Jun Zhao. 2023.  Unsupervised Dialogue State Tracking for End-to-End Task-Oriented Dialogue with a Multi-Span Prediction Network.  _Journal of Computer Science and Technology_ , 38(4):834–852.
  * Min et al. (2022) Sewon Min, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022.  Noisy channel language model prompting for few-shot text classification.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5316–5330, Dublin, Ireland. Association for Computational Linguistics.
  * Nekvinda and Dušek (2021) Tomáš Nekvinda and Ondřej Dušek. 2021.  Shades of BLEU, flavours of success: The case of MultiWOZ.  In _Proceedings of the 1st Workshop on Natural Language Generation, Evaluation, and Metrics (GEM 2021)_ , pages 34–46, Online. Association for Computational Linguistics.
  * Pan et al. (2023) Wenbo Pan, Qiguang Chen, Xiao Xu, Wanxiang Che, and Libo Qin. 2023.  A Preliminary Evaluation of ChatGPT for Zero-shot Dialogue Understanding.  Publisher: arXiv Version Number: 1.
  * Paul et al. (2019) Shachi Paul, Rahul Goel, and Dilek Hakkani-Tür. 2019.  Towards Universal Dialogue Act Tagging for Task-Oriented Dialogues.  In _Proc. Interspeech 2019_ , pages 1453–1457.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020.  Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer.  _arXiv:1910.10683 [cs, stat]_.  ArXiv: 1910.10683.
  * Rastogi et al. (2020) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2020.  Towards Scalable Multi-Domain Conversational Agents: The Schema-Guided Dialogue Dataset.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(05):8689–8696.
  * Song et al. (2020) Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie-Yan Liu. 2020.  MPNet: Masked and Permuted Pre-training for Language Understanding.  ArXiv:2004.09297 [cs].
  * Su et al. (2022) Yixuan Su, Lei Shu, Elman Mansimov, Arshit Gupta, Deng Cai, Yi-An Lai, and Yi Zhang. 2022.  Multi-task pre-training for plug-and-play task-oriented dialogue system.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 4661–4676, Dublin, Ireland. Association for Computational Linguistics.
  * Wu et al. (2023) Qingyang Wu, James Gung, Raphael Shu, and Yi Zhang. 2023.  DiactTOD: Learning generalizable latent dialogue acts for controllable task-oriented dialogue systems.  In _Proceedings of the 24th Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 255–267, Prague, Czechia. Association for Computational Linguistics.
  * Zang et al. (2020) Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen. 2020.  MultiWOZ 2.2 : A Dialogue Dataset with Additional Annotation Corrections and State Tracking Baselines.  In _Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI_ , pages 109–117, Online. Association for Computational Linguistics.
  * Zhang et al. (2023) Xiaoying Zhang, Baolin Peng, Kun Li, Jingyan Zhou, and Helen Meng. 2023.  SGP-TOD: Building task bots effortlessly via schema-guided LLM prompting.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 13348–13369, Singapore. Association for Computational Linguistics.
  * Zhang et al. (2020) Yichi Zhang, Zhijian Ou, Min Hu, and Junlan Feng. 2020.  A Probabilistic End-To-End Task-Oriented Dialog Model with Latent Belief States towards Semi-Supervised Learning.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9207–9219, Online. Association for Computational Linguistics.
  * Zhao et al. (2021) Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. 2021.  Calibrate before use: Improving few-shot performance of language models.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 12697–12706. PMLR.

##  Appendix A Prompt Examples

Fig. 5 provides abridged instances of our direct prompts for DST and for Act
Tagging. 5(a) shows our prompt for inferring API call(s) or changes to the
dialogue state from an unlabelled dialogue, as detailed in § 4.1. Our prompts
use python keyword arguments to provide the input variables for a given sub-
task, and to prompt the LLM for the next variable of interest. Using the
arbitrary ordering of keyword arguments in Python function calls, our
‘channel’ prompts simply re-order the arguments in order to score the
likelihood of the user’s utterance given the predicted state change. 5(b)
provides a similar abridged instance of our direct prompt for tagging dialogue
acts in an unlabelled dialogue. Here, we simply condition on the observed
system response $r_{t}$.

(a) Our ‘direct’ DST prompt with italicized completion

(b) Our ‘direct’ act tagging prompt, with italicized completion

Figure 5: Abridged prompt and completion examples from our in-context learning
approach to initial labelling for DST and DAT (Act Tagging), best viewed in
color. Key-word arguments are used to include variables from the turn context
and to prefix the completion

##  Appendix B Metric Details

#### End-to-End (E2E) Dialogue Metrics

We measure end-to-end dialogue performance using the Inform rate, Success
rate, and BLEU, following prior works, using the automatic evaluation provided
by Nekvinda and Dušek
(2021).101010https://github.com/Tomiinek/MultiWOZ_Evaluation

A dialogue is considered Informed if the most recently mentioned result for
each domain meets the user’s goal constraints, and is considered Successful if
it is Informed and all values for requested slots are presented to the user.
For example, if a user were to ask ‘Can you give me the phone number of a
cheap hotel in the east part of town?’, the dialogue would be Informed if we
refer them to a hotel that is actually in the cheap price range and in the
east, and Successful if we additionally provide the phone number, as
requested. BLEU is computed against a single reference response, and the
Combined score is $0.5(\text{Inform}+\text{Success})+BLEU$.

#### Dialogue State Tracking Metrics

Following prior works, we evaluate DST performance with joint-goal accuracy
(JGA): for a turn $x_{t}$, a dialogue state prediction $\hat{y}_{t}$ is
considered correct only if all slot names and values match the gold annotation
state $y_{t}$. We again use the evaluation provided in Nekvinda and Dušek
(2021). Following their work, we accept fuzzy matches for non-categorical
string values, such as the name of a restaurant or hotel, using the fuzzywuzzy
library and a fuzz ratio of 0.95.111111https://pypi.org/project/fuzzywuzzy/

##  Appendix C Dialogue Acts

Following Paul et al. (2019), we use a universal set of dialogue acts for
managing our agents communicative intents. We omit some acts for simplicity
and to reduce the context length required to enumerate them in a prompt. Table
5 lists each act and a description. Since our dialogue set is not directly
comparable to prior works, we do not directly evaluate act tagging or policy
accuracy. Instead, acts serve only as an intermediate representation for
planning responses in our end-to-end system.

Act |  Description (as used in our prompt)
---|---
Inform(x=y) |  Provide information.
Offer(x=y) |  System provides an offer or suggestion based on results.
Confirm(x=y) |  Seek confirmation of something.
Affirm(x=y) |  Express agreement or confirmation.
Negate(x=y) |  User or System denies or negates.
NotifySuccess(x=y) |  Notify of a successful action or result.
NotifyFailure(x=y) |  Notify of an error or failure.
Acknowledge |  Acknowledge.
Goodbye |  Goodbye.
Greeting |  Greeting.
ThankYou |  ThankYou.
RequestAlternatives |  Ask for other options, alternatives, or any additional user goals.
Request(x=?) |  Ask for specific information or action.
Table 5: Dialogue acts supported by our system, adapted from the universal
dialogue acts proposed in Paul et al. (2019). “x=y" indicates the act can take
on arbitrary key-value arguments, and “x=?" indicates the act takes on one or
more unpaired arguments. We reduce the number of acts and lengths of
descriptions relative to Paul et al. (2019) in order to fit within the LMs
context length

##  Appendix D Offline Labeling Algorithm

Algorithm 1 gives our algorithm for pseudo-labeling of unlabelled dialogues.

1:procedure InitialOfflineLabel($\mathcal{D}_{train},\theta_{ret}$, $\theta$)

2: $\mathcal{P}\leftarrow\emptyset$ $\triangleright$ Initialize example pool

3: $\mathcal{B}\leftarrow[]$ $\triangleright$ Store predictions by dialogue id
and turn index

4: for $t=0$ to $\underset{d\in\mathcal{D}_{train}}{\mathrm{max}}\;|d|$ do
$\triangleright$ Loop by increasing turn index

5: for all $(d_{id},u_{t},r_{t-1},r_{t})$ in $\mathcal{D}_{train}$ do
$\triangleright$ $d_{id}$ is dialogue ID

6: $\hat{b}_{t-1}\leftarrow\mathcal{B}[d_{id}][t-1]\textbf{ or }\emptyset$
$\triangleright$ Fetch $\hat{b}_{t-1}$ if known

7:
$\hat{b}_{t}\leftarrow\textsc{OfflineDST}(\mathcal{P},\theta_{ret},\hat{b}_{t-1},r_{t-1},u_{t})$

8:
$\hat{A}_{t}\leftarrow\textsc{OfflineActTag}(\mathcal{P},\theta_{ret},u_{t},r_{t})$

9:
$\mathcal{P}\leftarrow\mathcal{P}\cup\\{(r_{t-1},u_{t},r_{t},\hat{b}_{t},\hat{A}_{t})\\}$
$\triangleright$ Add in-context example for future labeling

10: end for

11: end for

12:end procedure

13:procedure
OfflineDST($\mathcal{P},\theta_{ret},\hat{b}_{t-1},r_{t-1},u_{t}$)

14: $\mathcal{E}_{k}\leftarrow\theta_{ret}(\hat{b}_{t}\cdot r_{t-1}\cdot
u_{t},\mathcal{P})$ $\triangleright$ Retrieve up to $k$ in-context examples

15: $\mathcal{C}\leftarrow\Delta
b_{t}\underset{\scalebox{0.6}{\text{top-}p}}{\sim}P(f_{\text{prompt}}(\mathcal{E}_{k},\hat{b}_{t-1},r_{t-1},u_{t}))$
$\triangleright$ Sample w/ ‘direct’ prompt

16: $\Delta\hat{b}_{t}\leftarrow\underset{\Delta
b_{t}\in\mathcal{C}}{\mathrm{argmax}}\;P(u_{t}|f_{\text{prompt}}(\mathcal{E}_{k},\hat{b}_{t-1},r_{t-1},\Delta
b_{t})$ $\triangleright$ Re-rank w/ ‘channel’ prompt

17: return $\hat{b}_{t-1}+\Delta\hat{b}_{t}$

18:end procedure

19:procedure OfflineActTag($\mathcal{P},\theta_{ret},u_{t},r_{t}$)

20: $\mathcal{E}_{k}\leftarrow\theta_{ret}(u_{t}\cdot r_{t},\mathcal{P})$
$\triangleright$ Retrieve up to $k$ in-context examples

21: $\mathcal{C}\leftarrow
A_{t}\underset{\scalebox{0.6}{\text{top-}p}}{\sim}(P(f_{\text{prompt}}(\mathcal{E}_{k},r_{t})))$
$\triangleright$ Sample w/ ‘direct’ prompt

22: return
$\underset{A_{t}\in\mathcal{C}}{\mathrm{argmax}}\;P(\mathcal{E}_{k},A_{t},r_{t})$
$\triangleright$ Re-rank w/ ‘channel’ prompt

23:end procedure

Algorithm 1 Our algorithm for initial pseudo-labeling of unlabelled dialogues
in $\mathcal{D}_{train}$

##  Appendix E Further results across EM Steps

Here we expand on our ablations in § 7, which evaluates our method with and
without our proposed noisy-channel prompting across iterations of expectation-
maximization (EM). In Fig. 6, we break down the performance gains we observed
in our ‘Combined’ metric into Inform rate, Success rate, and BLEU, where
$\text{Combined}=0.5(Inform+Success)+BLEU$. ‘0’ iterations of EM indicates our
zero-shot prompting system, without any in-context examples or EM. We find
that EM substantially improves performance in all cases, and particularly for
our noisy-channel prompting approach. We find the noisy channel prompting
approach improves performance on all metrics, with the most substantial gains
over the greedy baseline in Inform and Success rates. This suggests that
within our algorithm, noisy-channel inference may be particularly important
when inferring the system’s dialogue acts in order to reverse-engineer an
accurate policy.

In Fig. 7, we analyze dialogue state tracking performance across iterations of
EM using Joint Goal Accuracy (JGA). We find our noisy-channel prompting
approach improves the accuracy of our dialogue state tracking predictions
across iterations of EM when compared to a greedy, direct prompting approach.

Figure 6: Breaking down
$\text{Combined}=0.5(\text{Inform}+\text{Success})+BLEU$ into components
Inform Rate, Success Rate, and BLEU across iterations of EM between our
proposed noisy-channel approach and a greedy ablation, which omits noisy-
channel prompting at inference time and when labeling dialogue states & system
acts in the expectation step. We find improvement across all components, and
particularly our Inform and Success Rates Figure 7: Joint Goal Accuracy (JGA)
of our inferred API call(s)/Dialogue states across iterations of EM. We find
improved dialogue state tracking performance when using our noisy-channel
method at inference time and when labeling dialogue states offline in the
expectation step for training, compared to a greedy direct prompting approach

##  Appendix F Contamination Search & Result Details

###  F.1 Procedure

We detail our method for finding instances of task contamination within the
StarCoder pre-training set. We are particularly interested in supervised pairs
$(x,y)$ where $y$ belongs to our schema of interest $\mathcal{S}$, for any of
the dialogue sub-tasks used in our system. We devise a method for searching
the complete pre-training corpus for contaminated $(x,y)$ pairs, where $x$ is
an utterance we might observe from either the system or user, and $y$ is the
latent dialogue state change or dialogue act supporting $\mathcal{S}$. For
each utterance $x$ from either the system or user, we collect all documents
from the pre-training corpus which contain the complete utterance. We use the
elastic search index provided for the StarCoder pre-training data, which
accounts for differences in capitalization, punctuation, and interrupting
white-space.121212https://github.com/bigcode-project/search/blob/main/index.py
Following this, we search matching documents for keywords from $y$ (e.g. slot
names and values) to determine which of these documents may plausibly contain
a supervised label and warrant manual review. For dialogue states, these are
the slot names and values, discarding extremely generic keywords like ‘name’.
For act tags, these are the act names, slots, and values. We then consider a
document to need manual review if 40% or more of the keywords are found in the
500 characters before or after a matching $x$ in a document. Finally, we hand-
check the remaining documents and extract contaminated $(x,y)$ pairs.

###  F.2 Examples

Table 6 contains examples of contamination discovered in our search process,
and the type of document in which they were found. Notably, none of the
examples found closely match our output formatting.

Contaminated Input |  Contaminated Output | Sub-Task | Source
---|---|---|---
I need a restaurant to dine at in Cambridge on my upcoming trip . I need info about chiquito restaurant bar restaurant . |  restaurant-inform<<<name===chiquito restaurant bar | DST | Jupyter Notebook
i would like to book a 5 star , or closest to it , in the east part of town please . |  "<SOB> hotel area = east, stars = 5, type = hotel <EOB> <SOB> hotel area = east, stars = 5 restaurant area = east <EOB>" | DST | Python
[Syst] the train id is tr8292 and the price is 16.50 pounds. |  [SYS_DA] train-inform-leave-tr8292 [SYS_DA] train-inform-ticket-16.50 pounds | Act Tagging | Github Issue
Table 6: Example inputs and outputs in contaminated documents from each task,
discovered in the StarCoder pre-training corpus. We include the source type of
each document


The above implications, though simple, are remarkable! They convert the
problem of checking an induced norm inequality (a ratio of norms) to one of
checking the positivity of a quadratic form over the input and output signals
of a system. This problem fits in the general framework of (1) because the
form is a quadratic form jointly on the input $w$ and the state $x$ (for
notational simplicity, we set the direct-feedthrough term $D=0$ in the sequel)

$\displaystyle{\mbox{\large$\mathbf{q}$}}_{\mathrm{b}}~{}$
$\displaystyle:=~{}\gamma^{2}\|w\|_{2}^{2}-\|z\|^{2}_{2}~{}=~{}\gamma^{2}\int_{0}^{T}w^{*}(t)w(t)~{}dt~{}-~{}\int_{0}^{T}z^{*}(t)z(t)~{}dt$
$\displaystyle=~{}\int_{0}^{T}\left(\gamma^{2}w^{*}w~{}-~{}x^{*}C^{*}Cx\rule{0.0pt}{10.00002pt}\right)~{}dt~{}=~{}\int_{0}^{T}\\!\\!\\!\begin{bmatrix}x^{*}&w^{*}\end{bmatrix}\begin{bmatrix}\text{-}C^{*}C&0\\\
0&\gamma^{2}I\end{bmatrix}\begin{bmatrix}x\\\ w\end{bmatrix}dt$
$\displaystyle=~{}\left<\begin{bmatrix}x\\\
w\end{bmatrix}\bm{,}\begin{bmatrix}\text{-}C^{*}C&0\\\
0&\gamma^{2}I\end{bmatrix}\begin{bmatrix}x\\\
w\end{bmatrix}\right>_{L^{2}[0,{\scriptstyle
T}]}~{}=:~{}\left<\begin{bmatrix}x\\\
w\end{bmatrix}\bm{,}{\bm{Q}}_{\mathrm{b}}\begin{bmatrix}x\\\
w\end{bmatrix}\right>_{L^{2}[0,{\scriptstyle T}]},$ (93)

where ${\bm{Q}}_{\mathrm{b}}$ is the (possibly time-varying) matrix function
defined above. The subscript $\rm b$ references the bounded real lemma which
is another name for the criterion of the same problem we are addressing.

Another important systems theory criterion is that of passivity.

######  Definition 13.

An ${\sf L}^{2}$-stable linear system $G$ is called passive over
$(0,{\scriptstyle T})$ if all input output pairs $z=Gw$ with $w\in{\sf
L}^{2}(0,{\scriptstyle T})$ (and zero initial conditions) satisfy

$\left<z\bm{,}w\rule{0.0pt}{8.50006pt}\right>_{{\sf
L}^{2}(0,{\scriptscriptstyle
T})}~{}=~{}\scaleobj{.8}{\int_{{0}}^{{T}}}z^{*}(t)~{}w(t)~{}dt~{}\geq~{}0.$
(94)

A system passive over $(0,\infty)$ is simply called passive.

We can again convert this to a question about the positivity of a quadratic
form in input and state when the system $G$ is given by the realization (92)

$\displaystyle{\mbox{\large$\mathbf{q}$}}_{\rm p}~{}$
$\displaystyle:=~{}\scaleobj{.8}{\int_{{0}}^{{T}}}z^{*}w~{}dt~{}=~{}\scaleobj{.8}{\int_{{0}}^{{T}}}(Cx+Dw)^{*}~{}w~{}dt~{}=~{}\scaleobj{.8}{\int_{{0}}^{{T}}}\left(x^{*}C^{*}w+w^{*}D^{*}w\rule{0.0pt}{10.00002pt}\right)~{}dt$
$\displaystyle=~{}\frac{1}{2}\int_{0}^{T}\begin{bmatrix}x^{*}&w^{*}\end{bmatrix}\begin{bmatrix}0&C^{*}\\\
C&{D+D^{*}}\end{bmatrix}\begin{bmatrix}x\\\
w\end{bmatrix}dt~{}=:~{}\frac{1}{2}\left<\begin{bmatrix}x\\\
w\end{bmatrix}\bm{,}{\bm{Q}}_{\rm p}\begin{bmatrix}x\\\
w\end{bmatrix}\right>_{{\sf L}^{2}(0,T)}.$ (95)

Thus checking passivity of a system is equivalent to checking whether the
quadratic form (95) is positive on all signals that satisfy the system’s
equations.

###  A.3 Redundancy in Covariance Matrices

Let $z$ be a zero mean, continuous-time random process. Its instantaneous
covariance matrix is defined as

$\Sigma(t)~{}:=~{}{\mathbb{E}}\left[z(t)~{}z^{*}\\!(t)\rule{0.0pt}{9.10004pt}\right],$

which is a deterministic, matrix-valued function of $t$. Recall that
covariance matrices are always positive $\Sigma(t)\geq 0$, and therefore have
symmetric factorizations $\Sigma(t)=U(t)~{}U^{*}(t)$ for some other matrix
$U(t)$. The dimensions of any such factorization has implications for
dependencies between the components of the vector $z(t)$. This last statement
will of course be only true up to second order statistics of the process $z$.
For Gaussian processes, the statement is true without qualification.

In the following, the dependence on $t$ is suppressed for notational
simplicity. Given a factorization
${\mathbb{E}}\left[z~{}z^{*}\rule{0.0pt}{9.10004pt}\right]=UU^{*}$, consider
another random vector $\zeta:=Uw$, where $w$ is a zero-mean random vector with
uncorrelated components (i.e. ${\mathbb{E}}\left[ww^{*}\right]=I$). With this
construction, $\zeta$ and $z$ have the same second order statistics as can be
easily verified

${\mathbb{E}}\left[\zeta~{}\zeta^{*}\rule{0.0pt}{9.10004pt}\right]~{}=~{}{\mathbb{E}}\left[Uw~{}(Uw)^{*}\rule{0.0pt}{9.10004pt}\right]~{}=~{}{\mathbb{E}}\left[Uww^{*}U^{*}\rule{0.0pt}{9.10004pt}\right]~{}=~{}U~{}{\mathbb{E}}\left[ww^{*}\rule{0.0pt}{9.10004pt}\right]U^{*}~{}=~{}U~{}U^{*}~{}=~{}\Sigma.$

Of course if $z$ and $w$ are Gaussian, then this means that $z$ and $\zeta$
have the same distribution.

We are interested in full-rank factorizations, i.e.

$\Sigma~{}=~{}{\begin{bmatrix}\rule{0.0pt}{10.00002pt}\\\ U\\\
\rule{0.0pt}{10.00002pt}\end{bmatrix}}{\begin{bmatrix}~{}&U^{*}&~{}\end{bmatrix}},\hskip
20.00003pt\hskip
20.00003pt\Sigma\in{\mathbb{S}}_{n},~{}U\in{\mathbb{R}}^{n\times r},~{}r\leq
n.$

where $r={\rm\bf rk}\\!\left(\Sigma\right)$, and therefore $U$ has full column
rank. If $r<n$, then the original covariance matrix $\Sigma$ is not full rank.
This indicates that there are redundancies in the description of the processes
$z$ and $\zeta$. To see this, partition $\zeta$ and $U$ as follows

$\zeta~{}=~{}\begin{bmatrix}\zeta_{1}\\\ \zeta_{2}\end{bmatrix},\hskip
20.00003ptU~{}=~{}\begin{bmatrix}U_{1}\\\ U_{2}\end{bmatrix},$

so that $U_{1}$ is square (i.e. in ${\mathbb{R}}^{r\times r}$). Assume without
loss of generality that $U_{1}$ is invertible131313Since $U$ is full rank,
this can always be done by permuting the rows of $U$ so that the first $r$ are
linearly independent. This corresponds to permuting the components of the
vectors $z$ and $\zeta$.. With this partition, the relation $\zeta=Uw$ now has
the following implications

$\begin{bmatrix}\zeta_{1}\\\ \zeta_{2}\end{bmatrix}=\begin{bmatrix}U_{1}\\\
U_{2}\end{bmatrix}w=\begin{bmatrix}U_{1}w\\\ U_{2}w\end{bmatrix}\hskip
20.00003pt\Leftrightarrow\hskip
20.00003ptw=U_{1}^{-1}\zeta_{1}~{}~{}\mbox{and}~{}~{}\zeta_{2}=U_{2}w=U_{2}U_{1}^{-1}\zeta_{1}.$
(96)

Thus $\zeta_{2}$ is a function of $\zeta_{1}$, or equivalently, the entire
$\zeta$ vector is completely determined by its subcomponents $\zeta_{1}$,
which is an $r$-vector. In an intuitive sense, the number of “degrees of
freedom” in the random $n$-vector $\zeta$ is actually $r\leq n$, the rank of
its covariance matrix.

Finally, if $z$ and $w$ are Gaussian, then the components of $z$ have the same
joint distribution as the components of $\zeta$ as mentioned earlier. Since
the components of $\zeta$ obey the relation (96), then the components of $z$
obey the same relation. The statements made above hold for each $t$, although
the rank of the covariance matrix may depend on $t$.

###  A.4 Riccati Comparisons

Most of the arguments in this subsection are largely a reorganization of the
classic arguments in [5] for the case of finite time horizon. The expression
(97) below is from [5, Lemma 3]. The expression (98) is a slight modification
which is needed when the matrix $M$ below has no specific definiteness.

  1. 1.

Given the linear-quadratic portion of the Riccati opeator (i.e. without the
constant term)

$\mathcal{R}_{\sf lq}(\Lambda)~{}:=~{}A^{*}\Lambda+\Lambda A-\Lambda
M\Lambda,$

The difference $\mathcal{R}_{\sf lq}(\Lambda_{1})-\mathcal{R}_{\sf
lq}(\Lambda_{2})$ can be expressed in several ways as follows

$\displaystyle\mathcal{R}_{\sf lq}(\Lambda_{1})-\mathcal{R}_{\sf
lq}(\Lambda_{2})~{}$
$\displaystyle=~{}A^{*}(\Lambda_{1}-\Lambda_{2})+(\Lambda_{1}-\Lambda_{2})A-\Lambda_{1}M\Lambda_{1}+\Lambda_{2}M\Lambda_{2}$
$\displaystyle=~{}A^{*}(\Lambda_{1}-\Lambda_{2})+(\Lambda_{1}-\Lambda_{2})A-\Lambda_{1}M\Lambda_{1}+\Lambda_{2}M\Lambda_{2}$
$\displaystyle\hskip
20.00003pt+\Lambda_{1}M\Lambda_{1}-\Lambda_{1}M\Lambda_{1}+\Lambda_{1}M\Lambda_{2}-\Lambda_{1}M\Lambda_{2}+\Lambda_{2}M\Lambda_{1}-\Lambda_{2}M\Lambda_{1}$
$\displaystyle=~{}\left(A-M\Lambda_{1}\right)^{*}(\Lambda_{1}-\Lambda_{2})+(\Lambda_{1}-\Lambda_{2})\left(A-M\Lambda_{1}\right)+(\Lambda_{1}-\Lambda_{2})M(\Lambda_{1}-\Lambda_{2})$
(97)
$\displaystyle=~{}\big{(}A+M(\Lambda_{1}+\Lambda_{2})/2\big{)}^{*}~{}(\Lambda_{1}-\Lambda_{2})~{}+~{}(\Lambda_{1}-\Lambda_{2})~{}\big{(}A+M(\Lambda_{1}+\Lambda_{2})/2)\big{)}$
(98)

  2. 2.

Consider solutions of two Riccati differential equations with different
“$Q$-terms”

$\displaystyle 0{}$
$\displaystyle=~{}{\dot{\Lambda}}_{1}+A^{*}\Lambda_{1}+\Lambda_{1}A-\Lambda_{1}M\Lambda_{1}+Q_{1},\hskip
20.00003pt\Lambda_{1}({\scriptstyle T})=0,$ (99) $\displaystyle 0{}$
$\displaystyle=~{}{\dot{\Lambda}}_{2}+A^{*}\Lambda_{2}+\Lambda_{2}A-\Lambda_{2}M\Lambda_{2}+Q_{2},\hskip
20.00003pt\Lambda_{2}({\scriptstyle T})=0,$

with $Q_{1}\geq Q_{2}$. Define the difference
${\tilde{\Lambda}}:=\Lambda_{1}-\Lambda_{2}$, subtract the two equations and
apply the Riccati difference formula (98) to obtain

$\displaystyle\dot{{\tilde{\Lambda}}}+\left(A+M\big{(}\Lambda_{1}+\Lambda_{2}\big{)}/2\right)^{*}{\tilde{\Lambda}}+{\tilde{\Lambda}}\left(A+M\big{(}\Lambda_{1}+\Lambda_{2}\big{)}/2\right)+\left(Q_{1}-Q_{2}\right)~{}$
$\displaystyle=~{}0$ $\displaystyle\Rightarrow\hskip
20.00003pt\dot{{\tilde{\Lambda}}}+\left(A+M\big{(}\Lambda_{1}+\Lambda_{2}\big{)}/2\right)^{*}{\tilde{\Lambda}}+{\tilde{\Lambda}}\left(A+M\big{(}\Lambda_{1}+\Lambda_{2}\big{)}/2\right)~{}$
$\displaystyle=~{}-\left(Q_{1}-Q_{2}\right)~{}\leq~{}0.$

This is a differential Lyapunov inequality of the form (41) for
${\tilde{\Lambda}}$. Applying (45) we conclude that ${\tilde{\Lambda}}(t)\geq
0$, and for the differential Riccati equations with final conditions (99)

$Q_{1}(t)\geq Q_{2}(t),\hskip 10.00002ptt\in[0,{\scriptstyle T}]\hskip
20.00003pt\Rightarrow\hskip 20.00003pt\Lambda_{1}(t)\geq\Lambda_{2}(t),\hskip
10.00002ptt\in[0,{\scriptstyle T}]$ (100)

  3. 3.

Now consider the DRI (46) and the DRE obtained from it by setting the
inequality to equality

$\left.\begin{aligned} \dot{\Lambda}+A^{*}\Lambda+\Lambda
A-\Lambda~{}M~{}\Lambda+Q~{}\geq~{}0,\hskip 20.00003pt\Lambda({\scriptstyle
T})=0,\\\
\dot{{\bar{\Lambda}}}+A^{*}{\bar{\Lambda}}+{\bar{\Lambda}}A-{\bar{\Lambda}}~{}M~{}{\bar{\Lambda}}+Q~{}=~{}0,\hskip
20.00003pt{\bar{\Lambda}}({\scriptstyle T})=0.\end{aligned}\right\\}\hskip
20.00003pt\Rightarrow\hskip 20.00003pt{\bar{\Lambda}}(t)\geq\Lambda(t),$ (101)

where the conclusion ${\bar{\Lambda}}(t)\geq\Lambda(t)$ follows from previous
arguments. Indeed, the DRI is equivalent to the DRE (47) with the forcing
function $H\geq 0$. A comparison of their “$Q$-terms” shows that
$Q-(Q-H)=H\geq 0$, and therefore by the comparison result (100)
${\bar{\Lambda}}(t)\geq\Lambda(t)$ for all $t\in[0,{\scriptstyle T}]$, i.e.
${\bar{\Lambda}}$ is the maximal solution to the DRI.

###  A.5 DLMIs with initial or final conditions

######  Theorem 14 (Extremal Solutions).

Consider the linear matrix ${\cal M}$ and the associated Riccati $\mathcal{R}$
operators

$\displaystyle{\cal M}(\Lambda)~{}$
$\displaystyle:=~{}{\bm{Q}}+{\mathcal{E}}^{{\bm{*}}}({\dot{\Lambda}})+\mathcal{A}^{{\bm{*}}}(\Lambda)~{}=\begin{bmatrix}Q+\dot{\Lambda}+A^{*}\Lambda+\Lambda
A&N+\Lambda B\\\ (N+\Lambda B)^{*}&R\end{bmatrix},$ (102)
$\displaystyle\mathcal{R}(\Lambda)~{}$
$\displaystyle:=~{}{\dot{\Lambda}}+A^{*}\Lambda+\Lambda A-\left(N+\Lambda
B\right)R^{\text{-}1}\left(N+\Lambda B\right)^{*}+Q,$ (103)

where $R>0$ or $R<0$. Consider also initial- and final-value Differential
Linear Matrix Inequalities (DLMIs) and their equivalent Differential Riccati
Inequalities (DRIs) over $[t_{\rm i},t_{\rm f}]$

$\displaystyle\left.\begin{array}[]{rclcrcl}{\cal M}(\Lambda)&\geq&0&\hskip
20.00003pt\Leftrightarrow&\hskip 20.00003pt\mathcal{R}(\Lambda)&\geq&0\\\
\mbox{or}~{}{\cal M}(\Lambda)&\leq&0&\hskip 20.00003pt\Leftrightarrow&\hskip
20.00003pt\mathcal{R}(\Lambda)&\leq&0\end{array}\right\\}$
$\displaystyle\Lambda(t_{\rm i})$ $\displaystyle=\Lambda_{\rm i},\hskip
20.00003pt{\rm(DLMI_{i}/DRI_{i})}$ (104)
$\displaystyle\left.\begin{array}[]{rclcrcl}{\cal M}(\Lambda)&\geq&0&\hskip
20.00003pt\Leftrightarrow&\hskip 20.00003pt\mathcal{R}(\Lambda)&\geq&0\\\
\mbox{or}~{}{\cal M}(\Lambda)&\leq&0&\hskip 20.00003pt\Leftrightarrow&\hskip
20.00003pt\mathcal{R}(\Lambda)&\leq&0\end{array}\right\\}$
$\displaystyle\Lambda(t_{\rm f})$ $\displaystyle=\Lambda_{\rm f}.\hskip
20.00003pt{\rm(DLMI_{f}/DRI_{f})}$

Minimal and maximal solutions of the initial- and final-value inequalities
respectively are given by the following Differential Riccati Equations (DREs)

$\displaystyle\mathcal{R}({\underline{\Lambda}})~{}$ $\displaystyle=~{}0,$
$\displaystyle{\underline{\Lambda}}(t_{\rm i})=\Lambda_{\rm i},\hskip
20.00003pt{\rm(DRE_{i}):}~{}\mbox{\rm minimal-initial}$ (105)
$\displaystyle\mathcal{R}({\bar{\Lambda}})~{}$ $\displaystyle=~{}0,$
$\displaystyle{\bar{\Lambda}}(t_{\rm f})=\Lambda_{\rm f},\hskip
20.00003pt{\rm(DRE_{f}):}~{}\mbox{\rm maximal-final}$ (106)

i.e. for any $\Lambda$ satisfying $\rm DLMI_{i}/DRI_{i}$ (resp. $\rm
DLMI_{f}/DRI_{f}$)

${\underline{\Lambda}}(t)~{}\leq~{}\Lambda(t)\hskip
20.00003pt\left(\rule{0.0pt}{10.00002pt}\mbox{resp.}~{}\Lambda(t)~{}\leq~{}{\bar{\Lambda}}(t)\right),\hskip
20.00003pt\hskip 20.00003ptt\in[t_{\rm i},t_{\rm f}].$

Furthermore, at the extremal solutions, the matrix ${\cal M}$ has the full-
rank symmetric factorization

${\cal
M}({\bar{\Lambda}})~{}=~{}\begin{bmatrix}(N+{\bar{\Lambda}}B)R^{\text{-}\frac{1}{2}}\\\
R^{\frac{1}{2}}\end{bmatrix}\begin{bmatrix}R^{\text{-}\frac{1}{2}}(N+{\bar{\Lambda}}B)^{*}&R^{\frac{1}{2}}\end{bmatrix},$
(107)

and similarly for ${\cal M}({\underline{\Lambda}})$.

###### Proof.

We consider the case ${\cal M}(\Lambda)\geq 0$ with $\Lambda(t_{\rm
f})=\Lambda_{\rm f}$. The other three cases are argued similarly. The Riccati
operator (103) can be written in the more standard form

$\displaystyle\mathcal{R}(\Lambda)~{}$
$\displaystyle:=~{}{\dot{\Lambda}}+A^{*}\Lambda+\Lambda A-\left(N+\Lambda
B\right)R^{\text{-}1}\left(N+\Lambda B\right)^{*}+Q$
$\displaystyle=~{}{\dot{\Lambda}}+\big{(}A-BR^{\text{-}1}N^{*}\big{)}^{*}~{}\Lambda+\Lambda~{}\big{(}A-BR^{\text{-}1}N^{*}\big{)}-\Lambda~{}BR^{\text{-}1}B^{*}~{}\Lambda+\big{(}Q-NR^{\text{-}1}N^{*}\big{)}$
$\displaystyle=:~{}{\dot{\Lambda}}+\hat{A}^{*}\Lambda+\Lambda\hat{A}-\Lambda
M\Lambda+\hat{Q}.$ (108)

The Riccati comparison result (101) now implies that the solution
${\bar{\Lambda}}$ of $\mathcal{R}({\bar{\Lambda}})=0$ is maximal over all
solutions of the $\rm DRE_{f}$, i.e. over all solutions of the $\rm DLMI_{f}$

For the factorization (55), note that the $\rm DRE_{f}$ for ${\bar{\Lambda}}$
implies

$Q+\dot{{\bar{\Lambda}}}+A^{*}{\bar{\Lambda}}+{\bar{\Lambda}}A~{}=~{}(N+{\bar{\Lambda}}B)R^{\text{-}1}(N+{\bar{\Lambda}}B)^{*}.$

Using this, the matrix ${\cal M}({\bar{\Lambda}})$ can be decomposed as

$\displaystyle\begin{bmatrix}Q+\dot{{\bar{\Lambda}}}+A^{*}{\bar{\Lambda}}+{\bar{\Lambda}}A&(N+{\bar{\Lambda}}B)\\\
(N+{\bar{\Lambda}}B)^{*}&R\end{bmatrix}$
$\displaystyle=\begin{bmatrix}(N+{\bar{\Lambda}}B)R^{\text{-}1}(N+{\bar{\Lambda}}B)^{*}&N+{\bar{\Lambda}}B\\\
(N+{\bar{\Lambda}}B)^{*}&R\end{bmatrix}$
$\displaystyle=\begin{bmatrix}(N+{\bar{\Lambda}}B)R^{\text{-}\frac{1}{2}}\\\
R^{\frac{1}{2}}\end{bmatrix}\begin{bmatrix}R^{\text{-}\frac{1}{2}}(N+{\bar{\Lambda}}B)^{*}&R^{\frac{1}{2}}\end{bmatrix},$

which is a full-rank factorization since $R$ (and therefore $R^{\frac{1}{2}}$)
is assumed non-singular. ∎

## References

  * [1] R. E. Kalman, “Contributions to the theory of optimal control,” _Bol. soc. mat. mexicana_ , vol. 5, no. 2, pp. 102–119, 1960.
  * [2] V. Popov, “Hyperstability and optimality of automatic systems with several control functions,” _Rev. Roum. Sci. Tech., Ser. Electrotech. Energ_ , vol. 9, no. 4, pp. 629–690, 1964.
  * [3] R. E. Kalman, “Lyapunov functions for the problem of lur’e in automatic control,” _Proceedings of the national academy of sciences_ , vol. 49, no. 2, pp. 201–205, 1963.
  * [4] V. A. Yakubovich, “The solution of some matrix inequalities encountered in automatic control theory,” in _Doklady Akademii Nauk_ , vol. 143, no. 6. Russian Academy of Sciences, 1962, pp. 1304–1307.
  * [5] J. Willems, “Least squares stationary optimal control and the algebraic riccati equation,” _IEEE Transactions on automatic control_ , vol. 16, no. 6, pp. 621–634, 1971.
  * [6] A. Megretski and A. Rantzer, “System analysis via integral quadratic constraints,” _IEEE transactions on automatic control_ , vol. 42, no. 6, pp. 819–830, 1997.
  * [7] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, _Linear matrix inequalities in system and control theory_. SIAM, 1994.
  * [8] S. P. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [9] C. Scherer and S. Weiland, “Linear matrix inequalities in control,” _Lecture Notes, Dutch Institute for Systems and Control, Delft, The Netherlands_ , vol. 3, no. 2, 2000.
  * [10] A. Gattami, “Generalized linear quadratic control,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 1, pp. 131–136, 2009.
  * [11] ——, “Optimal decisions with limited information,” Ph.D. dissertation, Lund University, 2007.
  * [12] S. You and A. Gattami, “H infinity analysis revisited,” _arXiv preprint arXiv:1412.6160_ , 2014.
  * [13] S. You, A. Gattami, and J. C. Doyle, “Primal robustness and semidefinite cones,” in _2015 54th IEEE Conference on Decision and Control (CDC)_. IEEE, 2015, pp. 6227–6232.
  * [14] A. Gattami and B. Bamieh, “Simple covariance approach to $H^{\infty}$ analysis,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 3, pp. 789–794, 2015.
  * [15] A. Rantzer, “Linear quadratic dual control (cdc 2023 plenary presentation),” _arXiv preprint arXiv:2312.06014_ , 2023.
  * [16] M. A. Dahleh and J. Pearson, “$\ell^{1}$-optimal-feedback controllers for discrete-time systems,” in _1986 American Control Conference_. IEEE, 1986, pp. 1964–1968.
  * [17] M. Dahleh and J. Pearson, “$L^{1}$-optimal compensators for continuous-time systems,” _IEEE Transactions on Automatic Control_ , vol. 32, no. 10, pp. 889–895, 1987.
  * [18] X. Qi, M. H. Khammash, and M. V. Salapaka, “A matlab package for multiobjective control synthesis,” in _Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No. 01CH37228)_ , vol. 4. IEEE, 2001, pp. 3991–3996.
  * [19] M. V. Salapaka and M. Khammash, “Multi-objective mimo optimal control design without zero interpolation,” in _Robustness in identification and control_. Springer, 1999, pp. 306–317.
  * [20] L. Vandenberghe and S. Boyd, “Semidefinite programming,” _SIAM review_ , vol. 38, no. 1, pp. 49–95, 1996.
  * [21] R. Vinter, “Convex duality and nonlinear optimal control,” _SIAM journal on control and optimization_ , vol. 31, no. 2, pp. 518–538, 1993.
  * [22] A. Rantzer, “A dual to lyapunov’s stability theorem,” _Systems & Control Letters_, vol. 42, no. 3, pp. 161–168, 2001.
  * [23] A. Mauroy, A. Sootla, and I. Mezić, “Koopman framework for global stability analysis,” _The Koopman Operator in Systems and Control: Concepts, Methodologies, and Applications_ , pp. 35–58, 2020.
  * [24] D. Angeli and E. D. Sontag, “Monotone control systems,” _IEEE Transactions on automatic control_ , vol. 48, no. 10, pp. 1684–1698, 2003.
  * [25] A. Rantzer and M. E. Valcher, “A tutorial on positive systems and large scale control,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 3686–3697.
  * [26] A. Rantzer, “Explicit solution to bellman equation for positive systems with linear cost,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_. IEEE, 2022, pp. 6154–6155.
  * [27] B. Bamieh and M. Filo, “An input–output approach to structured stochastic uncertainty,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 12, pp. 5012–5027, 2020.
  * [28] P. Seiler, “Stability analysis with dissipation inequalities and integral quadratic constraints,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 6, pp. 1704–1709, 2014.
  * [29] A. Shapiro, “On duality theory of conic linear problems,” in _Semi-infinite programming_. Springer, 2001, pp. 135–165.