<commit_before>% Use the following line _only_ if you're still using LaTeX 2.09.
%\documentstyle[icml2014,epsf,natbib]{article}
% If you rely on Latex2e packages, like most modern people use this:
\documentclass{article}

% use Times
\usepackage{times}
% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure} 

% For citations
\usepackage{natbib}

% For algorithms
\usepackage{algorithm}
\usepackage{algorithmic}

% As of 2011, we use the hyperref package to produce hyperlinks in the
% resulting PDF.  If this breaks your system, please commend out the
% following usepackage line and replace \usepackage{icml2014} with
% \usepackage[nohyperref]{icml2014} above.
\usepackage{hyperref}

% Packages hyperref and algorithmic misbehave sometimes.  We can fix
% this with the following command.
\newcommand{\theHalgorithm}{\arabic{algorithm}}

% Employ the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
\usepackage{format/icml2014} 
% Employ this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Proceedings of the...''
%\usepackage[accepted]{icml2014}

\usepackage{times}
\usepackage{hyperref}
\usepackage{url}
\usepackage{color}
\usepackage{preamble}
\definecolor{mydarkblue}{rgb}{0,0.08,0.45}
\hypersetup{ %
    pdftitle={},
    pdfauthor={},
    pdfsubject={},
    pdfkeywords={},
    pdfborder=0 0 0,
    pdfpagemode=UseNone,
    colorlinks=true,
    linkcolor=mydarkblue,
    citecolor=mydarkblue,
    filecolor=mydarkblue,
    urlcolor=mydarkblue,
    pdfview=FitH}
    
    
\usepackage{amsmath, amsfonts, bm, lipsum, capt-of}
\usepackage{natbib, xcolor, wrapfig, booktabs, multirow, caption}
\DeclareCaptionType{copyrightbox}
\usepackage{float}

%\renewcommand{\baselinestretch}{0.99}

\def\ie{i.e.\ }
\def\eg{e.g.\ }
\let\oldemptyset\emptyset
\let\emptyset\varnothing

%\author{
%<NAME>\\
%University of Cambridge\\
%Department of Engineering\\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%University of Cambridge \\
%Department of Engineering \\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%M.I.T.\\
%Brain and Cognitive Sciences \\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%M.I.T.\\
%Brain and Cognitive Sciences \\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%University of Cambridge \\
%Department of Engineering \\
%\texttt{<EMAIL>}
%}

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\setlength{\marginparwidth}{0.6in}
\input{include/commenting.tex}

%% For submission, make all render blank.
%\renewcommand{\LATER}[1]{}
%\renewcommand{\fLATER}[1]{}
%\renewcommand{\TBD}[1]{}
%\renewcommand{\fTBD}[1]{}
%\renewcommand{\PROBLEM}[1]{}
%\renewcommand{\fPROBLEM}[1]{}
%\renewcommand{\NA}[1]{#1}  % Note, NA's pass through!


% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
\icmltitlerunning{Automatic construction and natural-language summarization of additive nonparametric models}

\begin{document} 

\twocolumn[
\icmltitle{Automatic construction and natural-language summarization\\of additive nonparametric models}

% It is OKAY to include author information, even for blind
% submissions: the style file will automatically remove it for you
% unless you've provided the [accepted] option to the icml2014
% package.
\icmlauthor{Your Name}{<EMAIL>}
\icmladdress{Your Fantastic Institute,
            314159 Pi St., Palo Alto, CA 94306 USA}
\icmlauthor{Your CoAuthor's Name}{<EMAIL>}
\icmladdress{Their Fantastic Institute,
            27182 Exp St., Toronto, ON M6H 2T1 CANADA}

% You may provide any keywords that you 
% find helpful for describing your paper; these are used to populate 
% the "keywords" metadata in the PDF but will not be shown in the document
\icmlkeywords{}

\vskip 0.3in
]

\begin{abstract} 
One of the broad aims of statistics is to produce an accurate and concise description of data.
Parametric techniques typically produces a concise description of data but can be inaccurate when there are deviations from the strong assumptions implied by parametric forms.
In contrast, nonparametric methods are typically capable of providing accurate descriptions of many data sets but at the expense of succinct descriptions.
To address this apparent antagonism we demonstrate that a recently introduced nonparametric model construction technique allows for the automatic natural-language description of a data set into natural-language while also constructing an accurate model.
We also extend the class of models that can be produced by this model construction method to include a wide variety of regression motifs.
\end{abstract} 

\allowdisplaybreaks

\section{Introduction}

Simple parametric regression models such as linear regression are usually easily interpretable, requiring only a table of regression coefficients and a few other parameters to describe the model.
In contrast, non-parametric models typically require graphical descriptions of their fit since any text description would be overly simplistic (\eg `a smooth function') and fitted parameters correspond only to very high level concepts such as bandwidths or typical lengthscales.

Advances in nonparametric and compositional modeling have allowed fully automatic model search and construction of complex, structured, nonparametric regression models \cite{DuvLloGroetal13}.
These automatically-constructed models were demonstrated to be interpretable, but this was performed post-hoc by the authors.
%Fortunately, the generated models are sufficiently structured to capture human-interpretable features in a given dataset, and the compositional nature of this structure allows for simple translation into natural language.

We extend this work by demonstrating that the compositional structure of the models searched over allows for the automatic natural-language description of patterns within a data set \ie the interpretable models are automatically interpreted!
We also expand and improve the components used in the model-construction process to improve the expressivity and interpretability of the models.
\NA{
This allows for the procedure to fit and describe many well established modelling motifs including, linear regression (cite), fourier analysis (cite), sparse spectrum GPs (cite), changepoints (cite), heteroscedasiticty (cite), trend-cyclical-irregular (cite) and nonparametric additive / MKL (cite).
}

This manuscript exhibits extracts of the models and natural-language reports which are automatically generated by our procedure.
The automatically generated text descriptions of the components of the models clearly communicate interpretable features of the data.
The supplementary material to this paper includes several complete reports generated by our method.

Finally, we demonstrate that our procedure is comparable to other model construction techniques as measured by interpolation and extrapolation experiments.

\section{Background: Gaussian Process Structure Search (GPSS)}
\label{sec:gpss}

Gaussian processes (\gp{}) \citep{rasmussen38gaussian} can be used to perform a Bayesian nonparametric regression analysis.
A \gp{} regression model uses a kernel function, ${\kernel : \mathcal{X}^2 \to \mathbb{R}}$, to define the covariance between any two function values, $\outputVar, \outputVar'$ evaluated at two inputs, $\inputVar,\inputVar'$ \ie ${\textrm{Cov}(\outputVar, \outputVar') = \kernel(\inputVar,\inputVar')}$.
The kernel specifies which structures are likely under the \gp{} prior, which in turn determines the generalisation properties of the model.

Different kernels can express a wide variety of covariance structures, such as local smoothness or periodicity.
New kernels can be constructed by taking the product of a set of base kernels to express richer structures, such as functions which are locally periodic, or heteroscedastic.

The Gaussian process structure search (GPSS) procedure \citep{DuvLloGroetal13} searches over sums and products of a set of simple base kernels to produce an appropriate model for a given data set.
It was demonstrated that when applied to time-series the learned kernel structures could be used to decompose the learned regression function into interpretable components.

For example, when applied to airline passenger data (section~\ref{sec:airline}), the syntax of the learned kernel structure was (see section~\ref{sec:notation} for notation)
\begin{equation}
\kSE \times \big( \kLin + \kLin \times ( \kPer + \kRQ ) \big)
\end{equation}
which can be distributed into a sum of products
\begin{equation}
(\kSE \times \kLin) + (\kSE \times \kLin \times \kPer) + (\kSE \times \kLin \times \kRQ).
\end{equation}
This sum decomposed the regression function into three additive components and the second component was described as periodic with linearly increasing amplitude.
It should not be surprising that this description could have been deduced from the linear ($\kLin$) and periodic ($\kPer$) kernels comprising the second product above.

Building upon this observation we demonstrate how to translate arbitrary sums and products of kernels in section~\ref{sec:translation}.
First we introduce some extensions and improvements to the base kernels and generative grammar of GPSS.

\subsection{Notation}
\label{sec:notation}

We typically refer to kernels by their syntax (\ie parameter values are implicit) via the following acronyms; zero -- $\emptyset$, white noise -- $\kWN$, constant -- $\kC$, linear -- $\kLin$, squared-exponential -- $\kSE$, rational-quadratic -- $\kRQ$ and periodic -- $\kPer$.
The parametric forms of these equations are provided in the supplementary material.

\subsection{Remarks}
\label{sec:Remarks}

In this manuscript we restrict to one dimensional regression models.
In the earlier work of \cite{DuvLloGroetal13} the GPSS procedure was applied to multidimensional inputs; we see no obstacles to extending the work in this manuscript to multidimensional inputs.

\section{An improved and expanded language of statistical models}
\label{sec:improvements}

The initial work of \cite{DuvLloGroetal13} constructed the search space of GPSS via four base kernels and a generative grammar applying addition and multiplication operators.
Together they define a language of kernels which in turn defines a language of regression models.

In this section we extend the language to include a greater variety of regression motifs.
We also make modifications to the language to improve the interpretability of the models produced by GPSS where we are guided by the principle that \emph{a model is interpretable if it can automatically be described in natural language}.

\subsection{Changepoints}

The original GPSS language was incapable of accurately describing the non-linear non-stationarity exhibited in a solar irradiance data set (section~\ref{sec:solar}).
A succinct extension to the modelling language to capture this phenomenon is to include the concept of changepoints (cite <NAME>bourne, <NAME> + others more generic papers?).
Suppose that $f_1(x) \dist \gp{}(0, \kernel_1)$ and $f_2(x) \dist \gp{}(0, \kernel_2)$ and define
\begin{equation}
f(x) = (1-\sigma(x))f_1(x) + \sigma(x)f_2(x)
\end{equation}
where $\sigma(x)$ is a sigmoid function varying between 0 and 1 \ie the function $f$ transitions between functions $f_1$ and $f_2$.
Then $f(x) \dist \gp{}(0,\kernel)$ where
\begin{equation}
\kernel(x,x') = (1-\sigma(x))k_1(x,x')(1-\sigma(x')) + \sigma(x)k_2(x)\sigma(x')
\label{eq:cp}
\end{equation}
(see section~\ref{sec:translation} for the properties to prove this identity).

We represent this operation as the changepoint operator $\kCP(\kernel_1, \kernel_2)$.
We also introduce a change window operator, $\kCW(.,.)$, by replacing the sigmoids with products of sigmoids (resulting in a smooth `hat' function).

\subsection{Heteroscedasticity}

We introduce the white noise kernel, $\kWN$, as a base kernel.
When multiplied by linear kernels and changepoints this can express polynomially varying standard deviation as well as switching between different noise regimes.
The original GPSS procedure always assumed homoscedastic noise.

\subsection{An improved periodic kernel}

We introduce a new periodic kernel defined by
\begin{equation}
\kernel_\kPer(x, x') = \kernel_\kPer(\tau) =  \sigma^2\frac{\exp\left(\frac{\cos\frac{2 \pi \tau}{p}}{\ell^2}\right) - I_0\left(\frac{1}{\ell^2}\right)}{\exp\left(\frac{1}{\ell^2}\right) - I_0\left(\frac{1}{\ell^2}\right)}
\label{eq:periodic}
\end{equation}
where $\tau := x - x'$ and $I_0$ is the modified Bessel function of the first kind of order 0.
It is linearly related to the original periodic kernel (cite various) but has the following elegant properties.

\paragraph{Cosine limit}

A simple application of l'H\^opital's rule shows that
\begin{equation}
\kernel_\kPer(\tau) \to \sigma^2\cos\left(\frac{2 \pi \tau}{p}\right) \quad \textrm{as} \quad\ell \to \infty.
\end{equation}
It was recently demonstrated (cite Andrew) that any stationary kernel can be arbitrarily well approximated by kernels with syntax
\begin{equation}
\sum \kSE \times \cos
\end{equation}
by appealing to Bochner's theorem (cite).
By using this new periodic kernel our language of kernels also attains this completeness property.

\paragraph{No power at zero frequency}

The kernel defined by equation~\eqref{eq:periodic} has a Fourier transform of zero when evaluated at zero.
Therefore, functions drawn from a \gp{} with this kernel will have zero mean.
In contrast, the previous periodic kernel defined a prior over a zero mean periodic function plus an independent constant function.
For the purposes of translation we find it more interpretable to separate zero mean periodicity and constant functions.
\NA{
cite Sheffield's orthogonal RKHS work?
}

\subsection{A separate constant kernel}

We also remove the constant component from $\kLin$ and introduce the constant function as a separate base kernel to improve interpretability.

\subsection{No rational quadratic}

The work of \cite{DuvLloGroetal13} also included the rational quadratic kernel which can be represented as a mixture of $\kSE$ with different lengthscales.
In preliminary investigations we found that this mixture of lengthscales could result in individual components expressing smooth trends and noise like components simultaneously.
We have therefore removed this kernel on the grounds of interpretability.

\subsection{A broad language of statistical models}

With these additions to the modelling language we can express a wide variety of regression motifs, shown in table~\ref{table:motifs}.

\begin{table}[ht]
\centering
\begin{tabular}{l|l}
Motif & Example syntax \\
\midrule
Linear regression & $\kC + \kLin$ \\
Fourier analysis & $\kC + \sum \cos$ \\
Sparse spectrum \gp{}s & $\sum \cos$ \\
Spectral kernels & $\sum \SE \times \cos$ \\
Changepoints & \eg $\kCP(\kSE, \kSE)$ \\
Kernel smoothing & $\kSE$ \\
Heteroscedasticity & \eg $\kSE + \kLin \times \kWN$ \\
Trend cyclical irregular & $\sum \kSE + \sum \kPer$ \\
Multiple kernel learning & $\sum \kSE$ \\
\end{tabular}
\caption{
Syntax of common regression motifs expressible in our language.
This table is accurate up to parameter choices, inference methods and noise models.
}
\label{table:motifs}
\end{table}

%In section~\ref{sec:example_translation} we demonstrate the natural-language descriptions of some of these kernel forms.

\subsection{Inference}

We use the same inference techniques as \cite{DuvLloGroetal13} but we introduce new search operators to accommodate the changepoint and change window operators.
The search procedure is not the focus of this manuscript so we defer the details to the supplementary material.

\section{Translation of kernel functions}
\label{sec:translation}

\TBD{Turn this into an algorithm - use the text from the workshop paper}

The extended GPSS language produces sentences composed of 5 base kernels (section~\ref{sec:notation}) and the arbitrary application of addition, multiplication, change point and change window operators. 
We recall elementary facts about kernels and demonstrate how they reduce the problem of translation to simple or finite subproblems.

\paragraph{Changepoints}

We use equation \eqref{eq:cp} to represent changepoints (and similarly change windows) using sums, products, base kernels and sigmoid functions.

\paragraph{Distributivity}

Multiplication is distributive over addition for univariate and kernel functions so we can convert any kernel expression into a sum of products.

\paragraph{Additive kernels}

If $f_1(x) \dist \gp{}(0, \kernel_1)$ and $f_2(x) \dist \gp{}(0, \kernel_2)$ then $f_1(x) + f_2(x) \dist \gp{}(0, \kernel_1 + \kernel_2)$.
Therefore, a sum of kernels can be described as a sum of independent functions.
%We now only need to describe arbitrary products of kernels.

\paragraph{Multiplication by univariate functions}

Suppose that $f(x) \dist \gp{}(0, \kernel)$ and $a : \mathcal{X} \to \mathcal{Y}$ is a deterministic univariate function.
Then $a(x)f(x) \dist \gp{}(0, g)$ where $g(x, x') = a(x)a(x')k(x, x')$.

The linear kernel, $\kLin$, has the form $\kLin(x, x') = c(x-a)(x'-a)$.
Setting $a(x) = \sqrt{c}(x-a)$ we see that multiplying a kernel, $\kernel$, by the linear kernel is equivalent to multiplying $\gp{}(0, k)$ by a linear function.
Similarly, changepoint and change window operators are equivalent to multiplying \gp{}s by sigmoids and hat functions respectively.

Therefore we can separate the descriptions of an arbitrary product into a deterministic univariate function envelope and a stationary kernel.
The univariate envelopes can be arbitrary products of linear functions and sigmoids which can be simply described by their parameters.

We now only need to describe arbitrary products of stationary kernels.

\paragraph{Redundancy}

At a syntactic level, $\kSE$ is idempotent \ie $\kSE \times \kSE = \kSE$.
For stationary kernels, $\kWN$ behaves like zero \eg $\kWN \times \kSE = \kWN \times \kPer =  \kWN$.
The constant kernel $\kC$ behaves like the identity \eg $\kC \times \kLin = \kLin$.

We now only need to describe the base kernels and products of the form $\kSE \times \prod \kPer$.

\paragraph{Base kernels}

The priors induced by the base kernels are well understood, with simple descriptions of typical functions.

\begin{table}[ht]
\centering
\begin{tabular}{c|c}
Kernel & Function description \\
\midrule
$\kWN$ & White noise \\
$\kC$ & Constant \\
$\kLin$ & Linear \\
$\kSE$ & Smooth \\
$\kPer$ & Periodic \\
\end{tabular}
\label{table:base-kernels}
\end{table}

\paragraph{$\prod \kPer$}

Suppose that ${f_1(x) \dist \gp{}(0, \kernel_1)}$ and ${f_2(x) \dist \gp{}(0, \kernel_2)}$.
Then
\begin{equation}
{\textrm{Covar}(f_1(x)f_2(x), f_1(x')f_2(x')) = k_1(x,x')k_2(x,x')}.
\end{equation}
Therefore $\prod \kPer$ defines a prior on functions whose covariance is the same as the product of independent periodic functions.

\paragraph{$\kSE \times \kPer$}

This kernel gives rise to locally periodic functions.
Indeed, if the input space is restricted to a grid with spacing equal to the period of the periodic kernel then $\kSE \times \kPer = \kSE$.
We therefore see that the functional form of the periodicity varies like $\kSE$, giving rise to the local nature of the periodicity.
This observation extends similarly to kernels of the form $\kSE \times \prod \kPer$.

\subsection{Ordering additive components}

\TBD{Not worthy of main body - try to make small}

An automatic regression system would ideally report the most interesting or important features of the data first.
\NA{
However, measuring importance is subjective.
We make the choice that additive components are important if they produce accurate extrapolations and order the components by this metric.
See the supplementary material for details.
}

%\subsection{Example translations}
%\label{sec:example_translation}

%\NA{
%Make a better version of table~\ref{table:descriptions} - perhaps describing some of the classical regression motifs.
%}

%\begin{table}[ht]
%\begin{tabular}{l|l}
%Kernel & Description \\
%\midrule
%$\kPer$ & An exactly periodic function \\
%$\kPer \times \kSE$ & An approximately periodic function \\
%$\kPer \times \kSE \times \kLin$ & An approximately periodic function with linearly varying amplitude \\
%$\kLin$ & A linear function \\
%$\kLin \times \kLin$ & A quadratic function \\
%$\kPer \times \kLin \times \kLin$ & An exactly periodic function with quadratically varying amplitude\\
%\end{tabular}
%\caption{
%Example translations of }
%\label{table:descriptions}
%\end{table}

\subsection{When is a description `correct'?}

\TBD{This can be significantly shortened - do not need model checking yet}

In the above we have described how to produce a description of the prior of a \gp{} described by an arbitrary kernel.
However, when describing a particular data set we are interested in the posterior of the function describing the data.

%For example, when fitting a linear regression model, the fit to the data will always be linear, for any data set.
%One can test the assumptions of linear regression by model checking.
%For example, one can test the prior independence assumption of the residuals by computing statistics of the posterior residuals and comparing to those expected under the prior \ie comparing the prior and posterior of parts of the model.

We have begun to experiment with using posterior predictive checks to check the models produced by GPSS.
Following the techniques of (cite Gelman, Meng and Stern) applied to each component of a model corresponds to comparing statistics of the posterior of each component with the statistics of its prior.
That is, posterior predictive checks when applied to additive Gaussian processes indicate a lack of fit only when the posteriors are dissimilar to their priors.

The reports in the supplementary compute and discuss a number of posterior predictive $p$-values. for each additive component.
These $p$-values appear to be a useful diagnostic tool, identifying \eg heavy-tailed noise distributions or un-modelled periodicity.
However, model checking for Gaussian processes, even those with simple kernels, is under-researched so we leave their description and more detailed analysis for future work.

%In the same way, one must also check the models produced by GPSS; this can take the form of testing whether the posterior of each component resembles its prior as measured by a variety of statistics.
%The plots in the later sections allow human model checking of this form, but ideally this process should be automated as well.
%We are actively researching model checking methods for \gp{} models.

%\NA{
%Some thoughts\ldots
%Optimising marginal likelihood is attempting to maximise the probability of a data set given the model.
%The components can still be anti-correlated which is a problem - but model checking can see this if necessary.
%A small amount of descriptions are about the posterior (\eg increasing / decreasing linear functions).
%Posterior predictive checks compare posterior and prior (of the not parameters), so we believe our model is reasonable when prior and posterior align and we have a greater chance of this happening when we search over a large space of models.
%What are consistency results about additive \gp{}s, or other additive nonparametric models - clearly there can be non-identifiability.
%}

\section{Related work}

\paragraph{Equation learning}

In this work we have defined a search space of statistical models, where each model is characterised by a parametric covariance function.
Previous work has considered searching over parametric functions (cite equation learning).
Some functions are well explained parametrically \eg a logistic function, whereas others are best described by their covariance \eg an approximately periodic function.
It is our opinion that equation learning and covariance learning should ultimately be combined.

\paragraph{Searching over statistical models}

GPSS was originally inspired by the search over matrix factorisation models by (cite Roger).
This work and GPSS is possible for the following reasons: we can define a large space of models through a succinct langauge, inference can be performed for all sentences in this language and a basic search procedure is sufficient to find accurate models.
\NA{
This is also true of - can we also cite some sort of graphical model work?
}

\paragraph{Standardised inference methods}

The GPSS language can express many regression motifs as \gp{}s for which inference is well understood.
Probabilistic programming (cite) defines languages that describe generative models in such a way that inference can be performed in each model.
Extending the model search ideas in GPSS to searches over probabilistic programs would be an interesting area for future research.

\paragraph{Natural-language descriptions of data}

To the best of our knowledge, the automatic translation of nonparametric statistical models is novel (whereas parametric models are typically described by their parameters).
However, grammar based techniques have previously been used to automatically understand images (cite something?) and recently (cite Gowers) have produced a theorem proving system that expresses its proof in natural language.

\section{Natural-language description of time series}
\label{sec:examples}

\TBD{Look at workshop paper for changes to language}

We demonstrate the ability of our procedure to describe a variety of patterns on two time series (full automatically produced reports for a greater number of data sets are provided as supplementary material).
The automatic natural-language descriptions objectively demonstrate that the models produced are interpretable.
However, it is difficult to quantify the quality of a verbal description so we also provide numerical evidence in support of our procedure in section~\ref{sec:numerical}.

%Our report generation procedure takes as its starting point a dataset and a composite kernel, which together define a joint posterior probability distribution over a sum of functions.
%The procedure summarizes properties of this complex distribution to the user through a comprehensive report.
%
%These reports are designed to be intelligible to non-experts, illustrating the assumptions made by the model, describing the model's posterior distribution, and most importantly, enabling model-checking.
%\subsection{Design goals}
%
%\begin{itemize}
%\item {\bf Intelligibility}
%The procedure was designed to produce reports intelligible to non-experts.  
%
%\item {\bf Illustrate Model Assumptions}
%One of the main design criteria when designing our procedure was to make clear what assumptions the model is making, and what these assumptions imply in terms of extrapolation.  Even when simple Gaussian process models are used, it is often unclear what structure was captured by the model and what was not.
%
%\item {\bf Illustrate Posterior Uncertainty}
%One of the selling points of Bayesian modeling over point estimates is that they produce a rich posterior distribution over possible explanations of the data.  However, this posterior distribution is often quite a complex object, and is usually difficult to summarize.
%
%\item {\bf Enable Model-checking}
%One of the most important reasons to examine a model is to discover flawed assumptions, or structure not captured by the model.  Simply examining residuals, cross-validation or marginal likelihood scores is often not sufficient to notice when the model is failing to capture.
%\end{itemize}<commit_msg>Updates to first half of text<commit_after>% Use the following line _only_ if you're still using LaTeX 2.09.
%\documentstyle[icml2014,epsf,natbib]{article}
% If you rely on Latex2e packages, like most modern people use this:
\documentclass{article}

% use Times
\usepackage{times}
% For figures
\usepackage{graphicx} % more modern
%\usepackage{epsfig} % less modern
\usepackage{subfigure} 

% For citations
\usepackage{natbib}

% For algorithms
%\usepackage{algorithm}
%\usepackage{algorithmic}
%\usepackage{algorithmicx}

% As of 2011, we use the hyperref package to produce hyperlinks in the
% resulting PDF.  If this breaks your system, please commend out the
% following usepackage line and replace \usepackage{icml2014} with
% \usepackage[nohyperref]{icml2014} above.
\usepackage{hyperref}

% Packages hyperref and algorithmic misbehave sometimes.  We can fix
% this with the following command.
\newcommand{\theHalgorithm}{\arabic{algorithm}}

% Employ the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
\usepackage{format/icml2014} 
% Employ this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Proceedings of the...''
%\usepackage[accepted]{icml2014}

\usepackage{times}
\usepackage{hyperref}
\usepackage{url}
\usepackage{color}
\usepackage{preamble}
\definecolor{mydarkblue}{rgb}{0,0.08,0.45}
\hypersetup{ %
    pdftitle={},
    pdfauthor={},
    pdfsubject={},
    pdfkeywords={},
    pdfborder=0 0 0,
    pdfpagemode=UseNone,
    colorlinks=true,
    linkcolor=mydarkblue,
    citecolor=mydarkblue,
    filecolor=mydarkblue,
    urlcolor=mydarkblue,
    pdfview=FitH}
    
    
\usepackage{amsmath, amsfonts, bm, lipsum, capt-of}
\usepackage{natbib, xcolor, wrapfig, booktabs, multirow, caption}
\DeclareCaptionType{copyrightbox}
\usepackage{float}


%\renewcommand{\baselinestretch}{0.99}

\def\ie{i.e.\ }
\def\eg{e.g.\ }
\let\oldemptyset\emptyset
\let\emptyset\varnothing

%\author{
%<NAME>\\
%University of Cambridge\\
%Department of Engineering\\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%University of Cambridge \\
%Department of Engineering \\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%M.I.T.\\
%Brain and Cognitive Sciences \\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%M.I.T.\\
%Brain and Cognitive Sciences \\
%\texttt{<EMAIL>}
%\And
%<NAME>\\
%University of Cambridge \\
%Department of Engineering \\
%\texttt{<EMAIL>}
%}

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\setlength{\marginparwidth}{0.6in}
\input{include/commenting.tex}

%% For submission, make all render blank.
%\renewcommand{\LATER}[1]{}
%\renewcommand{\fLATER}[1]{}
%\renewcommand{\TBD}[1]{}
%\renewcommand{\fTBD}[1]{}
%\renewcommand{\PROBLEM}[1]{}
%\renewcommand{\fPROBLEM}[1]{}
%\renewcommand{\NA}[1]{#1}  % Note, NA's pass through!


% The \icmltitle you define below is probably too long as a header.
% Therefore, a short form for the running title is supplied here:
\icmltitlerunning{Automatic construction and natural-language summarization of additive nonparametric models}

\begin{document} 

\twocolumn[
\icmltitle{Automatic construction and natural-language summarization\\of additive nonparametric models}

% It is OKAY to include author information, even for blind
% submissions: the style file will automatically remove it for you
% unless you've provided the [accepted] option to the icml2014
% package.
\icmlauthor{Your Name}{<EMAIL>}
\icmladdress{Your Fantastic Institute,
            314159 Pi St., Palo Alto, CA 94306 USA}
\icmlauthor{Your CoAuthor's Name}{<EMAIL>}
\icmladdress{Their Fantastic Institute,
            27182 Exp St., Toronto, ON M6H 2T1 CANADA}

% You may provide any keywords that you 
% find helpful for describing your paper; these are used to populate 
% the "keywords" metadata in the PDF but will not be shown in the document
\icmlkeywords{}

\vskip 0.3in
]

\begin{abstract} 
One of the broad aims of statistics is to produce an accurate and concise description of data.
Parametric techniques typically produces a concise description of data but can be inaccurate when there are deviations from the strong assumptions implied by parametric forms.
In contrast, nonparametric methods are typically capable of providing accurate descriptions of many data sets but at the expense of succinct descriptions.
To address this apparent antagonism we demonstrate that a recently introduced nonparametric model construction technique allows for the automatic natural-language description of a data set into natural-language while also constructing an accurate model.
We also extend the class of models that can be produced by this model construction method to include a wide variety of regression motifs.
\end{abstract} 

\allowdisplaybreaks

\section{Introduction}

Simple parametric regression models such as linear regression are usually easily interpretable, requiring only a table of regression coefficients and a few other parameters to describe the model.
In contrast, non-parametric models typically require graphical descriptions of their fit since any text description would be overly simplistic (\eg `a smooth function') and fitted parameters correspond only to very high level concepts such as bandwidths or typical lengthscales.

Several recently proposed methods search over a large class of structured nonparametric regression models \citep{DuvLloGroetal13, kronberger2013evolution, diosan2007evolving, bing2010gp}.
In \citep{DuvLloGroetal13}, it was noted that these models could be decomposed into sums of diverse components, and that the different components corresponded to interpretable features of the data.
In that work, components discovered on real datasets were interpreted post-hoc by the authors.

We extend this work by demonstrating that the compositional structure of the models searched over allows for the automatic natural-language description of patterns within a data set \ie the interpretable models are automatically interpreted!
We also expand and improve the components used in the model-construction process to improve the expressivity and interpretability of the models.
This allows for the procedure to fit and describe many well established modelling motifs including, linear regression, Fourier analysis, sparse spectrum \gp{}s (cite), changepoints (cite), heteroscedasiticty (cite), trend-cyclical-irregular (cite) and nonparametric additive / MKL (cite).

This manuscript exhibits extracts of the models and natural-language reports which are automatically generated by our procedure.
The automatically generated text descriptions of the components of the models clearly communicate interpretable features of the data.
The supplementary material to this paper includes several complete reports generated by our method.

Finally, we demonstrate that our procedure is comparable to other model construction techniques as measured by interpolation and extrapolation experiments.

\section{Background: Gaussian Process Structure Search (GPSS)}
\label{sec:gpss}

Gaussian processes (\gp{}) \citep{rasmussen38gaussian} can be used to perform a Bayesian nonparametric regression analysis.
A \gp{} regression model uses a kernel function, ${\kernel : \mathcal{X}^2 \to \mathbb{R}}$, to define the covariance between any two function values, $\outputVar, \outputVar'$ evaluated at two inputs, $\inputVar,\inputVar'$ \ie ${\textrm{Cov}(\outputVar, \outputVar') = \kernel(\inputVar,\inputVar')}$.
The kernel specifies which structures are likely under the \gp{} prior, which in turn determines the generalisation properties of the model.

Different kernels can express a wide variety of covariance structures, such as local smoothness or periodicity.
New kernels can be constructed by taking the product of a set of base kernels to express richer structures, such as functions which are locally periodic, or heteroscedastic.

The Gaussian process structure search (GPSS) procedure \citep{DuvLloGroetal13} searches over sums and products of a set of simple base kernels to produce an appropriate model for a given data set.
It was demonstrated that when applied to time-series the learned kernel structures could be used to decompose the learned regression function into interpretable components.

For example, when applied to airline passenger data (section~\ref{sec:airline}), the syntax of the learned kernel structure was (see section~\ref{sec:notation} for notation)
\begin{equation}
\kSE \times \big( \kLin + \kLin \times ( \kPer + \kRQ ) \big)
\end{equation}
which can be distributed into a sum of products
\begin{equation}
(\kSE \times \kLin) + (\kSE \times \kLin \times \kPer) + (\kSE \times \kLin \times \kRQ).
\end{equation}
This sum decomposed the regression function into three additive components and the second component was described as periodic with linearly increasing amplitude.
It should not be surprising that this description could have been deduced from the linear ($\kLin$) and periodic ($\kPer$) kernels comprising the second product above.

Building upon this observation we demonstrate how to translate arbitrary sums and products of kernels in section~\ref{sec:translation}.
First we introduce some extensions and improvements to the base kernels and generative grammar of GPSS.

\subsection{Notation}
\label{sec:notation}

We typically refer to kernels by their syntax (\ie parameter values are implicit) via the following acronyms; zero -- $\emptyset$, white noise -- $\kWN$, constant -- $\kC$, linear -- $\kLin$, squared-exponential -- $\kSE$, rational-quadratic -- $\kRQ$ and periodic -- $\kPer$.
The parametric forms of these equations are provided in the supplementary material.

\subsection{Remarks}
\label{sec:Remarks}

In this manuscript we restrict to one dimensional regression models.
In the earlier work of \cite{DuvLloGroetal13} the GPSS procedure was applied to multidimensional inputs; we see no obstacles to extending the work in this manuscript to multidimensional inputs.

\section{An improved and expanded language of statistical models}
\label{sec:improvements}

The initial work of \cite{DuvLloGroetal13} constructed the search space of GPSS via four base kernels and a generative grammar applying addition and multiplication operators.
Together they define a language of kernels which in turn defines a language of regression models.

In this section we extend the language to include a greater variety of regression motifs.
We also make modifications to the language to improve the interpretability of the models produced by GPSS where we are guided by the principle that \emph{a model is interpretable if it can automatically be described in natural language}.

\subsection{Changepoints}

The original GPSS language was incapable of accurately describing the non-linear non-stationarity exhibited in a solar irradiance data set (section~\ref{sec:solar}).
A succinct extension to the modelling language to capture this phenomenon is to include the concept of changepoints (cite Mike Osbourne, <NAME> + others more generic papers?).
Suppose that $f_1(x) \dist \gp{}(0, \kernel_1)$ and $f_2(x) \dist \gp{}(0, \kernel_2)$ and define
\begin{equation}
f(x) = (1-\sigma(x))f_1(x) + \sigma(x)f_2(x)
\end{equation}
where $\sigma(x)$ is a sigmoid function varying between 0 and 1 \ie the function $f$ transitions between functions $f_1$ and $f_2$.
Then $f(x) \dist \gp{}(0,\kernel)$ where
\begin{equation}
\kernel(x,x') = (1-\sigma(x))k_1(x,x')(1-\sigma(x')) + \sigma(x)k_2(x)\sigma(x')
\label{eq:cp}
\end{equation}
(see section~\ref{sec:translation} for the properties to prove this identity).

We represent this operation as the changepoint operator $\kCP(\kernel_1, \kernel_2)$.
We also introduce a change window operator, $\kCW(.,.)$, by replacing the sigmoids with products of sigmoids (resulting in a smooth `hat' function).

\subsection{Heteroscedasticity}

We introduce the white noise kernel, $\kWN$, as a base kernel.
When multiplied by linear kernels and changepoints this can express polynomially varying standard deviation as well as switching between different noise regimes.
The original GPSS procedure always assumed homoscedastic noise.

\subsection{An improved periodic kernel}

We introduce a new periodic kernel defined by
\begin{equation}
\kernel_\kPer(x, x') = \kernel_\kPer(\tau) =  \sigma^2\frac{\exp\left(\frac{\cos\frac{2 \pi \tau}{p}}{\ell^2}\right) - I_0\left(\frac{1}{\ell^2}\right)}{\exp\left(\frac{1}{\ell^2}\right) - I_0\left(\frac{1}{\ell^2}\right)}
\label{eq:periodic}
\end{equation}
where $\tau := x - x'$ and $I_0$ is the modified Bessel function of the first kind of order 0.
It is linearly related to the original periodic kernel (cite various) but has the following elegant properties.

\paragraph{Cosine limit}

A simple application of l'H\^opital's rule shows that
\begin{equation}
\kernel_\kPer(\tau) \to \sigma^2\cos\left(\frac{2 \pi \tau}{p}\right) \quad \textrm{as} \quad\ell \to \infty.
\end{equation}
It was recently demonstrated (cite Andrew) that any stationary kernel can be arbitrarily well approximated by kernels with syntax
\begin{equation}
\sum \kSE \times \cos
\end{equation}
by appealing to Bochner's theorem (cite).
By using this new periodic kernel our language of kernels also attains this completeness property.

\paragraph{No power at zero frequency}

The kernel defined by equation~\eqref{eq:periodic} has a Fourier transform of zero when evaluated at zero.
Therefore, functions drawn from a \gp{} with this kernel will have zero mean.
In contrast, the previous periodic kernel defined a prior over a zero mean periodic function plus an independent constant function.
For the purposes of translation we find it more interpretable to separate zero mean periodicity and constant functions.
\NA{
cite Sheffield's orthogonal RKHS work?
}

\subsection{A separate constant kernel}

We also remove the constant component from $\kLin$ and introduce the constant function as a separate base kernel to improve interpretability.

\subsection{No rational quadratic}

The work of \cite{DuvLloGroetal13} also included the rational quadratic kernel which can be represented as a mixture of $\kSE$ with different lengthscales.
In preliminary investigations we found that this mixture of lengthscales could result in individual components expressing smooth trends and noise like components simultaneously.
We have therefore removed this kernel on the grounds of interpretability.

\subsection{A broad language of statistical models}

With these additions to the modelling language we can express a wide variety of regression motifs, shown in table~\ref{table:motifs}.

\begin{table}[ht]
\centering
\begin{tabular}{l|l}
Motif & Example syntax \\
\midrule
Linear regression & $\kC + \kLin$ \\
Fourier analysis & $\kC + \sum \cos$ \\
Sparse spectrum \gp{}s & $\sum \cos$ \\
Spectral kernels & $\sum \SE \times \cos$ \\
Changepoints & \eg $\kCP(\kSE, \kSE)$ \\
Kernel smoothing & $\kSE$ \\
Heteroscedasticity & \eg $\kSE + \kLin \times \kWN$ \\
Trend cyclical irregular & $\sum \kSE + \sum \kPer$ \\
Multiple kernel learning & $\sum \kSE$ \\
\end{tabular}
\caption{
Syntax of common regression motifs expressible in our language.
This table is accurate up to parameter choices, inference methods and noise models.
}
\label{table:motifs}
\end{table}

%In section~\ref{sec:example_translation} we demonstrate the natural-language descriptions of some of these kernel forms.

\subsection{Inference}

We use the same inference techniques as \cite{DuvLloGroetal13} but we introduce new search operators to accommodate the changepoint and change window operators.
The search procedure is not the focus of this manuscript so we defer the details to the supplementary material.

\section{Translation of kernel functions}
\label{sec:translation}

The extended GPSS language produces sentences composed of 5 base kernels (section~\ref{sec:notation}) and the arbitrary application of addition, multiplication, change point and change window operators. 
In this section, we describe how the compositional properties of kernel functions reduce the task of natural-language description into relatively simple subproblems.
The text follows the flow of algorithm~\ref{alg:translation}.

\begin{algorithm}[tb]
   \caption{Describe kernel expression}
   \label{alg:translation}
\begin{algorithmic}
   \STATE {\bfseries Input:} kernel expression $e$
   \STATE $e = {ChangePointsToSumsAndProducts}(e)$
   \STATE $e = {DistributeProducts}(e)$
   \FOR{$k$ in $e.sumands$}
   \STATE \COMMENT{Individual summands can be described separately}
     \REPEAT
       \STATE $k = Simplify(k)$
     \UNTIL $k$ is unchanged
     \STATE $DescribeLinearComponents(k)$
     \STATE $DescribeChangePointComponents(k)$
     \STATE $DescribeStationaryComponents(k)$
   \ENDFOR
\end{algorithmic}
\end{algorithm}

\paragraph{Changepoints}

We use equation \eqref{eq:cp} to represent changepoints (and similarly change windows) using sums, products, base kernels and sigmoid functions.

\paragraph{Distributivity}

Pointwise multiplication is distributive over addition for functions so we can convert any kernel expression into a sum of products.

\paragraph{Sums of kernels are sums of functions}

If $f_1(x) \dist \gp{}(0, \kernel_1)$ and $f_2(x) \dist \gp{}(0, \kernel_2)$ then $f_1(x) + f_2(x) \dist \gp{}(0, \kernel_1 + \kernel_2)$.
Therefore, a sum of kernels can be described as a sum of functions.
We now only need to describe arbitrary products of kernels.

\paragraph{Simplification}

At a syntactic level, $\kSE$ is idempotent \ie $\kSE \times \kSE = \kSE$ (simply, the product of two $\kSE$ kernels is another $\kSE$ kernel but with different parameters).
For stationary kernels, $\kWN$ behaves like zero \eg $\kWN \times \kSE = \kWN \times \kPer =  \kWN$.
The constant kernel $\kC$ behaves like the identity \eg $\kC \times \kLin = \kLin$

\paragraph{Multiplication by linear kernels}

$\kLin$ has the form $k(x,x') = a(x)a(x')$.
This can be used as follows: suppose that $f(x) \dist \gp{}(0, \kernel)$ and $a : \mathcal{X} \to \mathcal{Y}$ is a deterministic function.
Then $a(x)f(x) \dist \gp{}\left(0, a(x) k(x, x') a(x') \right)$.
Therefore multiplying a kernel, $\kernel$, by the linear kernel is equivalent to multiplying $f(x) \sim \gp{}(0, k)$ by a linear function.

This allows us to describe any linear kernels separately.
For example, multiplying by a linear kernel means that the amplitude of the function grows linearly away from a central point.
Multiplication by two linear kernels results in quadratic growth, etc.

\paragraph{Changepoints and changewindows}

Representing changepoints/windows as sigmoid functions as shown in equation~\eqref{eq:cp} also results in kernels of the form $a(x)k(x,x')a(x')$ where $a(x)$ is a sigmoid (changepoint) or product of sigmoids (changewindow).
Therefore the application of changepoint/window operators can be described separately as multiplication of functions by sigmoids.
When the sigmoids transition between 0 and 1 sharply the effect is particularly trivial to express in natural-language \eg ``this component applies from 1700 to 1800''.

We now only need to describe the base kernels and products of the form $\kSE \times \prod \kPer$.

\paragraph{Base kernels}

The priors induced by the base kernels are well understood, with simple descriptions of typical functions.

\begin{table}[ht]
\centering
\begin{tabular}{c|c}
Kernel & Function description \\
\midrule
$\kWN$ & White noise \\
$\kC$ & Constant \\
$\kLin$ & Linear \\
$\kSE$ & Smooth \\
$\kPer$ & Periodic \\
\end{tabular}
\label{table:base-kernels}
\end{table}

\paragraph{$\kSE \times \kPer$}

gives rise to functions which are \emph{locally} periodic: they only approximately repeat.
More exactly, if the input space is restricted to a grid with spacing equal to the period of the periodic kernel, then $\kSE \times \kPer = \kSE$.
That is, the functional form of the periodicity varies like $\kSE$, giving rise to the local nature of the periodicity.

\paragraph{Products of multiple periodic kernels}

Suppose that ${f_1(x) \dist \gp{}(0, \kernel_1)}$ and ${f_2(x) \dist \gp{}(0, \kernel_2)}$.
Then
\begin{equation}
{\textrm{Cov} \left[f_1(x)f_2(x), f_1(x')f_2(x') \right] = k_1(x,x')k_2(x,x')}.
\end{equation}
Therefore $\kPer \times \kPer$ defines a prior on functions whose covariance is the same as the product of independent periodic functions.  However, note that a product of periodic functions drawn from \gp{} priors will not be distributed according to a \gp{}.

\subsection{Ordering additive components}

An automatic regression system would ideally report the most interesting or important features of the data first.
\NA{
However, measuring importance is subjective.
We make the choice that additive components are important if they produce accurate extrapolations and order the components by this metric.
See the supplementary material for details.
}

\subsection{When is a description `correct'?}

In the above we have described how to produce a description of the prior of a \gp{} described by an arbitrary kernel.
The GPSS procedure attempts to find the best fitting model for a data set subject to the constraints of its modeling language.
Of course, a data set may not be well described by any model in this language and therefore the natural-language description will be spurious.

We have begun to experiment with using posterior predictive checks to check the models produced by GPSS following the techniques of (cite Gelman, Meng and Stern) (see reports reports in the supplementary material).
However, model checking for Gaussian processes, even those with simple kernels, is under-researched so we leave their description and more detailed analysis for future work.

\section{Related work}

\paragraph{Equation learning}

In this work we have defined a search space of statistical models, where each model is characterised by a parametric covariance function.
Previous work has considered searching over parametric functions (cite equation learning).
Some functions are well explained parametrically \eg a logistic function, whereas others are best described by their covariance \eg an approximately periodic function.
It is our opinion that equation learning and covariance learning should ultimately be combined.

\paragraph{Searching over statistical models}

GPSS was originally inspired by the search over matrix factorisation models by (cite Roger).
This work and GPSS is possible for the following reasons: we can define a large space of models through a succinct langauge, inference can be performed for all sentences in this language and a basic search procedure is sufficient to find accurate models.
\NA{
This is also true of - can we also cite some sort of graphical model work?
}

\paragraph{Standardised inference methods}

The GPSS language can express many regression motifs as \gp{}s for which inference is well understood.
Probabilistic programming (cite) defines languages that describe generative models in such a way that inference can be performed in each model.
Extending the model search ideas in GPSS to searches over probabilistic programs would be an interesting area for future research.

\paragraph{Natural-language descriptions of data}

To the best of our knowledge, the automatic translation of nonparametric statistical models is novel (whereas parametric models are typically described by their parameters).
However, grammar based techniques have previously been used to automatically understand images (cite something?) and recently (cite Gowers) have produced a theorem proving system that expresses its proof in natural language.

\section{Natural-language description of time series}
\label{sec:examples}

We demonstrate the ability of our procedure to describe a variety of patterns on two time series (full automatically produced reports for a greater number of data sets are provided as supplementary material).
The automatic natural-language descriptions objectively demonstrate that the models produced are interpretable.
However, it is difficult to quantify the quality of a verbal description so we also provide numerical evidence in support of our procedure in section~\ref{sec:numerical}.

%Our report generation procedure takes as its starting point a dataset and a composite kernel, which together define a joint posterior probability distribution over a sum of functions.
%The procedure summarizes properties of this complex distribution to the user through a comprehensive report.
%
%These reports are designed to be intelligible to non-experts, illustrating the assumptions made by the model, describing the model's posterior distribution, and most importantly, enabling model-checking.
%\subsection{Design goals}
%
%\begin{itemize}
%\item {\bf Intelligibility}
%The procedure was designed to produce reports intelligible to non-experts.  
%
%\item {\bf Illustrate Model Assumptions}
%One of the main design criteria when designing our procedure was to make clear what assumptions the model is making, and what these assumptions imply in terms of extrapolation.  Even when simple Gaussian process models are used, it is often unclear what structure was captured by the model and what was not.
%
%\item {\bf Illustrate Posterior Uncertainty}
%One of the selling points of Bayesian modeling over point estimates is that they produce a rich posterior distribution over possible explanations of the data.  However, this posterior distribution is often quite a complex object, and is usually difficult to summarize.
%
%\item {\bf Enable Model-checking}
%One of the most important reasons to examine a model is to discover flawed assumptions, or structure not captured by the model.  Simply examining residuals, cross-validation or marginal likelihood scores is often not sufficient to notice when the model is failing to capture.
%\end{itemize}
{'fraction_non_alphanumeric': 0.07916504024238369, 'fraction_numerical': 0.0061339430100931245, 'mean_word_length': 4.851005981511691, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2483439', 'n_tokens_mistral': 14557, 'n_tokens_neox': 13597, 'n_words': 6898}