# An Unified Search and Recommendation Foundation Model for Cold-Start
Scenario

Yuqi Gong  Ant GroupBeijingChina<EMAIL_ADDRESS>,  Xichen Ding  Ant
GroupBeijingChina<EMAIL_ADDRESS>,  Yehui Su  Ant GroupBeijingChina
<EMAIL_ADDRESS>,  Kaiming Shen  Ant GroupBeijingChina
<EMAIL_ADDRESS>,  Zhongyi Liu  Ant GroupHangzhouChina
<EMAIL_ADDRESS>and  Guannan Zhang  Ant GroupHangzhouChina
<EMAIL_ADDRESS>
(2023)

###### Abstract.

In modern commercial search engines and recommendation systems, data from
multiple domains is available to jointly train the multi-domain model.
Traditional methods train multi-domain models in the multi-task setting, with
shared parameters to learn the similarity of multiple tasks, and task-specific
parameters to learn the divergence of features, labels, and sample
distributions of individual tasks. With the development of large language
models, LLM can extract global domain-invariant text features that serve both
search and recommendation tasks. We propose a novel framework called S&R
Multi-Domain Foundation, which uses LLM to extract domain invariant features,
and Aspect Gating Fusion to merge the ID feature, domain invariant text
features and task-specific heterogeneous sparse features to obtain the
representations of query and item. Additionally, samples from multiple search
and recommendation scenarios are trained jointly with Domain Adaptive Multi-
Task module to obtain the multi-domain foundation model. We apply the S&R
Multi-Domain foundation model to cold start scenarios in the pretrain-finetune
manner, which achieves better performance than other SOTA transfer learning
methods. The S&R Multi-Domain Foundation model has been successfully deployed
in Alipay Mobile Application’s online services, such as content query
recommendation and service card recommendation, etc.

###### Abstract.

In modern commercial search engines and recommendation systems, data from
multiple domains is available to jointly train the multi-domain model.
Traditional methods train multi-domain models in the multi-task setting, with
shared parameters to learn the similarity of multiple tasks, and task-specific
parameters to learn the divergence of features, labels, and sample
distributions of individual tasks. With the development of large language
models, LLM can extract global domain-invariant text features that serve both
search and recommendation tasks. We propose a novel framework called S&R
Multi-Domain Foundation, which uses LLM to extract domain invariant features,
and Aspect Gating Fusion to merge the ID feature, domain invariant text
features and task-specific heterogeneous sparse features to obtain the
representations of query and item. Additionally, samples from multiple search
and recommendation scenarios are trained jointly with Domain Adaptive Multi-
Task module to obtain the multi-domain foundation model. We apply the S&R
Multi-Domain foundation model to cold start scenarios in the pretrain-finetune
manner, which achieves better performance than other SOTA transfer learning
methods. The S&R Multi-Domain Foundation model has been successfully deployed
in Alipay Mobile Application’s online services, such as content query
recommendation and service card recommendation, etc.

search and recommendation, LLM, multi-domain recommendation

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
32nd ACM International Conference on Information and Knowledge Management;
October 21–25, 2023; Birmingham, United Kingdom††booktitle: Proceedings of the
32nd ACM International Conference on Information and Knowledge Management
(CIKM ’23), October 21–25, 2023, Birmingham, United Kingdom††price:
15.00††doi: 10.1145/3583780.3614657††isbn: 979-8-4007-0124-5/23/10††ccs:
Computing methodologies Machine learning algorithms††ccs: Information systems
Data mining††ccs: Information systems Retrieval models and ranking

##  1\. Introduction

Modern commercial recommendation systems and search engines are widely used in
online service platforms such as YouTube, TikTok, Taobao, Alipay, etc. Search
and recommendation can facilitate users’ behaviors to browse instant videos,
buy products, use services, and make payments using E-wallets. The similarity
between Search (S) and Recommendation (R) makes jointly modeling S&R a
promising research topic. Some work (Si et al., 2023; Si et al., 2022) propose
to enhance recommendation by learning from a unified sequence of search and
recommendation behaviors. Others (Liu et al., 2022; Ai et al., 2017) propose
to improve personalized search by adding users’ multi-interests in
recommendation. Methods to model search and recommendation tasks jointly are
also proposed in (Xu et al., 2018; Zamani and Croft, 2020, 2018; Yao et al.,
2021; Zhao et al., 2022). JSR framework in (Zamani and Croft, 2018)
simultaneously learns retrieval and recommendation models with shared item set
and optimizes a joint loss function. Researchers in (Yao et al., 2021) applied
two-level transformer encoders, text encoder to learn documents and queries,
session encoder to model the integrated sequence of search and browsing
behaviors. (Zhao et al., 2022) applied GNN to learn node embedding of
user&item, and treat search query as a special attribute of edges in the
graph. In industrial scenarios, there are several benefits to model S and R
jointly. First, there are multiple search and recommendation scenarios in a
single mobile application. The training data collected in a single domain
can’t fully reflect users’ complete intents and is sub-optimal compared to
modeling them jointly. Secondly, majority of items are shared between search
and recommendation. Once users have impressions of any products, videos, and
services in a recommendation scenario, they should be able to retrieve the
item in Search later for repurchase or reuse purposes. Despite the similarity
between Search and Recommendation, there are also difficulties in modeling
them jointly, such as the data imbalance issue of multiple domains, the
heterogeneous issue of different item sets (videos, products, and services),
the negative transferring issue. With the latest developments in large
language models (LLM) (Brown et al., 2020; Zhao et al., 2023; Touvron et al.,
2023; Cui et al., 2022a, b), the pretrain-finetune framework (Zhao et al.,
2022; Si et al., 2023; Yao et al., 2021; Ding et al., 2019; Li et al., 2022)
greatly improves the performance of downstream tasks. We are inspired by the
strong expressive power of natural language features and propose to build the
Search and Recommendation Foundation model on top of LLMs, which extract low-
level domain-invariant text features of the query (Q) and item (I). The major
difference between our S&R foundation model and traditional multi-domain
multi-task models is how we use the domain-invariant text features to help
constrain the divergence of different tasks, which alleviates data imbalance,
negative transferring, and item heterogeneous issues. To summarize, our
proposed S&R Foundation model has the following key contributions:

  * •

We apply LLMs in S&R Multi-Domain Foundation model, and extract domain
invariant text features to help mitigate the negative transferring and item
heterogeneous issues in the multi-domain settings.

  * •

We novelly proposed the Aspect Gating Fusion (Domain-Specific Gating) to fuse
the ID feature, text features from LLMs, and sparse features. The Domain
Adaptive Multi-Task module is also used to extract the domain-specific query
and item towers’ representations.

  * •

For the cold start of new scenarios, we have conducted extensive experiments
both offline and online, to show the effectiveness of supervised fine-tuning
of our S&R Foundation model in downstream tasks, which is now fully deployed
online and serving in Alipay’s mobile application.

Figure 1. SR Multi-Domain Foundation Model Architecture

##  2\. Proposed Model

###  2.1. Problem Formulation

Given a set of $K$ search and recommendation tasks $\\{D_{k}\\}^{K}_{k=1}$,
$D_{k}$ denotes the dataset for the $k$-th task. We let
$\mathcal{U}=\\{u_{1},u_{2},…,u_{N}\\}$ denote the user set,
$\mathcal{I}=\\{i_{1},i_{2},…,i_{M}\\}$ denote the item set and
$\mathcal{Q}=\\{q_{1},q_{2},...,q_{T}\\}$ denote the search query set. In
real-world scenarios, items in search and recommendation usually come from
different domains and are heterogeneous. Some items are shared across multiple
domains and some items belong to each specific domain. And we let
$\mathcal{I}=\mathcal{I}_{1}\cup\mathcal{I}_{2}\cup…\cup\mathcal{I}_{K}$
denote the union of all items in $K$ domains, which contains $M$ items in
total. We aim to jointly train a search and recommendation (S&R) foundation
model $M^{S\&R}_{Foundation}$ in the multi-task setting and predict the
probability of user $u_{l}$ click the item $i_{l}$ given input query $q_{l}$
as $p(y^{ctr}_{l}=1|u_{l},q_{l},i_{l})$. And for search scenarios, additional
query-item relevance score is also predicted as
$p(y^{sim}_{l}=1|q_{l},i_{l})$. For cold start of a new search or
recommendation scenario $D^{*}$, we restore parameters of embedding tables and
partial network structures from the pretrained S&R foundation model
$M^{S\&R}_{Foundation}$, and then apply supervised fine-tuning on the
downstream tasks, such as click through rate (CTR) prediction, query-item
relevance prediction, etc. For the search task $D^{S}_{k}$, we let
$D^{S}_{k}=\\{x_{l}=(u_{l},q_{l},i_{l}),y_{l}\\}_{l}$, which denotes the
search ranking task given the triple input of (user, query, item) as
$(u_{l},q_{l},i_{l})$. For the recommendation task $D^{R}_{k}$, we set search
query set Q as emptyset $\emptyset$ in
$D^{R}_{k}=\\{x_{l}=(u_{l},q_{l}=\emptyset,i_{l}),y_{l}\\}_{l}$.

###  2.2. S&R Multi-Domain Foundation Model

As illustrated in Figure 1, the S&R Multi-Domain Foundation model has three
main components: the User-Query-Item encoding module, the Aspect Gating Fusion
module, and the Domain-Adaptive Multi-Task module. Firstly, raw features of
user, query and item pass through the embedding layers, and we extract the ID
embedding, token-level text embedding and sparse features’ embedding. We apply
LLM to extract domain-invariant text features of query and item towers, which
minimize the divergence of features’ distribution cross multiple domains.
Secondly, the Aspect Gating Fusion module is designed to merge different
groups of ID, text, sparse features’ embedding. The fusion network is to
balance the relative importance of ID, text, and sparse features. Very few
training samples contain ID features of cold start items and can’t represent
them well, and generic text features play more important role. Finally, we
feed the concatenated embedding of user, query and item towers to the Domain
Adaptive MTL module. The module has two outputs representing the click through
rate (CTR) prediction task and the query-item relevance prediction task. The
final loss function is the sum of CTR prediction loss $\mathcal{L}^{ctr}$,
relevance prediction loss $\mathcal{L}^{sim}$ and domain adaptive
regularization $\mathcal{L}^{reg}$.

####  2.2.1. User Query and Item Encoding

We extract three towers for user, query and item respectively. For the user
tower, $e_{u}^{ID}\in\mathbb{R}^{D}$ denotes user id embedding.
$e_{u}^{N_{H}}=[x_{1},...,x_{s},…,x_{N_{H}}]$ denotes the unified sequence of
both search and recommendation clicks in chronological order. Each behavior
$x_{s}$ is encoded as multiple layers of MLPs with inputs of ID feature,
sparse feature of behavior type S or R, and other sparse features of
attributes, $x_{s}=FC(e^{ID}_{s}\oplus e^{type}_{s}\oplus e^{attr}_{s})$. For
the query ($Q$) and item ($I$) features, we extract both domain-invariant text
features, such as tokens in search query and items’ title, and the domain-
specific sparse features. The tokens of $Q$ and $I$ go through the same
tokenizer and we get the tokenized id sequences as integer tensors
$e^{Token}_{q}$ and $e^{Token}_{i}$.
$e^{Token}_{q}=[e^{1}_{q},e^{2}_{q},…,e^{L_{q}}_{q}]\in\mathbb{R}^{L_{q}\times
D}$ denotes the query’s tokenized id tensor of length $L_{q}$, and
$e^{Token}_{i}=[e^{1}_{i},e^{2}_{i},…,e^{L_{i}}_{i}]\in\mathbb{R}^{L_{i}\times
D}$ denotes the item’s tokenized id tensor of length $L_{i}$. For ID feature,
we also embed the search query as ID feature $e^{ID}_{q}\in\mathbb{R}^{D}$,
and item ID as $e^{ID}_{i}\in\mathbb{R}^{D}$. For the sparse features, we
embed sparse features of $Q$ as $e^{S}_{q}$ and sparse features of $I$ as
$e^{S}_{i}$. Finally, we get the feature groups of query tower as
$e_{q}=[e_{q}^{ID},e_{q}^{Token},e_{q}^{S}]$ and the feature groups of item
tower as $e_{i}=[e_{i}^{ID},e_{i}^{Token},e_{i}^{S}]$.

LLM as Domain-Invariant Feature Extractor

We apply the pretrained Large Language Model, such as BERT (Devlin et al.,
2019), GPT (Brown et al., 2020), ChatGLM (Zeng et al., 2022; Du et al., 2022),
to extract domain-invariant text features on both query tower and item tower,
represented as
$\phi_{lm}(Q)=\phi_{lm}(e^{Token}_{q})\in\mathbb{R}^{L_{q}\times D}$ and
$\phi_{lm}(I)=\phi_{lm}(e^{Token}_{i})\in\mathbb{R}^{L_{i}\times D}$. After
mean pooling of the encoding layer, followed by shared linear projection, we
get the domain-invariant text representation of query and item as
$E_{lm}(Q)=W_{lm}\times\text{MEAN}(\phi_{lm}(e^{Token}_{q}))\in
R^{H},E_{lm}(I)=W_{lm}\times\text{MEAN}(\phi_{lm}(e^{Token}_{i}))\in R^{H}$.
$W_{lm}\in\mathbb{R}^{H\times D}$ denotes the linear projection layer shared
between query tower and item tower, $H$ denotes the hidden size of the learned
representations. The language models’ representation is useful for cold start
scenarios, especially when we have few training samples to update the ID
feature of new item $i^{*}$ and new search query $q^{*}$. We also apply linear
projections $W^{q}_{ID},W^{i}_{ID}\in\mathbb{R}^{H\times D}$ to ID feature of
query and item tower, and get the ID representation of query and item as
$E_{ID}(Q),E_{ID}(I)\in\mathbb{R}^{H}$. For the sparse features we have
separate network (usually multiple layers of MLPs) to encode query and item as
$E_{S}(Q),E_{S}(I)\in\mathbb{R}^{H}$. Finally, we get the feature groups of
query tower as $[E_{ID}(Q),E_{lm}(Q),E_{S}(Q)]$ and item tower as
$[E_{ID}(I),E_{lm}(I),E_{S}(I)]$.

####  2.2.2. Aspect Gating Fusion

After low level networks $L_{0}$ (embedding tables) and $L_{1}$ (feature
encoding layers) in Figure 1, we fuse different aspects of query and item as
in literature (Kong et al., 2022). Each aspect $E_{a}$ represents some fine-
grained properties of query and item, such as ID, text and sparse features.
$\mathcal{A}$ denotes the set of aspects we extract from query and item. In
S&R scenarios, we set $|\mathcal{A}|=3$ as ID, text and sparse attributes.
Final representations are fused as weighted sum of different aspects’
representations.

$E(Q)=\sum_{a}w_{a}(Q)E_{a}(Q),E(I)=\sum_{a}w_{a}(I)E_{a}(I)\quad\forall
a\in|\mathcal{A}|$

The weight vector $w(Q),w(I)\in\mathbb{R}^{|\mathcal{A}|}$ are outputs of a
gating network, and we have different strategies to design the network.

  * •

Mean-Gating Strategy Simply mean pooling of different aspects of query and
item features as $w_{a}=\frac{1}{|\mathcal{A}|}$.

  * •

[CLS]-Gating Strategy We use randomly initialized embedding
$E_{CLS}(Q)$,$E_{CLS}(I)\in\mathbb{R}^{H}$ to represent classification token
[CLS] of query and item respectively.

$w_{a}=\frac{e^{E_{CLS}E_{a}}}{\sum_{a\in|\mathcal{A}|}e^{E_{CLS}E_{a}}}\in\mathbb{R}^{|\mathcal{A}|}$

.

  * •

Domain-Gating Strategy

We design the domain gating strategy from the intuition that the fusion
network has different weights when merging different aspects of query and
item. To model the differences across domains, we randomly initialize the
domain embedding
$E_{D}=[E_{D_{1}},E_{D_{2}},...,E_{D_{K}}]\in\mathbb{R}^{K\times H}$ as the
representations of different domains. And the domain-specific gating is
calculated as

$\\\
w_{a}=\frac{e^{E_{D_{k}}E_{a}}}{\sum_{a\in|\mathcal{A}|}e^{E_{D_{k}}E_{a}}}\in\mathbb{R}^{|\mathcal{A}|}$

.

####  2.2.3. Domain Adaptive Multi-Task Learning

The input to the Domain Adaptive Multi-Task module is the concatenation of
representations of user, query and item towers as $\mathbb{x}=E(U)\oplus
E(Q)\oplus E(I)$. For multi-domain setting, a series of multi-task and multi-
domain models are proposed, such as SharedBottom(Caruana, 1997), MMoE(Ma et
al., 2018), PLE(Tang et al., 2020), STAR(Sheng et al., 2021), SAMD(Huan et
al., 2023), etc. These models use shared structures (Experts or MLP layers) to
model the similarity among different tasks or domains, and use individual
structures to learn the domain-specific properties. The difficulty of training
the multi-domain models is the domain shift phenomena. For the k-th domain
$D_{k}$, the marginal distribution of input feature $p(\mathbb{x}_{k})$ and
the conditional distribution of predicting output $y_{k}$ as
$p(y_{k}|\mathbb{x}_{k})$ has divergence from other domains. The well studied
MTL models handle the divergence of conditional distribution. We propose to
add a Domain Adaptive Layer to the input features $\mathbb{x}_{i}$, which maps
the inputs from multiple domains to a common vector space. We reuse the
randomly initialized domain embedding
$E_{D}=[E_{D_{1}},E_{D_{2}},...,E_{D_{K}}]\in\mathbb{R}^{K\times H}$ in
section • ‣ 2.2.2 and concatenate the domain embedding $E_{D_{k}}$ to feature
vector $\mathbb{x}_{i}$ of instances from the k-th domain $D_{k}$, followed by
domain-specific linear transformation $W_{k}$. Suppose $\mathbb{x}_{i}$ and
$\mathbb{x}_{j}$ denote two instances from different domains in the same
training batch, we can get the domain-adaptive representation
$\hat{\mathbb{x}}_{i},\hat{\mathbb{x}}_{j}$ as

$\hat{\mathbb{x}}_{i}=W_{i}(\mathbb{x}_{i}\oplus
E_{D_{i}}),\hat{\mathbb{x}}_{j}=W_{j}(\mathbb{x}_{j}\oplus E_{D_{j}})$

We apply domain adaptation (Ganin et al., 2016) techniques to constrain the
divergence of distributions from domains $i$ and $j$ as
$p(\hat{\mathbb{x}}_{i})$ and $p(\hat{\mathbb{x}}_{j})$ as
$\mathcal{L}^{reg}=\sum_{i,j\in\\{1,2,...,K\\}}d(p(\hat{\mathbb{x}}_{i})||p(\hat{\mathbb{x}}_{j}))$.
In terms of divergence measurement, we compared different metrics such as
Jensen-Shannon Divergence (symmetric KL Divergence), Maximum Mean Discrepancy
(MMD) (Gretton et al., 2012) in the experiment section. And we find the
Jensen-Shannon Divergence achieves the best performance as

$\mathcal{L}^{reg}=\sum_{i,j\in\\{1,2,...,K\\}}\text{JS}(p(\hat{\mathbb{x}}_{i})||p(\hat{\mathbb{x}}_{j}))$

.

Finally, on top of the Domain Adaptive Layer we stack the standard Multi-Task
module, such as MMoE to extract outputs and predict two objectives, CTR
prediction $y^{ctr}$ and query-item relevance prediction $y^{sim}$.

CTR Prediction Click-Through Rate (CTR) Prediction is a common task in both
search and recommendation scenarios. We apply a unified scoring function
$y^{ctr}_{l}=f_{\theta}(u_{l},q_{l},i_{l})$ in the S&R foundation framework to
predict CTR with the triple inputs of user, item and query as $(u,q,i)$. For
search tasks, users have explicit search query $q$. And for recommendation
tasks users don’t have explicit intentions. So we set $q=\emptyset$ as the
default embedding in the unified scoring function.

Query-Item Relevance Prediction Query-Item Relevance Prediction is a common
task in search scenarios, which predicts the relevance score of query-item
pair of $(q,i)$ and train a function $y^{sim}_{l}=f_{\phi}(q_{l},i_{l})$ to
represent query-item pair’s relevance score. The relevance prediction is
usually a classification task.

####  2.2.4. Loss of S&R Foundation model

We train the S&R foundation model in multi-domain multi-task settings, using
datasets from $K$ domains. Each domain calculates either or both of two
objectives of CTR prediction $y^{ctr}_{l}=f_{\theta}(u_{l},q_{l},i_{l})$ and
relevance prediction $y^{sim}_{l}=f_{\phi}(q_{l},i_{l})$, depending on whether
the task is search or recommendation. The final objective function consists of
three parts, the loss for CTR prediction $\mathcal{L}^{ctr}$, the loss for
relevance prediction $\mathcal{L}^{sim}$, and the loss for domain adaptive
regularizer $\mathcal{L}^{reg}$.

$\mathcal{L}=\mathcal{L}^{ctr}+\mathcal{L}^{sim}+\mathcal{L}^{reg}$

$\mathcal{L}^{ctr}=\sum_{k\in K}\sum_{l\in
N^{ctr}_{k}}\mathcal{L}_{ce}(f_{\theta}(u_{l},q_{l},i_{l});y^{ctr}_{l})$

$\mathcal{L}^{sim}=\sum_{k\in K}\sum_{l\in
N^{sim}_{k}}\mathcal{L}_{ce}(f_{\phi}(q_{l},i_{l});y^{sim}_{l})$

###  2.3. Supervised Fine-Tuning Downstream Tasks

The pretrained S&R foundation model can benefit downstream tasks in the
pretrain-finetune manner. The downstream model restores parameters from the
foundation model, freezes part of the parameters and finetunes the remaining
layers. We experiment different ways of freeze-finetune split. Firstly, the
freeze-finetune split is between level $L_{0}$ and $L_{1}$ as in Figure 1. The
pretrained embedding in level $L_{0}$ is freezed and the remaining layers from
$L_{1}$ to $L_{n}$ are finetuned. Secondly, the freeze-finetune split is
between level $L_{1}$ and $L_{2}$. The embedding in level $L_{0}$ as well as
the parameters of encoding layers in level $L_{1}$ are freezed, and the
parameters from level $L_{2}$ to $L_{n}$ are finetuned. Given dataset of new
downstream task $D^{*}=\\{(u^{*}_{l},q^{*}_{l},i^{*}_{l}),y^{*}_{l}\\}$, the
domain embedding $E_{D^{*}}\in\mathbb{R}^{H}$ is randomly initialized and
finetuned. In the experiment section, we thoroughly tested the performance of
different ways of freeze-finetune split. We also compared the performance of
pretrain-finetuning S&R Foundation model $M^{S\&R}_{Foundation}$ with the
performance of training single domain model without transfer learning.

##  3\. Experiment

To test the effectiveness of our proposed S&R Multi-Domain Foundation model,
we want to answer the following questions:

  * •

RQ1: Whether our joint S&R Multi-Domain Foundation model can achieve SOTA
performance compared to other multi-domain and multi-task models?

  * •

RQ2: In terms of query and item towers’ representations, what’s the
performance of the domain-invariant text features extracted by LLM and Aspect
Gating Fusion network compared to other methods?

  * •

RQ3: Whether S&R Multi-Domain Foundation and Supervised Finetuning can help
benefit cold start scenarios?

Table 1. Statistics of Alipay Search Ranking and Query Recommendation Datasets. ID | Dataset | S/R | Train | Eval | Test | #Query | #Item
---|---|---|---|---|---|---|---
Task 1 | Query-Item Relevance Prediction | S | 76.2M | 12.7M | 12.7M | 40K | 40K
Task 2 | Query Suggest CTR Prediction | S/R | 145.4M | 23.5M | 23.5M | 0.84M | 0.16M
Task 3 | Background Word Query Recommendation CTR Prediction | R | 146.2M | 24.3M | 24.3M | - | 65K
Task 4 | Content Query Recommendation CTR Prediction | R | 0.76M | 0.09M | 0.09M | - | 4.6K
Task 5 | People Also Ask DeepSuggest | S/R | 2.4M | 0.38M | 0.38M | 0.41M | 25K
Task 6 | Service Card Recommendation | S/R | 1.01M | 0.17M | 0.17M | 1.3K | 1.6K
Task 7 | Content Search Ranking | S | 6.13M | 1.03M | 1.03M | 0.27M | 0.14M
Table 2. Performance of S&R Multi-Domain Foundation Model. Method | Task1 | Task2 | Task3 | Task4 | Task5 | Task6 | Task7
---|---|---|---|---|---|---|---
S&R Multi-Domain Shared Bottom (Caruana, 1997) | 0.6483 | 0.8993 | 0.7829 | 0.6575 | 0.8511 | 0.8015 | 0.8561
S&R Multi-Domain MMoE (Ma et al., 2018) | 0.6482 | *0.9003 | 0.7812 | 0.6650 | 0.8463 | 0.7942 | 0.8599
S&R Multi-Domain PLE (Tang et al., 2020) | *0.7006 | 0.8981 | 0.7815 | 0.6682 | 0.8487 | 0.7978 | 0.8620
S&R Multi-Domain Foundation (MLP) | 0.6827 | 0.8974 | 0.7784 | 0.6683 | 0.8462 | 0.7926 | 0.8629
S&R Multi-Domain Foundation-MMoE-DA-MMD | 0.6874 | 0.8942 | *0.7971 | 0.6793 | 0.8564 | 0.8203 | 0.8569
S&R Multi-Domain Foundation-MMoE-DA-JS | 0.6942 | 0.8973 | 0.7912 | *0.6979 | *0.8703 | *0.8312 | *0.8692
Absolute Improvement | +0.0459 | -0.0020 | +0.0083 | +0.0404 | +0.0192 | +0.0297 | +0.0131
Table 3. Comparison of Query and Item Token Encoding Methods after Fine-tuning Task 4.  ID | Token Embedding | Query/Item Encoder | Finetune | AUC
---|---|---|---|---
1 | Baseline: Without Token Emb | - | - | 0.7524
2 | Randomly Initialized | Mean Pooling | - | 0.7551
3 | Randomly Initialized | Transfomer(L=1) | True | 0.7544
4 | Randomly Initialized | Transfomer(L=6) | True | 0.7559
5 | SR Foundation (LM=Transformer) | Transfomer(L=1) |  $L_{0},L_{1}$:True | 0.7562
6 | SR Foundation (LM=Transformer) | Transfomer(L=1) |  $L_{0}$:False,$L_{1}$:True | 0.7531
7 | SR Foundation (LM=Transformer) | Transfomer(L=1) |  $L_{0},L_{1}$:False | 0.7574
8 | SR Foundation (LM=BERT) | BERT BASE(L=12) | True | 0.7563
9 | SR Foundation (LM=BERT) | BERT BASE(L=12) | False | *0.7580
10 | SR Foundation (LM=ChatGLM 6B) | ChatGLM 6B Pretrained LLM (Zeng et al., 2022; Du et al., 2022) | False | 0.7518
11 | SR Foundation (LM=ChatGLM 6B) | ChatGLM 6B Pretrained LLM (Zeng et al., 2022; Du et al., 2022) \+ prompt | False | 0.7503
12 | SR Foundation (LM=ChatGLM2 6B) | ChatGLM2 Pretrained LLM (Zeng et al., 2022; Du et al., 2022) | False | 0.7502
| Absolute Improvement | - | - | +0.0056
Table 4. Comparison of Aspect Gating Fusion on Task 4. Method | AUC | Absolute Gain
---|---|---
Mean-Pooling | 0.7385 | -
[CLS]-Gating | 0.7515 | +0.0130
Domain-Gating | *0.7524 | +0.0139
Table 5. Comparison of Cold Start Scenarios Task 4 and 6. | Service Card Rec | Content Query Rec
---|---|---
Single Domain | 0.8229 | 0.7295
SR Fdt-¿Finetune | 0.8446 | 0.7574
Absolute Improvement | +0.0216 | +0.0279
Figure 2. Visualization of SR Foundation Model’s Domain-Adaptive Layers Figure
3. Online AB Testing PVCTR Performance of Service Card Recommendation.

###  3.1. Experimental Settings

####  3.1.1. Dataset

We conducted extensive experiments of S&R Foundation model on real-world
datasets, including 7 industrial datasets of Alipay Search Ranking and Query
Recommendation. The statistics are summarized in table 1. $S$ denotes the
search dataset, in which users have explicit search query, such as Query-Item
Relevance Prediction, Content Search Ranking, etc. And $R$ denotes the
recommendation dataset, in which users don’t have explicit intent of search
query. There are also some tasks between Search and Recommendation, which we
classify as S/R, such as Query Suggest CTR Prediction, in which users have
explicit query, and at the same time the task is a CTR prediction task to make
recommendation of query suggestions to users.

####  3.1.2. Comparison Methods

S&R Foundation Model We compared our proposed S&R Multi-Domain Foundation
model with SOTA multi-domain and multi-task models, such as Shared Bottom MTL
(Caruana, 1997), Multi-Gate Mixture of Experts (MMoE) (Ma et al., 2018), PLE
(Tang et al., 2020), etc. For ablation study, we designed separate experiments
to evaluate different modules of the framework, including the User-Query-Item
encoding module, Aspect Gating Fusion module and Domain Adaptive Multi Task
module. The experiment of S&R Multi-Domain Foundation (MLP) denotes the
concatenated user-query-item representations are followed by multiple MLP
layers. And the experiment of S&R Multi-Domain Foundation-MMoE-DA-JS denotes
the representations are followed by a Domain Adaptive Layer (JS-Divergence)
and MMoE multi-task module.

Domain-Invariant Text Features and Aspect Gating Fusion To prove the
effectiveness of adding domain-invariant text features in S&R Foundation
model, we have conducted experiments and ablation studies on different query
and item token encoding methods on Alipay Content Query Recommendation dataset
of tasks 4 in table 1. In the baseline method, we intentionally leave out the
token-embedding of text features and only use ID and sparse features. We also
compared randomly initialized token embedding with embedding restored from the
pretrained S&R foundation model under different configurations. For the
encoders, we compared mean pooling, randomly initialized Transformer, BERT,
ChatGLM-6B(Zeng et al., 2022; Du et al., 2022), and ChatGLM+prompt, etc. In
methods 10-12, we adopt ChatGLM-6B and ChatGLM2-6B to encode the text features
of query and items. The implementation details are: we utilized the encoders
of ChatGLM-6B and ChatGLM2-6B to convert the input text features and
corresponding prompts into 4096-dimensional vectors, which are followed by 2
MLP dense layers and further reduced to 32-dimensional vectors. The prompt
function used in our approach is defined as $f_{prompt}(X)="\text{Extract
keywords from sentence [X]}"$. To compare different Aspect Gating Fusion
methods, e.g. Mean-Pooling, [CLS]-Gating, Domain-Gating, we conducted ablation
studies and the results are listed in table 4.

Supervised Fine-Tuning on Cold Start Scenarios For cold start scenarios, we
compared the performance of supervised fine-tuning (SFT) the foundation model
using downstream dataset, with the method of training single domain model on
several tasks, including Service Card Recommendation (task 6) and Content
Query Recommendation (task 4) as in table 5.

###  3.2. Experimental Results

####  3.2.1. S&R Multi-Domain Foundation model

To compare the performance of different multi-domain models, we report AUC
performance on 7 search and recommendation datasets in table 2. All the
experimented models share same input features, User-Query-Item Encoding
module, and Domain-Gating as Aspect Gating Fusion strategy. The baseline for
the multi-task learning (MTL) module is the shared bottom model. MMoE-DA-MMD
and MMoE-DA-JS represent models that utilize Maximum Mean Discrepancy (MMD)
and Jensen–Shannon Divergence (JS-Divergence) to constrain the distributions
of domain adaptive layers respectively. The asterisk (*) denotes the best
performance achieved in each task, and the absolute improvement represents the
absolute improvement of MMoE-DA-JS method compared to baseline. MMoE-DA-JS
achieved best performance on 4 tasks: 4, 5, 6, 7 with AUC improvement of
+0.0404, +0.0192, +0.0297, +0.0131 respectively. The domain-adaptive layer
constrains the embedding representations from different domains in the common
vector space. The t-SNE visualization of S&R Foundation model’s domain-
adaptive layers is depicted in Figure 2. The embedding depicted in the first
subplot ”S&R Foundation MLP” is scattered, and the embedding in the third
subplot ”S&R Foundation-MMoE-DA-JS” is coherently aligned.

####  3.2.2. Domain-Invariant Text Features and Aspect Gating Fusion

We report the performance of different methods to encode domain-invariant text
features and freeze-finetune split in table 3 on task 4 Content Query
Recommendation. Our proposed method of restoring pretrained parameters from
BERT BASE (12 layers Transformer) in S&R Foundation, freezing the parameters
of the encoder and finetuning the remaining networks achieves the best AUC
performance 0.7580, which is 0.0056 absolute gain over baseline model.
Comparing different freeze-finetune split (methods 5-7), we can see that
freezing pretrained parameters in level $L_{0}$ and $L_{1}$ (method 7)
achieves better performance than other split methods (method 5/6), which is
0.0043 absolute gain in AUC. As for the ablation studies of Aspect Gating
Fusion in table 4, the baseline is to simply mean pooling three aspects: ID,
text and sparse features. We can see the Domain-Gating achieves best AUC
performance 0.7524, which is 0.0139 absolute gain over mean-pooling method.

####  3.2.3. Supervised Finetuning in Cold Start Scenarios

To prove the effectiveness of finetuning our pretrained S&R Foundation model,
we compared cold start performance of two scenarios, Service Card
Recommendation (task 6) and Content Query Recommendation (task 4). They are
new scenarios and we only collected a few samples in a short period of time.
The samples are splitted as we leave out last one day’s collected data for
testing, and use the remaining data for fine-tuning the S&R Foundation. We
also train the single domain model as the baseline. From table 5, we can see
the fine-tuned S&R Foundation model achieves +0.0216 AUC improvement over
single domain model on task 6 and +0.0279 AUC improvement on task 4.

####  3.2.4. Online AB Testing

To further prove the effectiveness of online performance in cold start
scenario, we deployed the fine-tuned S&R Foundation model online in Service
Card Recommendation scenario, and compared with baseline, which is the single
domain DNN model. The results of the AB Testing from day 1 to day 7 are
depicted in Figure 3. The key performance measurement of the cold start
scenario is PVCTR (Page View Click Through Rate). And we observed that the
fine-tuned S&R Foundation model achieved +17.54% relative gain in PVCTR over
baseline. The online AB Testing results showed that our method achieved better
performance than baseline consistently in cold start scenario.

##  4\. Conclusion

In this paper, we study the problem of training search and recommendation
tasks jointly as the S&R Multi-Domain Foundation model, and use domain
adaptation techniques to benefit cold start scenario. Our proposed model
learns user, query and item representations, applies LLM to encode domain
invariant text features and Aspect Gating Fusion to merge ID, text and sparse
features. We also conducted extensive experiments on finetuning the foundation
models in cold start scenarios, which achieves better performance than the
single domain model. The fine-tuned S&R Multi-Domain Foundation model has been
successfully deployed online in Alipay’s multiple search and recommendation
scenarios.

## References

  * (1)
  * Ai et al. (2017) Qingyao Ai, Yongfeng Zhang, Keping Bi, Xu Chen, and W. Bruce Croft. 2017.  Learning a Hierarchical Embedding Model for Personalized Product Search. In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Shinjuku, Tokyo, Japan) _(SIGIR ’17)_. Association for Computing Machinery, New York, NY, USA, 645–654.  https://doi.org/10.1145/3077136.3080813
  * 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. In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.).
  * Caruana (1997) Rich Caruana. 1997\.  Multitask Learning.  _Mach. Learn._ 28, 1 (1997), 41–75.
  * Cui et al. (2022a) Zeyu Cui, Jianxin Ma, Chang Zhou, Jingren Zhou, and Hongxia Yang. 2022a.  M6-Rec: Generative Pretrained Language Models are Open-Ended Recommender Systems.  _CoRR_ abs/2205.08084 (2022).
  * Cui et al. (2022b) Zeyu Cui, Jianxin Ma, Chang Zhou, Jingren Zhou, and Hongxia Yang. 2022b.  M6-Rec: Generative Pretrained Language Models are Open-Ended Recommender Systems.  arXiv:2205.08084 [cs.IR]
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , Jill Burstein, Christy Doran, and Thamar Solorio (Eds.). Association for Computational Linguistics, 4171–4186.
  * Ding et al. (2019) Xichen Ding, Jie Tang, Tracy Liu, Cheng Xu, Yaping Zhang, Feng Shi, Qixia Jiang, and Dan Shen. 2019\.  Infer Implicit Contexts in Real-Time Online-to-Offline Recommendation. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining_ (Anchorage, AK, USA) _(KDD ’19)_. Association for Computing Machinery, New York, NY, USA, 2336–2346.  https://doi.org/10.1145/3292500.3330716
  * Du et al. (2022) Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang. 2022.  GLM: General Language Model Pretraining with Autoregressive Blank Infilling. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. 320–335.
  * Ganin et al. (2016) Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. 2016\.  Domain-Adversarial Training of Neural Networks.  _J. Mach. Learn. Res._ 17, 1 (jan 2016), 2096–2030.
  * Gretton et al. (2012) Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. 2012\.  A Kernel Two-Sample Test.  _J. Mach. Learn. Res._ 13, null (mar 2012), 723–773.
  * Huan et al. (2023) Zhaoxin Huan, Ang Li, Xiaolu Zhang, Xu Min, Jieyu Yang, Yong He, and Jun Zhou. 2023.  SAMD: An Industrial Framework for Heterogeneous Multi-Scenario Recommendation. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ (Long Beach, CA, USA) _(KDD ’23)_. Association for Computing Machinery, New York, NY, USA, 4175–4184.  https://doi.org/10.1145/3580305.3599955
  * Kong et al. (2022) Weize Kong, Swaraj Khadanga, Cheng Li, Shaleen Kumar Gupta, Mingyang Zhang, Wensong Xu, and Michael Bendersky. 2022.  Multi-Aspect Dense Retrieval. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ (Washington DC, USA) _(KDD ’22)_. Association for Computing Machinery, New York, NY, USA, 3178–3186.  https://doi.org/10.1145/3534678.3539137
  * Li et al. (2022) Ningning Li, Qunwei Li, Xichen Ding, Shaohu Chen, and Wenliang Zhong. 2022.  Prototypical Contrastive Learning and Adaptive Interest Selection for Candidate Generation in Recommendations. In _Proceedings of the 31st ACM International Conference on Information and Knowledge Management_ (Atlanta, GA, USA) _(CIKM ’22)_. Association for Computing Machinery, New York, NY, USA, 4183–4187.  https://doi.org/10.1145/3511808.3557674
  * Liu et al. (2022) Jiongnan Liu, Zhicheng Dou, Qiannan Zhu, and Ji-Rong Wen. 2022\.  A Category-Aware Multi-Interest Model for Personalized Product Search. In _Proceedings of the ACM Web Conference 2022_ (Virtual Event, Lyon, France) _(WWW ’22)_. Association for Computing Machinery, New York, NY, USA, 360–368.  https://doi.org/10.1145/3485447.3511964
  * Ma et al. (2018) Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H. Chi. 2018\.  Modeling Task Relationships in Multi-task Learning with Multi-gate Mixture-of-Experts. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018_. ACM, 1930–1939.
  * Sheng et al. (2021) Xiang-Rong Sheng, Liqin Zhao, Guorui Zhou, Xinyao Ding, Binding Dai, Qiang Luo, Siran Yang, Jingshan Lv, Chi Zhang, Hongbo Deng, and Xiaoqiang Zhu. 2021.  One Model to Serve All: Star Topology Adaptive Recommender for Multi-Domain CTR Prediction. In _CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 - 5, 2021_ , Gianluca Demartini, Guido Zuccon, J. Shane Culpepper, Zi Huang, and Hanghang Tong (Eds.). ACM, 4104–4113.
  * Si et al. (2022) Zihua Si, Xueran Han, Xiao Zhang, Jun Xu, Yue Yin, Yang Song, and Ji-Rong Wen. 2022\.  A Model-Agnostic Causal Learning Framework for Recommendation Using Search Data. In _Proceedings of the ACM Web Conference 2022_ (Virtual Event, Lyon, France) _(WWW ’22)_. Association for Computing Machinery, New York, NY, USA, 224–233.  https://doi.org/10.1145/3485447.3511951
  * Si et al. (2023) Zihua Si, Zhongxiang Sun, Xiao Zhang, Jun Xu, Xiaoxue Zang, Yang Song, Kun Gai, and Ji-Rong Wen. 2023\.  When Search Meets Recommendation: Learning Disentangled Search Representation for Recommendation. In _Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Taipei, Taiwan) _(SIGIR ’23)_. Association for Computing Machinery, New York, NY, USA, 1313–1323.  https://doi.org/10.1145/3539618.3591786
  * Tang et al. (2020) Hongyan Tang, Junning Liu, Ming Zhao, and Xudong Gong. 2020\.  Progressive Layered Extraction (PLE): A Novel Multi-Task Learning (MTL) Model for Personalized Recommendations. In _RecSys 2020: Fourteenth ACM Conference on Recommender Systems, Virtual Event, Brazil, September 22-26, 2020_. ACM, 269–278.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023.  LLaMA: Open and Efficient Foundation Language Models.  _CoRR_ abs/2302.13971 (2023).
  * Xu et al. (2018) Jun Xu, Xiangnan He, and Hang Li. 2018.  Deep Learning for Matching in Search and Recommendation. In _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_ (Ann Arbor, MI, USA) _(SIGIR ’18)_. Association for Computing Machinery, New York, NY, USA, 1365–1368.  https://doi.org/10.1145/3209978.3210181
  * Yao et al. (2021) Jing Yao, Zhicheng Dou, Ruobing Xie, Yanxiong Lu, Zhiping Wang, and Ji-Rong Wen. 2021\.  USER: A Unified Information Search and Recommendation Model Based on Integrated Behavior Sequence. In _Proceedings of the 30th ACM International Conference on Information and Knowledge Management_ (Virtual Event, Queensland, Australia) _(CIKM ’21)_. Association for Computing Machinery, New York, NY, USA, 2373–2382.  https://doi.org/10.1145/3459637.3482489
  * Zamani and Croft (2018) Hamed Zamani and W. Bruce Croft. 2018.  Joint Modeling and Optimization of Search and Recommendation. In _Proceedings of the First Biennial Conference on Design of Experimental Search & Information Retrieval Systems, Bertinoro, Italy, August 28-31, 2018_ _(CEUR Workshop Proceedings, Vol. 2167)_ , Omar Alonso and Gianmaria Silvello (Eds.). CEUR-WS.org, 36–41.
  * Zamani and Croft (2020) Hamed Zamani and W. Bruce Croft. 2020.  Learning a Joint Search and Recommendation Model from User-Item Interactions. In _WSDM ’20: The Thirteenth ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3-7, 2020_ , James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang (Eds.). ACM, 717–725.
  * Zeng et al. (2022) Aohan Zeng, Xiao Liu, Zhengxiao Du, Zihan Wang, Hanyu Lai, Ming Ding, Zhuoyi Yang, Yifan Xu, Wendi Zheng, Xiao Xia, et al. 2022\.  Glm-130b: An open bilingual pre-trained model.  _arXiv preprint arXiv:2210.02414_ (2022).
  * Zhao et al. (2022) Kai Zhao, Yukun Zheng, Tao Zhuang, Xiang Li, and Xiaoyi Zeng. 2022.  Joint Learning of E-Commerce Search and Recommendation with a Unified Graph Neural Network. In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_ (Virtual Event, AZ, USA) _(WSDM ’22)_. Association for Computing Machinery, New York, NY, USA, 1461–1469.  https://doi.org/10.1145/3488560.3498414
  * Zhao et al. (2023) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, Peiyu Liu, Jian-Yun Nie, and Ji-Rong Wen. 2023\.  A Survey of Large Language Models.  _CoRR_ abs/2303.18223 (2023).


11institutetext: Chongqing Institute of Green and Intelligent Technology,
Chinese Academy of Sciences, Chongqing, China 22institutetext: Department of
Applied Mathematics, Western University, Canada

# SHORT-MT: Optimal Solution of Linear Ordinary Differential Equations by
Conjugate Gradient Method††thanks: Supported by NSFC 11471307 and CAS Research
Program of Frontier Sciences (QYZDB-SSW-SYS026).

Wenqiang Yang 11 Wenyuan Wu Corresponding author: .11<EMAIL_ADDRESS>Robert M. Corless 22

###### Abstract

Solving initial value problems and boundary value problems of Linear Ordinary
Differential Equations (ODEs) plays an important role in many applications.
There are various numerical methods and solvers to obtain approximate
solutions represented by points. However, few work about optimal solution to
minimize the residual can be found in the literatures. In this paper, we first
use Hermit cubic spline interpolation at mesh points to represent the
solution, then we define the residual error as the $L_{2}$ norm of the
residual obtained by substituting the interpolation solution back to ODEs.
Thus, solving ODEs is reduced to an optimization problem in curtain solution
space which can be solved by conjugate gradient method with taking advantages
of sparsity of the corresponding matrix. The examples of IVP and BVP in the
paper show that this method can find a solution with smaller global error
without additional mesh points.

###### Keywords:

ODEs global error Hermit cubic spline optimization problem conjugate gradient
method.

##  1 Introduction

Differential equations (DEs) are one of the most fundamental tools in physical
world to model the dynamics of a system. In machine learning, we may model the
learner as some dynamical system, for example a neural network with weights
changing according to certain rules. For example, the continuous time
recurrent neural network using a system of ODE to simulate the effects on a
neuron of the incoming spike train works successfully in evolutionary
robotics. Spiking neural networks as third generation of neural network
increase the level of realism in a neural simulation where the neural voltage
is usually described as DEs.

Interestingly, people also exploit reversely a variety of neural network
methods for solving DEs arising in science and engineering [14]. In this
paper, starting with the most fundamental case: linear ODE, we attempt to
study the optimal solution first by symbolic transformation to an optimization
problem and then attain the solution by numerical methods.

The standard from of a Linear ODEs is

${\bm{x}}^{\prime}={\bm{A}}(t)\cdot{\bm{x}}(t)+{\bm{q}}(t)$ (1)

Where ${\bm{x}}={\bm{x}}(t):\mathbb{R}\rightarrow\mathbb{R}^{n}$ is vector of
solutions as a function time, the $n\times n$ matrix ${\bm{A}}(t)$ is the
state matrix, the $n$ dimensional vector ${\bm{q}}(t)$ corresponds to the
inhomogeneous part of the system.

Such ODE often appearing in numerical modelling and simulation is of great
importance in mechanical engineering and industrial design. Numerical solving
of linear ODE is well studied, especially IVP[12] and BVP[1][10][2] for ODE.
Even a number of efficient solvers have been developed e.g. Matlab. To qualify
and measure the reliability of these solvers without knowing the exact
solution is an important question[13]. A natural choice is to consider the
residual error of the equation after substituting the approximate
solution[9][3][6].

Accuracy of the solution depends on the used discrete mesh. If we fix the mesh
and consider the solution with first-order continuity approximated by degree
$3$ piecewise polynomials. The key question is to look for a solution with
smallest residual error in such solution space which is different from the
goal of [3] to search optimal interpolant with a given numerical solution of
ODE. Our main contribution of this paper is to convert the IVP/BVP of ODEs to
a quadratic programming problem. Moreover, the optimal solution can be
obtained efficiently by the conjugate gradient method since the corresponding
matrix is symmetric and positive definite.

##  2 Preliminaries

###  2.1 Hermite Cubic Spline

For first-order continuity, we apply Hermite cubic spline interpolation to
construct an approximate solution of ODEs [7].

###### Theorem 2.1

Let $\\{t_{0},...,t_{m}\\}$ be a set of knots in the interval $[t_{0},t_{m}]$
with $t_{0}<t_{1}<...<t_{m}$ and $m\geq 2$, there is a unique cubic spline
$\widetilde{x}\in C^{1}[t_{0},t_{m}]$ on the interval $[t_{i},t_{i+1}]$, for
$i=0,...,m-1$ such that

$\widetilde{x}(t_{i})=x_{i},\widetilde{x}^{\prime}(t_{i})=x^{\prime}_{i}$

Let $h_{i}=t_{i+1}-t_{i}$, and $\tau=(t-t_{i})/h_{i}$, $\tau\in[0,1]$, then
writing the spline $\widetilde{x}$ as

$\widetilde{x}_{i}(\tau)=\alpha_{0}(\tau)\cdot
x_{i-1}+h_{i}\alpha_{1}(\tau)\cdot x^{\prime}_{i-1}+\beta_{0}(\tau)\cdot
x_{i}+h_{i}\beta_{1}(\tau)\cdot x^{\prime}_{i}$

Where $\alpha_{0}(\tau)=2\tau^{3}-3\tau^{2}+1$,
$\alpha_{1}(\tau)=\tau^{3}-2\tau^{2}+\tau$,
$\beta_{0}(\tau)=-2\tau^{3}+3\tau^{2}$, $\beta_{1}(\tau)=\tau^{3}-\tau^{2}$.

###  2.2 Residual and Forward Error

To evaluate the accuracy of this solution, here we first define the residual
and forward error which is introduced in [13]. More detailed study about the
error analysis can be found in the book [3].

###### Definition 1

Let $n$-dimensional vector $\widetilde{{\bm{x}}}(t)\in C^{1}[t_{0},t_{m}]$ be
approximate solution of Eq.(1). Then its residual is defined to be

${\bm{\delta}}(t)=\widetilde{{\bm{x}}}^{\prime}(t)-{\bm{A}}(t)\cdot\widetilde{{\bm{x}}}(t)-{\bm{q}}(t)$
(2)

The residual of $C^{1}$ solution is also called defect in [3].

The $L_{2}$ norm of the residual

$\sqrt{\int_{t_{0}}^{t_{m}}\delta(t)^{T}\delta(t)dt}$

is called the residual error.

Let $n$-dimensional vector ${\bm{x}}^{*}(t)$ be the exact solutions of linear
ordinary system Eq.(1), such that

$({\bm{x}}^{*})^{\prime}={\bm{A}}(t)\cdot{\bm{x}}^{*}+{\bm{q}}(t)$ (3)

The difference $\Delta{\bm{x}}(t)={\bm{x}}^{*}-\widetilde{{\bm{x}}}$ is called
the forward error.

In addition, we define the $L_{2}$ norm of the forward error

$\sqrt{\int_{t_{0}}^{t_{m}}\Delta{\bm{x}}^{T}\Delta{\bm{x}}\;dt}$

as the global error.

##  3 Optimal Solution

In order to minimize the residual error of ODEs solution on the whole time
interval, we can define an objective function as follow:

$\min\sqrt{\sum\limits_{i=0}^{m-1}\int_{t_{i}}^{t_{i+1}}{\bm{\delta}}_{i}(t)^{T}\cdot{\bm{\delta}}_{i}(t)\;dt}$
(4)

where ${\bm{\delta}}_{i}(t)$ is the residual on the $i$-th time interval.
Recall Theorem 2.1, we can express each ${\bm{\delta}}_{i}(t)$ in terms of
${\bm{x}}_{i}$, ${\bm{x}}^{\prime}_{i}$, ${\bm{x}}_{i+1}$,
${\bm{x}}^{\prime}_{i+1}$ at the mesh points.

We denote the matrices
${\bm{a}}_{i}=\frac{\alpha^{\prime}_{0}}{h_{i}}{\bm{E}}-\alpha_{0}{\bm{A}}$,
${\bm{b}}_{i}=\alpha^{\prime}_{1}{\bm{E}}-h_{i}\alpha_{1}{\bm{A}}$,
${\bm{c}}_{i}=\frac{\beta^{\prime}_{0}}{h_{i}}{\bm{E}}-\beta_{0}{\bm{A}}$ and
${\bm{d}}_{i}=\beta^{\prime}_{1}{\bm{E}}-h_{i}\beta_{1}{\bm{A}}$, where
${\bm{E}}$ is the $n\times n$ identity matrix. Thus,

${\bm{\delta}}_{i}={\bm{a}}_{i}{\bm{x}}_{i}+{\bm{b}}_{i}{\bm{x}}^{\prime}_{i}+{\bm{c}}_{i}{\bm{x}}_{i+1}+{\bm{d}}_{i}{\bm{x}}^{\prime}_{i+1}-{\bm{q}}.$

Additionally, let
$I_{i}=\int_{t_{i}}^{t_{i+1}}{\bm{\delta}}_{i}(t)^{T}\cdot{\bm{\delta}}_{i}(t)\;dt$.
Then we have

$I_{i}={\bm{y}}^{T}_{i}{\bm{F}}_{i}{\bm{y}}_{i}-2{\bm{B}}_{i}^{T}{\bm{y}}_{i}+\int_{t_{i}}^{t_{i+1}}{\bm{q}}^{T}{\bm{q}}dt$
(5)

where
${\bm{F}}_{i}=\int_{t_{i}}^{t_{i+1}}\left(\begin{array}[]{cccc}{\bm{a}}^{T}_{i}{\bm{a}}_{i}&{\bm{a}}^{T}_{i}{\bm{b}}_{i}&{\bm{a}}^{T}_{i}{\bm{c}}_{i}&{\bm{a}}^{T}_{i}{\bm{d}}_{i}\\\
{\bm{b}}^{T}_{i}{\bm{a}}_{i}&{\bm{b}}^{T}_{i}{\bm{b}}_{i}&{\bm{b}}^{T}_{i}{\bm{c}}_{i}&{\bm{b}}^{T}_{i}{\bm{d}}_{i}\\\
{\bm{c}}^{T}_{i}{\bm{a}}_{i}&{\bm{c}}^{T}_{i}{\bm{b}}_{i}&{\bm{c}}^{T}_{i}{\bm{c}}_{i}&{\bm{c}}^{T}_{i}{\bm{d}}_{i}\\\
{\bm{d}}^{T}_{i}{\bm{a}}_{i}&{\bm{d}}^{T}_{i}{\bm{b}}_{i}&{\bm{d}}^{T}_{i}{\bm{c}}_{i}&{\bm{d}}^{T}_{i}{\bm{d}}_{i}\end{array}\right)dt\;\;$
is a $4n\times 4n$ matrix, and
${\bm{B}}_{i}=\int_{t_{i}}^{t_{i+1}}{\bm{q}}^{T}\left(\begin{array}[]{c}{\bm{a}}_{i}\\\
{\bm{b}}_{i}\\\ {\bm{c}}_{i}\\\ {\bm{d}}_{i}\end{array}\right)dt\;\;$ and
${\bm{y}}_{i}=\left(\begin{array}[]{c}{\bm{x}}_{i}\\\ {\bm{x}}^{\prime}_{i}\\\
{\bm{x}}_{i+1}\\\ {\bm{x}}^{\prime}_{i+1}\end{array}\right)$ are
$4n$-dimensional vectors.

Here ${\bm{x}}_{i}$, ${\bm{x}}^{\prime}_{i}$, ${\bm{x}}_{i+1}$,
${\bm{x}}^{\prime}_{i+1}$ are unknowns in the optimization problem Eq.(4).

Figure 1: The Structure of Matrix F and Vector B. Here “$+$” indicates the
overlapping of two adjacent blocks.

Since $\sum\limits_{i=0}^{m-1}\int_{t_{i}}^{t_{i+1}}{\bm{q}}^{T}{\bm{q}}dt\geq
0$ is a constant, to minimize $I_{i}$ is equivalent to minimize
${\bm{y}}^{T}_{i}{\bm{F}}_{i}{\bm{y}}_{i}-2{\bm{q}}^{T}_{i}{\bm{B}}_{i}{\bm{y}}_{i}$.
It’s obviously that objective function can be rewritten as a quadratic form

$opt=\min{\bm{y}}^{T}{\bm{F}}{\bm{y}}-2{\bm{B}}^{T}{\bm{y}}_{i}.$ (6)

where ${\bm{F}}$ is highly structured with size $2n(m+1)\times 2n(m+1)$ (see
Fig. 1).

It is not difficult to verify that matrix ${\bm{F}}$ is a symmetric positive
definite matrix. According to [8], the minimal value can be attained at the
solution of

${\bm{F}}{\bm{y}}={\bm{B}}$ (7)

It is well-known that such linear system can be solved efficiently by using
conjugate gradient method. Especially, if we have obtained an approximate
numerical solution by other solvers, we can use it as an initial point of
conjugate gradient method to refine the solution.

It is important to point out here that the same formulation Eq.(6) works for
both initial value problems (IVPs) and boundary value problems (BVPs) of
Linear ODEs. The only difference is that the first $n$ rows and columns of
${\bm{F}}$ will be removed after substituting the initial values for IVPs. But
for BVPs, there are $n$ rows in different places and the corresponding columns
which will be removed. Accordingly, the substitution also happens in
${\bm{B}}$. Thus, the number of unknowns of Eq.(6) drops by $n$.

##  4 Examples

In order to show the performance of our method to IVPs and BVPs for linear
ODEs, we give an RC ladder network system as an example, which can be used to
filter a signal by blocking certain frequencies and passing others. When we
consider its time response, this system can be considered as an IVP. In
addition, when we consider its controllability, this system becomes a BVP. We
use a constant state matrix A since it is easy to obtain the exact solution
for comparison.

Figure 2: An RC Ladder Network

###  4.1 An Initial Value Problem

An RC ladder network is shown in Fig. 2. Assume that the state variables are
${\bm{x}}=[x_{1},x_{2}]^{T}$ be the voltage across each capacitor. During the
time period $t\in[0,2]$, we study the time response function of the system.
Suppose the resistances $R_{1}=R_{2}=10k\Omega$, and the capacitance
$C_{1}=C_{2}=100\mu F$. At the beginning, ${\bm{x}}(0)=[0,0]^{T}$, we give an
input signal $u(t)=2\cdot sin(2t)$. So the model can be described as follows:

${\bm{x}}^{\prime}=\left(\begin{array}[]{rr}-2&1\\\
1&-1\end{array}\right){\bm{x}}+\left(\begin{array}[]{c}1\\\
0\end{array}\right)u(t)$

Obviously, this ODE has an exact solution as
${\bm{x}}^{*}=e^{{\bm{A}}t}\cdot\int_{0}^{t}e^{-{\bm{A}}s}{\bm{q}}(s)ds$. We
apply ode$45$ and our method, which is implemented also in Matlab, to the same
$13$ mesh-points decided by ode$45$, and get the approximate solutions
respectively. The corresponding $F$ is a $50\times 50$ matrix and its
condition number is $3.949\times 10^{3}$. The residual of both methods are
almost the same in Fig.3, and residual error of our method $0.4097\times
10^{-3}$ is slightly less than $0.4275\times 10^{-3}$ by ode$45$. However,
Fig. 4 shows that global error by our method (blue curve) $9.1313\times
10^{-5}$ is much smaller than the one by ode$45$ (red dash curve)$1.8232\times
10^{-4}$. It’s clear that the forward errors of both methods are fluctuating
around zero but the blue curve given by our method has a smaller amplitude
than ode$45$. The reason behind would be our method is a kind of global
approach compared with the local approach ode$45$.

Figure 3: Residual comparison for IVP between ODE45 (red dash) and our method
(blue).
Figure 4: Error comparison for IVP between ODE45 (red dash) and our method
(blue).

###  4.2 A Boundary Value Problem

If we want to control the former RC ladder network to achieve the goal
$x_{1}(0)=0$ and $x_{2}(2)=1$, and input signal $u(t)=2\cdot sin(2t)$, how
about the beginning voltage of $x_{2}(0)$? To answer the question, we need to
solve bvp for ODEs.

Figure 5: Residual comparison for IVP between ODE45 (red dash) and our method
(blue).
Figure 6: Error comparison for BVP between ODE45 (red dash) and our method
(blue).

In this example, We apply Matlab’s bvp5c and our method to the same $10$ mesh-
points decided by bvp5c. In our method, $F$ is a $38\times 38$ matrix with the
condition number $1.640\times 10^{3}$. In order to compare the forward error,
we also compute its exact solution by Sec 6.1 [1]. The residual of both
methods are almost the same in Fig.5, and residual error of our method
$0.7942\times 10^{-3}$ is less than $0.9595\times 10^{-3}$ given by bvp5c.
Similar to the IVP case, the same comparison result can be observed in Fig. 6,
that global error by our method (blue curve) $1.7824\times 10^{-4}$ is much
smaller than the one by bvp5c (red dash curve) $4.8521\times 10^{-4}$.

##  5 Conclusion

In this paper, we provide a conjugate gradient based method for computing
optimal solution of linear ordinary differential equations. A fine mesh in
time interval leads to a large but sparse matrix F. Due to nice properties of
F the iteration approach for linear system can be applied here and it can take
advantages of sparsity. This method can solve both IVPs and BVPs of Linear
ODEs.

As an illustrative example, we use RC ladder network to generate IVP and BVP
of Linear ODEs, whose exact solution can be found easily. By comparison, we
find that our method can give solutions with smaller forward error and global
error than solvers provided by Matlab at the same mesh-points.

## References

  * [1] U.M. Ascher, L.R. Petzold: Computer Methods for Ordinary Differential Equations and Differential Equations and Differential-algebraic Equations. SIAM, Phaladephia, 1998
  * [2] U.M. Ascher, R. Mattheij and R. Russell: Numerical Solution of Boundary Value Problems for Ordinary Differential Equations. SIAM, Vancouver(1988)
  * [3] R.M. Corless, N. Fillion: A Graduate Introduction to Numerical Methods. Springer, New York, 2013
  * [4] W.H. Enright: Continuous Numerical Methods for ODEs with Defect Control. Journal of Computational and Applied Mathematics 125:159-170 (2000)
  * [5] G.H. Golub, F.Van Loan Charles: Matrix Computations. The Johns Hopkins Unibersity Press, New York, 2012
  * [6] D.J. Higham: Robust Defect Control with Runge-Kutta Schemes.Siam Journal on Numerical Analysis 26(5):1175-1183 (1989)
  * [7] E. Kreyszig: Advanced Engineering Mathematics. 9th edn. Wiley,Columbus (2005)
  * [8] J.R. Shewchuk: An Introduction to the Conjugate Gradient Method Without the Agonizing Pain.Journal of Comparative Physiology 186(3),219–20 (1994)
  * [9] L.F. Shampine: Solving ODEs and DDEs with Residual Control: Applied Numerical Mathematics 52(1):113-127 (2005)
  * [10] L.F. Shampine, M.W. Reichelt, and J. Kierzenka: Solving Boundary Value Problems for Ordinary Differential Equations in Matlab with bvp4c. ftp://ftp.mathworks. com/pub/doc/papers/bvp/ (2000)
  * [11] E. Süli, D. Mayers: An introduction to numerical analysis. Cambridge Unibersity Press, Cambridge, 2003
  * [12] W. Walter: Ordinary Differential Equations. Springer, New York, 1998
  * [13] W.Y. Wu, W.Q. Yang: Error Estimation of Numerical Solvers for Linear Ordinary Differential Equations. https://arxiv.org/abs/1804.03363 (2018)
  * [14] N. Yadav, A. Yadav, M. Kumar: An Introduction to Neural Network Methods for Differential Equations. Springer, 2015