# Progressive Co-Attention Network for Fine-Grained Visual Classification

Tian Zhang1, Dongliang Chang1, Zhanyu Ma1,2,∗, and Jun Guo1 ∗ Corresponding
author 1 Pattern Recognition and Intelligent System Lab.,
Beijing University of Posts and Telecommunications, Beijing, China  2 Beijing
Academy of Artificial Intelligence, Beijing, China

###### Abstract

Fine-grained visual classification aims to recognize images belonging to
multiple sub-categories within a same category. It is a challenging task due
to the inherently subtle variations among highly-confused categories. Most
existing methods only take an individual image as input, which may limit the
ability of models to recognize contrastive clues from different images. In
this paper, we propose an effective method called progressive co-attention
network (PCA-Net) to tackle this problem. Specifically, we calculate the
channel-wise similarity by encouraging interaction between the feature
channels within same-category image pairs to capture the common discriminative
features. Considering that complementary information is also crucial for
recognition, we erase the prominent areas enhanced by the channel interaction
to force the network to focus on other discriminative regions. The proposed
model has achieved competitive results on three fine-grained visual
classification benchmark datasets: CUB-$200$-$2011$, Stanford Cars, and FGVC
Aircraft.

###### Index Terms:

Fine-grained visual classification, channel interaction, attention mechanism

##  I Introduction

In the past few years, convolutional neural networks (CNNs) [1, 2, 3, 4] have
achieved remarkable success in general image classification tasks. However,
recognizing fine-grained object categories (e.g., bird species [5], car [6]
and aircraft [7] models) is still a challenging task due to high intra-class
variances and low inter-class variances, which attracts extensive research
attentions.

The research of fine-grained visual classification has changed from multi-
stage framework with hand-crafted features [8, 9, 10, 11] to multi-stage
framework based on CNN features and then to end-to-end methods. Some works
design a localization sub-network to locate key parts, and then a
classification sub-network follows for identification. Such as STN [12], RA-
CNN [13], NTS-Net [14]. They first detected the local areas, and then cropped
the detected areas on the original image to learn the key parts. However,
little or no effort has been made to guarantee maximum discriminability in
these areas [15] and the training procedures of these methods are
sophisticated due to the complex architecture designs [16]. Others directly
learn a more discriminative feature representation by developing powerful deep
models [17, 18, 19, 20, 21]. Among them, the most representative method is
bilinear CNNs [17], which used two deep convolutional networks to fuse output
features, so that it could encode high-order statistics of convolutional
activation. More recent advances reduce high feature dimensions [18, 19] or
use kernel methods [20, 21] to extract higher order information. However,
these works do not have an effective design for fine-grained visual
classification in terms of the relationship between categories and the number
of key parts. Meanwhile, most of the methods mentioned above only take an
individual image as input, which will limit their ability to identify
contrastive clues from different images for fine-grained visual
classification. Generally, humans often recognize fine-grained objects by
comparing image pairs, instead of checking single image alone [22]. As shown
in Figure 1, by comparing a pair of same-category images, we can easily
capture their common and prominent features, such as head and wings. In this
way, we can learn the discriminative features precisely.

Figure 1: The motivation of the proposed method. Most previous methods only
took an individual image as input, and the relationship between images was not
explored. In our work, we input a pair of same-category images and model the
channel interaction between them to capture their common features.

Inspired by this observation, we propose a co-attention module (CA-Module) to
model the channel interaction between a pair of same-category images. By
capturing the contrastive features between channels, the model can better
learn the commonality of same-category images, thereby force the network to
focus on the common discriminative features. However, only focusing on common
features of same-category images will cause the network to ignore
complementary features that are essential for highly-confused categories. In
order to tackle this problem, we propose an attention erase module (AE-Module)
to learn complementary features by erasing the most prominent area found in
CA-Module. With the combination of these two modules, the proposed method can
capture more relevant areas to improve the model performance.

Figure 2: The framework of the progressive co-attention network (PCA-Net). The
CA-Module can model the channel-wise interaction within a pair of same-
category images to focus on the prominent areas with common characteristics.
The AE-Module can erase the images to distract attention to other areas to
capture complementary features.

##  II METHODOLOGY

In this section, we present the progressive co-attention network (PCA-Net) for
fine-grained visual classification, as illustrated in Figure 2. It is made up
of the CA-Module and the AE-Module to dig distinguishing features that are
both prominent and complementary.

###  II-A Co-Attention Module

Each channel of feature maps can be considered as the representation of a
certain feature, and its value is the response to the current feature’s
strength. Convolutional layer is to model the interaction between channels
within an image to generate more abundant features. Gao et al. [23] proposed a
self-channel interaction (SCI) module to model the interplay between different
channels within an image more effectively. Since the intra-class variances of
fine-grained images are very high, it is important to compare a pair of same-
category images to obtain common features. Hence, unlike [23] modeling self-
channel interaction, we propose a co-attention module (CA-Module) to model the
interaction between channels within two same-category images, forcing the
network to focus on the common areas.

Specifically, given an image pair, the two images are first processed by a
convolutional network to generate a pair of feature maps
${F_{1},F_{2}}\in\mathbb{R}^{c\times h\times w}$. The $c$, $h$ and $w$
indicate channel numbers, height, and width respectively. We reshape the
feature maps $F_{1},F_{2}$ to
$F^{{}^{\prime}}_{1},F^{{}^{\prime}}_{2}\in\mathbb{R}^{c\times l},l=h\times
w$. Then the channel-wise similarity is calculated by performing a bilinear
operation on $F^{{}^{\prime}}_{1}$ and $F_{2}^{\mathrm{{}^{\prime}T}}$ to
obtain a bilinear matrix $F^{{}^{\prime}}_{1}F_{2}^{\mathrm{{}^{\prime}T}}$ as
$M$. Then we take the negative value of it and get the weight matrix through a
softmax function:

$\displaystyle W_{ij}=\frac{exp({-M}_{ij})}{\sum_{k=1}^{c}exp({-M}_{ik})}.$
(1)

Where $i$ represents the $i^{th}$ channel of the first image, and $j$
represents the $j^{th}$ channel of the second image. We weight the weight
matrix $W$ to the original feature maps. Then the interacted feature maps can
be obtained as:

$\displaystyle F_{W1}={W\times F_{1}}\in\mathbb{R}^{c\times h\times w},$
$\displaystyle F_{W2}={W\times F_{2}}\in\mathbb{R}^{c\times h\times w}.$ (2)

Moreover, we use the cross-entropy loss for classification based on the
predictions that are generated by the features $F_{W}$.

After weighting the feature maps, the channels corresponding to similar
features are enhanced to find the commonality of this pair of images. The
response values of similar parts increase, and the response values of other
parts decrease.

###  II-B Attention Erase Module

The CA-Module aims to focus on the common features of same-category images,
but it ignores other slight clues containing complementary information.
Because there are subtle differences between highly-confused categories in
fine-grained images, it is necessary to pay attention to subtle features.
Hence, we propose an attention erase module (AE-Module) to capture the subtle
complementary features by erasing the prominent areas in the image.

We perform global average pooling on the feature maps weighted by CA-Module.
Then we select the channel of the feature maps corresponding to the maximum
value as attention map, and up-sample it to the original image size:

$\displaystyle A(x,y)=Upsample(\underset{m}{max}\ [F_{W}(m,x,y)]).$ (3)

Where $m$ denotes the channel index, $x$ and $y$ denote the spatial indexs.

We obtain a drop mask $M$ by setting the elements $A(x,y)$ larger than
threshold $\theta$ to $0$, and setting other elements to $1$:

$\displaystyle M(x,y)=\begin{cases}0,&\mbox{if }A(x,y)>\theta\\\ 1,&\mbox{else
}\end{cases}.$ (4)

Overlay the drop mask on the original image to obtain a new image with partial
areas erased:

$\displaystyle I_{e}=I(x,y)\otimes M(x,y),$ (5)

where $\otimes$ denotes element-wise multiplication, $I$ denotes the original
image, $I_{e}$ denotes the erased image.

TABLE I: Statistics of benchmark datasets Datesets | Class | Training | Testing
---|---|---|---
CUB-$200$-$2011$ | $200$ | $5997$ | $5794$
Stanford Cars | $196$ | $8144$ | $8041$
FGVC Aircraft | $100$ | $6667$ | $3333$

As the prominent areas of the image are erased, the attention is distracted
and the network is forced to learn discriminative information from other
areas. It can also reduce the dependence on training samples to improve the
robustness of the model.

TABLE II: Comparative experiment between recent methods with our method on CUB-$200$-$2011$, Stanford Cars, and FGVC Aircraft. The best result is colored in red, and the second best result is colored in blue. Method | Backbone | Input size | CUB-$200$-$2011$ (%) | Stanford Cars (%) | FGVC-Aircraft (%)
---|---|---|---|---|---
FT VGG-$19$ [24] | VGG-$19$ | $448\times 448$ | $77.8$ | $84.9$ | $84.8$
RA-CNN [13] | VGG-$19$ | $448\times 448$ | $85.3$ | $92.5$ | $-$
MA-CNN [25] | VGG-$19$ | $448\times 448$ | $86.5$ | $92.8$ | $89.9$
FT ResNet-$50$ [24] | ResNet-$50$ | $448\times 448$ | $84.1$ | $91.7$ | $88.5$
RAM [26] | ResNet-$50$ | $448\times 448$ | $86.0$ | $93.1$ | -
DFL-CNN [24] | ResNet-$50$ | $448\times 448$ | $87.4$ | $93.1$ | $91.7$
NTS-Net [14] | ResNet-$50$ | $448\times 448$ | $87.5$ | $93.9$ | $91.4$
MC-Loss [27] | ResNet-$50$ | $448\times 448$ | $87.3$ | $93.7$ | $92.6$
TASN [28] | ResNet-$50$ | $448\times 448$ | $87.9$ | $93.8$ | -
Cross-X [29] | ResNet-$50$ | $448\times 448$ | $87.7$ | $94.6$ | $92.6$
ACNet [30] | ResNet-$50$ | $448\times 448$ | $88.1$ | $94.6$ | $92.4$
MAMC [16] | ResNet-$50$ | $448\times 448$ | $86.2$ | $92.8$ | -
MAMC [16] | ResNet-$101$ | $448\times 448$ | $86.5$ | $93.0$ | -
CIN [23] | ResNet-$50$ | $448\times 448$ | $87.5$ | $94.1$ | $92.6$
CIN [23] | ResNet-$101$ | $448\times 448$ | $88.1$ | $94.5$ | $92.8$
API-Net [22] | ResNet-$50$ | $448\times 448$ | $87.7$ | 94.8 | 93.0
API-Net [22] | ResNet-$101$ | $448\times 448$ | 88.6 | 94.9 | 93.4
Ours | ResNet-$50$ | $448\times 448$ | $88.3$ | $94.3$ | $92.4$
Ours | ResNet-$101$ | $448\times 448$ | 88.9 | $94.6$ | $92.8$

###  II-C Fine-Grained Feature Learning

In order to make the learned features more aggregated in embedding space, we
introduce the center loss [31]. For each category, a feature vector is
calculated as the center of the corresponding category, and it will be
continuously updated during training phase. By penalizing the deviation
between the bilinear feature vector of each sample and the center of the
corresponding category, the samples belonging to the same category are grouped
together as many as possible, which enhances the discrimination of the learned
features.

Benefiting from global and local informative features of an image, we define
the feature representations for each image: $F_{J}=\\{F_{O},F_{W},F_{E}\\}$,
where $F_{O}$ denotes the feature maps extracted from the original image,
$F_{W}$ denotes the weighted feature maps of the original image, and $F_{E}$
denotes the feature maps extracted from the erased image. These features are
then fed to a fully-connection layer with a softmax function for the final
classification.

During training phase, the whole model is optimized by losses defined as

$\displaystyle L=\sum_{i\in I}L_{cls}(Y^{i},Y^{*})+\lambda
L_{cen}(Y^{i},Y^{c}),$ (6)

where $L_{cls}$ denotes the cross-entropy loss, $L_{cen}$ denotes the center
loss and $\lambda$ denotes the weight of $L_{cen}$. $Y^{i}$ is the predicted
bilinear label vector based on features $F_{O}$, $F_{W}$ and $F_{E}$. $Y^{*}$
is the ground-truth label vector and $Y^{c}$ is the learned center vector of
category.

##  III EXPERIMENTS AND DISCUSSIONS

We evaluate the proposed approach on three publicly competitive fine-grained
visual classification datasets, including CUB-$200$-$2011$ [5], Stanford Cars
[6], and FGVC Aircraft [7]. The detailed statistics with category numbers and
the standard training/testing splits are summarized in Table I. We employ
top-1 accuracy as evaluation metric.

Figure 3: The first line is the original images, the second line is the
features learned by the base model, and the third line is the features learned
by the proposed method. It can be observed that the proposed method has
learned more feature information than the base model.

###  III-A Implementation details

In all experiments, we use ResNet-$50$ [4] and ResNet-$101$ [4] as our base
networks. We remove the last pooling layer and fully-connected layer, and add
a billinear pooling [17] to generate a more powerful feature representation.
Then send the feature representation to a new fully-connected layer. The
convolutional layers are pretrained on ImageNet [32] and the fully connected
layer is randomly initialized.

The input image size of all experiments is $448\times 448$, which is the same
as the most state-of-the-art fine-grained classification approaches [24, 14,
28, 16, 23]. In order to improve the generalization ability of the model, we
implement data augmentation including random cropping and random horizontal
flipping during training phase. Only center cropping is involved in inference
phase. All experimental models are trained for $180$ epochs, using SGD as
optimizer. The initial learning rate is set to $0.01$, which annealed by $0.9$
every $2$ epoches. We use a batch size of $32$, and the last $16$ samples
belong to the same category as the first $16$ samples. The weight decay is set
to $10^{-5}$ and the momentum is set to $0.9$.

###  III-B Experimental results

The proposed method is compared with several representative methods without
extra annotations on three fine-grained benchmark datasets of
CUB-$200$-$2011$, Stanford Cars, and FGVC Aircraft, as shown in Table II. The
proposed method performs competitive results compared with the state of-the-
art methods.

Specifically, the top-1 accuracy of the proposed method on CUB-$200$-$2011$
dataset is $88.9\%$, which is better than $88.6\%$ of API-Net [22]. API-Net
performs well because it also takes a pair of images as input, and learns a
mutual feature vector by modeling the interaction between them to capture the
semantic difference in the input pair. Our method is to capture the
semantically similarity of a pair of same-category images, and disperse the
network’s attention to each discriminative area of the image.

On the other two datasets, our method also performs well, which achieves the
result with $94.6\%$ top-1 accuracy for Stanford Cars dataset and $92.8\%$
top-1 accuracy for FGVC-Aircraft dataset. However, our method does not obtain
the best results on these two datasets. Since cars and aircrafts are rigid
objects, the intra-class variances of them are not assignificant as birds. And
our method works better for objects that greatly vary within the category.

TABLE III: Ablation studies CA-Module | AE-Module | center loss | accuracy(%)
---|---|---|---
$\checkmark$ |  |  | $86.8$
| $\checkmark$ |  | $86.5$
$\checkmark$ |  | $\checkmark$ | $87.9$
| $\checkmark$ | $\checkmark$ | $87.5$
$\checkmark$ | $\checkmark$ | $\checkmark$ | $88.3$

###  III-C Ablation studies

In order to verify the effectiveness of each component in the model, we
conduct ablation studies on CUB-$200$-$2011$ dataset using ResNet-$50$ with
some of components removed for better understanding the behavior of the model,
as shown in Table III.

It can be observed that CA-Module generates weighted feature maps through
modeling the channel-wise interaction of same-category images, so that the
network can learn their common features. AE-Module erases the most prominent
area based on the weighted feature maps, making the informative areas learned
by the network diversified. The center loss makes the extracted features more
discriminative by constraining the distance between the feature vector and the
center vector of the corresponding category. Each component of the model
contributes to performance.

###  III-D Visualizations

In order to further evaluate the effectiveness of our method, we apply Grad-
CAM [33] to visualize the images of the CUB-$200$-$2011$ dataset. Grad-CAM is
formed by weighted summation of feature maps, which can show the importance of
each area to its classification. We compare the visualization results of our
method with the base model (ResNet-$50$), as shown in Figure 3. It can be
observed that the base model only learns the most prominent area of the image,
such as the bird’s beak. Our method can learn more abundant and discriminative
features, including wings and claws. This is because that our method can
distribute attention to each area to make the prediction more comprehensive,
which can not only focus on the salient features, but also capture the subtle
and fine-grained features.

##  IV CONCLUSIONS

We propose an effective fine-grained visual classification method, namely
progressive co-attention network. Among them, the co-attention module learns
discriminative features by comparing same-category images, and the attention
erase module learns subtle complementary features of images by erasing the
most prominent area. We have conducted experiments on CUB-$200$-$2011$,
Stanford Cars, and FGVC Aircraft datasets, which are superior to most existing
methods.

Acknowledgments: This work was supported in part by the National Key R & D
Program of China under Grant $2019$YFF$0303300$ and under Subject II
No.$2019$YFF$0303302$, in part by National Natural Science Foundation of China
(NSFC) No.$61922015$,$61773071$, U$19$B$2036$, in part by Beijing Natural
ScienceFoundation Project No. Z$200002$.

## References

  * [1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton,  “Imagenet classification with deep convolutional neural networks,”  in Advances in Neural Information Processing Systems, 2012.
  * [2] Karen Simonyan and Andrew Zisserman,  “Very deep convolutional networks for large-scale image recognition,”  arXiv preprint arXiv:1409.1556, 2014.
  * [3] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich,  “Going deeper with convolutions,”  in CVPR, 2015.
  * [4] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in CVPR, 2016.
  * [5] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie,  “The caltech-ucsd birds-200-2011 dataset,”  Tech. Rep., 2011.
  * [6] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei,  “3d object representations for fine-grained categorization,”  in ICCV workshops, 2013.
  * [7] Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi,  “Fine-grained visual classification of aircraft,”  Tech. Rep., 2013.
  * [8] Thomas Berg and Peter Belhumeur,  “Poof: Part-based one-vs.-one features for fine-grained categorization, face verification, and attribute estimation,”  in CVPR, 2013.
  * [9] Bangpeng Yao, Gary Bradski, and Li Fei-Fei,  “A codebook-free and annotation-free approach for fine-grained image categorization,”  in CVPR, 2012.
  * [10] Yuning Chai, Victor Lempitsky, and Andrew Zisserman,  “Symbiotic segmentation and part localization for fine-grained categorization,”  in ICCV, 2013.
  * [11] Philippe-Henri Gosselin, Naila Murray, Hervé Jégou, and Florent Perronnin,  “Revisiting the fisher vector for fine-grained classification,”  Pattern Recognition Letters, vol. 49, pp. 92–98, 2014.
  * [12] Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al.,  “Spatial transformer networks,”  in NeurIPS, 2015.
  * [13] Jianlong Fu, Heliang Zheng, and Tao Mei,  “Look closer to see better: Recurrent attention convolutional neural network for fine-grained image recognition,”  in CVPR, 2017.
  * [14] Ze Yang, Tiange Luo, Dong Wang, Zhiqiang Hu, Jun Gao, and Liwei Wang,  “Learning to navigate for fine-grained classification,”  in ECCV, 2018.
  * [15] Ruoyi Du, Dongliang Chang, Ayan Kumar Bhunia, Jiyang Xie, Yi-Zhe Song, Zhanyu Ma, and Jun Guo,  “Fine-grained visual classification via progressive multi-granularity training of jigsaw patches,”  in ECCV, 2020.
  * [16] Ming Sun, Yuchen Yuan, Feng Zhou, and Errui Ding,  “Multi-attention multi-class constraint for fine-grained image recognition,”  in ECCV, 2018.
  * [17] Tsung-Yu Lin, Aruni RoyChowdhury, and Subhransu Maji,  “Bilinear cnn models for fine-grained visual recognition,”  in ICCV, 2015.
  * [18] Yang Gao, Oscar Beijbom, Ning Zhang, and Trevor Darrell,  “Compact bilinear pooling,”  in CVPR, 2016, pp. 317–326.
  * [19] Shu Kong and Charless Fowlkes,  “Low-rank bilinear pooling for fine-grained classification,”  in CVPR, 2017.
  * [20] Yin Cui, Feng Zhou, Jiang Wang, Xiao Liu, Yuanqing Lin, and Serge Belongie,  “Kernel pooling for convolutional neural networks,”  in CVPR, 2017.
  * [21] Sijia Cai, Wangmeng Zuo, and Lei Zhang,  “Higher-order integration of hierarchical convolutional activations for fine-grained visual categorization,”  in ICCV, 2017.
  * [22] Peiqin Zhuang, Yali Wang, and Yu Qiao,  “Learning attentive pairwise interaction for fine-grained classification.,”  in AAAI, 2020.
  * [23] Yu Gao, Xintong Han, Xun Wang, Weilin Huang, and Matthew R. Scott,  “Channel Interaction Networks for Fine-Grained Image Categorization,”  arXiv e-prints, 2020.
  * [24] Yaming Wang, Vlad I Morariu, and Larry S Davis,  “Learning a discriminative filter bank within a cnn for fine-grained recognition,”  in CVPR, 2018.
  * [25] Heliang Zheng, Jianlong Fu, Tao Mei, and Jiebo Luo,  “Learning multi-attention convolutional neural network for fine-grained image recognition,”  in ICCV, 2017.
  * [26] Zhichao Li, Yi Yang, Xiao Liu, Feng Zhou, Shilei Wen, and Wei Xu,  “Dynamic computational time for visual attention,”  in ICCV, 2017.
  * [27] Dongliang Chang, Yifeng Ding, Jiyang Xie, Ayan Kumar Bhunia, Xiaoxu Li, Zhanyu Ma, Ming Wu, Jun Guo, and Yi-Zhe Song,  “The devil is in the channels: Mutual-channel loss for fine-grained image classification,”  IEEE Transactions on Image Processing, 2020.
  * [28] Heliang Zheng, Jianlong Fu, Zheng-Jun Zha, and Jiebo Luo,  “Looking for the devil in the details: Learning trilinear attention sampling network for fine-grained image recognition,”  in CVPR, 2019.
  * [29] Wei Luo, Xitong Yang, Xianjie Mo, Yuheng Lu, Larry S Davis, Jun Li, Jian Yang, and Ser-Nam Lim,  “Cross-x learning for fine-grained visual categorization,”  in ICCV, 2019.
  * [30] Ruyi Ji, Longyin Wen, Libo Zhang, Dawei Du, Yanjun Wu, Chen Zhao, Xianglong Liu, and Feiyue Huang,  “Attention convolutional binary neural tree for fine-grained visual categorization,”  arXiv preprint arXiv:1909.11378, 2019.
  * [31] Yandong Wen, Kaipeng Zhang, Zhifeng Li, and Yu Qiao,  “A discriminative feature learning approach for deep face recognition,”  in ECCV, 2016.
  * [32] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei,  “Imagenet: A large-scale hierarchical image database,”  in CVPR, 2009.
  * [33] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra,  “Grad-cam: Visual explanations from deep networks via gradient-based localization,”  in ICCV, 2017.


# Large Language Models as Data Augmenters for
Cold-Start Item Recommendation

Jianling Wang, Haokai Lu, James Caverlee, Ed Chi and Minmin Chen  Google
DeepMind jianlingw, haokai, caverlee, edchi<EMAIL_ADDRESS>
(2018)

###### Abstract.

The reasoning and generalization capabilities of LLMs can help us better
understand user preferences and item characteristics, offering exciting
prospects to enhance recommendation systems. Though effective while user-item
interactions are abundant, conventional recommendation systems struggle to
recommend cold-start items without historical interactions. To address this,
we propose utilizing LLMs as data augmenters to bridge the knowledge gap on
cold-start items during training. We employ LLMs to infer user preferences for
cold-start items based on textual description of user historical behaviors and
new item descriptions. The augmented training signals are then incorporated
into learning the downstream recommendation models through an auxiliary
pairwise loss. Through experiments on public Amazon datasets, we demonstrate
that LLMs can effectively augment the training signals for cold-start items,
leading to significant improvements in cold-start item recommendation for
various recommendation models.

Large Language Models, Cold-start Recommendation, Data Augmentation

††copyright: acmcopyright††copyright: rightsretained††journalyear: 2018††doi:
10.1145/1122445.1122456††ccs: Information systems Information retrieval

##  1\. Introduction

Large language models (LLMs) trained on massive amount of web data, embody
comprehensive understandings of the world, and have exhibited remarkable
reasoning and generalization abilities (Anil et al., 2023; Brown et al.,
2020). They have revolutionized many application fields, from creative
writing, conversational agents, to search engine design (Zhao et al., 2023;
Qin et al., 2023; Kamalloo et al., 2023). With their potential to reason and
generalize user preferences and item characteristics better, we explore their
application for recommendation systems, especially under cold-start setup.
Recommendation systems serve as essential conduits conveying interesting
contents to users across a wide range of online platforms. These systems
typically operate by analyzing users’ historical interactions to infer their
preferences and subsequently recommend items that align with those
preferences. The most widely adopted model-based recommendation systems
heavily rely on well-learned ID-based embeddings (He et al., 2017; Wang et
al., 2019) for both users and items to memorize and predict their relevance.

While effective when user item interactions are abundant, these ID embedding-
based approaches face a critical challenge in recommending fresh and tail
content, which lack the initial exposure and interaction data necessary for
the model to learn accurate embeddings. This is also known as the cold-start
problem111We focus on cold-start item recommendation here and leave
recommendations for cold-start users for future work.. To mitigate this long-
standing problem, content-based recommendation systems utilize item meta
features to assist item representation learning, i.e., replacing the ID-based
item embedding with transformation of meta features, or their combination
(Schnabel et al., 2022; Zhao et al., 2022; Gope and Jain, 2017). The hope is
to generalize the learning power from items with abundant interactions to
cold-start items through shared meta features.

Recent breakthroughs in LLMs and other foundation models offer exciting
prospects for enhancing recommendation systems. Works in (Li et al., 2023b, c;
Hou et al., 2023; Geng et al., 2022) showcase the promise of turning user
query and content features into text, and utilizing the generative LLM models
to build ID-free recommendation systems. However, it is still necessary to
fine-tune large pre-trained modality encoders for recommendation (i.e., for
the parameters and architecture) (Yuan et al., 2023), which is a resource-
intensive step and requires a significant amount of engineering effort.
Additionally, latency in serving LLMs or large foundation models per user
request to obtain recommendation results as required by these approaches is
often more than the O(100ms) response time expected on recommendation
platforms. Therefore it is prohibitively expensive to meet the Query-Per-
Second requirement of industrial recommendation systems.

To transfer the power of LLMs to address the long-standing recommendation
cold-start problem, instead of plugging them at the serving phase, we look
into their potential in filling in the data gap during the training phase for
current recommendation systems. In previous works (Li et al., 2023b, c; Hou et
al., 2023), it is observed that LLMs are capable of understanding users’
behavior (with appropriate prompt) and generating the context for contents of
interest to the users (i.e., directly generating the title of the items or
related topics). The research questions we are answering is: 1) can we utilize
LLMs’ reasoning and generalization capabilities to generate synthetic user
behaviors on cold-start items (i.e., ask if a user would prefer to watch a new
video about “prompt-engineering” taught by Andrew Ng or the new TV series
acted by Selena Gomez given the user’s watching history); 2) does augmenting
the training data for cold-start items with these synthetic interactions
improve learning for classic recommendation models? With such a model-agnostic
approach, we could bypass the slow API calls for LLM inference during serving
time and also address the data sparsity issue for cold-start items.
Additionally, the augmentation procedure as a data pre-processing step can be
easily integrated to any industrial-scale recommenation system, providing a
scalable approach to exploit LLMs’ generalization capabilities. Together we
make the following contributions in this work: 1) we propose pairwise
comparison prompting LLMs to infer a user’s preference between an item pair
based on the user’s historical interactions; 2) we integrate these LLM-
generated synthetic user preferences with a pairwise loss as a supplement to
the regular recommendation task; 3) we experiment on two real-world datasets
and show that these synthetic user preferences can significantly improve the
performance for cold-start items, and LLMs, even with a small model size, can
be effectively used as a data augmenter for cold-start recommendation.

##  2\. Related Work

LLMs for Recommendation Systems. There is increasing interest in adapting LLMs
directly for recommendation (Bao et al., 2023; Dai et al., 2023; Geng et al.,
2023; Hou et al., 2023; Li et al., 2023c; Liu et al., 2023). Another line of
research explores how to use LLMs to improve conventional recommendation
systems by generating new features (Li et al., 2023a; Xi et al., 2023) or
improving the encoding of existing features (Yu et al., 2022). The main
advantage of augmenting conventional recommendation systems with LLMs through
feature engineering or feature encoders lies in its serving efficiency, since
directly serving LLMs to retrieve items from millions or even billions of
contents on industrial recommendation platform is prohibitively expensive and
prevents their wide adoption. Our work aims to augment conventional ID-based
recommmendation with synthetic examples generated by LLMs during training,
instead of directly serving LLMs.

Cold-start item recommendation has been a persistent challenge in the field of
recommender systems. Specifically, we focus on the more challenging scenario
where cold-start items are newly uploaded and lack any user feedback.
Traditionally, recommendation systems have addressed this issue by
incorporating side information about items (Schnabel et al., 2022) and
learning the correlation between well-trained ID-based embeddings and side
information (Zhao et al., 2022). While recent efforts enable models to learn
item embedding with just few interaction (Lee et al., 2019; Du et al., 2020)
via meta-learning, these methods still fall short in effectively handling
items with no historical interactions. Our work investigates the feasibility
of utilizing LLMs to generate synthetic training signals for cold-start items,
allowing for direct learning of collaborative embeddings from these synthetic
signals.

Figure 1. Pairwise comparison prompt for a user query.

Data Augmentation has demonstrated its effectiveness on enhancing the training
efficiency of neural models across various application domains (Krizhevsky et
al., 2012; Ding et al., 2022). In the context of recommendation systems,
CLS4Rec, inspired by similar concepts in (Devlin et al., 2019), employs random
item cropping, masking, and reordering to generate augmented views of user
historical sequences, ultimately improving model robustness and accuracy. To
address the challenge of less active users, Wang et al. proposed a learning-
to-learn pipeline for augmenting training data and enhancing model performance
for this user group. However, our work is the first to generate augmented
training data for user behavior understanding based on historical
interactions, specifically aiming to bridge the knowledge gap for cold-start
items.

Table 1. Summary of cold-start recommendation and warm-start recommendation
performance (%). The augmented data generated by LLMs significantly boost
cold-start recommendation without sacrificing warm-start.

Task | Cold-start | Warm-start
---|---|---
Dataset | Beauty | Sports | Beauty | Sports
Metrics | R@5 | R@10 | R@50 | R@5 | R@10 | R@50 | R@5 | R@10 | R@50 | R@5 | R@10 | R@50
NeuMF | w/o aug | 0.14 | 0.22 | 0.48 | 0.01 | 0.02 | 0.13 | 3.44 | 5.36 | 18.76 | 2.65 | 4.76 | 17.98
content-based | 0.45 | 1.07 | 2.13 | 0.09 | 0.19 | 0.87 | 2.48 | 4.02 | 16.89 | 1.77 | 3.23 | 16.01
w/ aug | 1.19 | 2.32 | 10.53 | 0.22 | 0.41 | 2.11 | 3.35 | 5.21 | 18.03 | 2.32 | 4.75 | 17.67
SASRec | w/o aug | 0.18 | 0.48 | 0.74 | 0.10 | 0.22 | 0.31 | 4.25 | 6.18 | 19.87 | 3.57 | 5.48 | 19.01
content-based | 0.56 | 1.26 | 4.77 | 0.15 | 0.30 | 0.96 | 2.90 | 5.01 | 16.97 | 1.89 | 3.09 | 16.33
w/ aug | 1.34 | 2.47 | 11.40 | 0.37 | 0.61 | 2.41 | 4.30 | 6.11 | 19.79 | 3.51 | 5.39 | 18.95

##  3\. Preliminaries

Let $\mathcal{U}=\\{u_{1},u_{2},...,u_{G}\\}$ represent the user set,
$\mathcal{I}_{warm}=\\{i_{1},i_{2},...,i_{P}\\}$ and
$\mathcal{I}_{cold}=\\{i_{P+1},i_{P+2},...,i_{P+N}\\}$ represent the warm and
cold-start items on the platform respectively. Each item is mapped to a
trainable embedding associated with its ID. The principle of generating
personalized recommendation is to predict the compatibility between users and
items, from which the items with high compatibility to a user would be
retrieved from a large set of candidate items to make up the unique
recommendation list for the user. As one of the most effective variants of
matrix factorization (He et al., 2017), latent factor model-based
recommendation has attracted lots of attention due to the Netflix Prize. The
high level idea of latent factor models is to approximate compatibility
between a user and an item with the dot product of the corresponding latent
factor vectors. Given that $\mathbf{v}_{u}$ and $\mathbf{v}_{i}$ denote the
latent factor vector for user $u$ on item $i$, a latent factor model
calculates their compatibility via
$\hat{y}_{u,i}=\mathbf{v}_{u}^{T}\mathbf{v}_{i}$. Most of the widely-adopted
recommendation frameworks can be regarded as extension of such latent factor
model. Cold-start items, of course, have no training signal to obtain
informative embeddings $\mathbf{v}_{i}$. To bridge the knowledge gap, we
propose to generate synthetic data to simulate users’ interactions on the
cold-start items.

##  4\. LLMs as Data Augmenters

Augmented Data Generation. We focus on the PaLM family (Anil et al., 2023),
and directly use their generation without any finetuning. We follow (Hou et
al., 2023) and simply put the description of items that the user has
interacted with into the prompt. Specifically, given a user query $U_{i}$ in
the training set, we adopt the descriptive item titles to denote each
historical interactions. To infer users’ preferences from this descriptive
user query, we can either ask the user if he/she would like a specific cold-
start item (pointwise) or ask them if he/she prefer cold-start item A or B
(pairwise). LLMs have been shown to struggle with calibrated pointwise
relevance estimation (Ouyang et al., 2022), but demonstrate better
capabilities (Dai et al., 2023; Qin et al., 2023) at pairwise comparison task.
Therefore, we probe LLMs to generate pairwise preference between cold-start
items given a user query. In particular, we randomly sample an item pair
$(A,B)$ with $A,B\in\mathcal{I}_{cold}$, and construct the prompt as shown in
Figure 1 to retrieve the user’s preference between $A$ and $B$. The pairwise
comparison in the prompt ensures that we obtain training signal from every LLM
call to indicate preference between two cold-start items for the user. In
comparison, a pointwise inference on a random cold-start item for the user
will most likely result in negative labels (not interested) while positive
labels are rare.

Pairwise Comparison Loss. To incorporate this augmented signal during the
training process, we add the pair-wise preference prediction on the cold-start
item pairs as an auxiliary task complementary to the regular recommendation
task. The answer returned by the LLM would be regarded as the $pos$ item and
the other item as the $neg$. And given that a user $u$ prefers cold-start item
$pos$ than cold-start item $neg$, we have the following pairwise loss inspired
by Bayesian Personalized Ranking (BPR) loss (Rendle et al., 2009):

(1)
$\mathcal{L}_{aug}=-\sum_{(u,pos,neg)}\ln\sigma(\hat{y}_{u,pos}-\hat{y}_{u,neg}),$

in which $\sigma$ is the Sigmoid activation function. We then add this
pairwise BPR loss to the sampled batch softmax (Yi et al., 2019) loss
typically used in training recommendation model. The pairwise loss back-
propagates gradients to the embeddings of the positive and negative cold-start
items, which are often under-trained due to the lack of interaction, and thus
training signals from the main task.

##  5\. Experiments

###  5.1. Experimental Setup

Data and Preprocessing. We use the public Amazon review datasets (Ni et al.,
2019) for evaluating the performance of our method. We select the “Beauty” and
“Sports and Outdoors” categories, which include users’ ratings and reviews on
items falling into these two categories. To split the datasets for training
and testing, we follow the single-time-point split (Sun, 2023) and select the
time-point to split the data by $7$:$3$. The interaction data before the
splitting time-point would be used for model training and the trained model is
tested on interaction data after the splitting time-point. Specifically, we
regard the items showing up only in the testing data as cold-start items and
others as warm-start items, which is similar to the real-world setup. As an
example, the split resulted in 55,255 warm-start items and 2,751 cold-start
items in the “Sports and Outdoors” category. There are 224,956 user queries in
this category. We randomly sample a subset of user queries, and randomly
sampled two cold-start items for each query to generate augmented data
examples.

Models and Parameters. We evaluate the generalizability of our proposed
methods employing two established recommender backbones: Neural Matrix
Factorization (NeuMF) (He et al., 2017) and SASRec (Kang and McAuley, 2018).
NeuMF learns user embedding $\mathbf{v}_{u}$ and item embedding
$\mathbf{v}_{i}$ from their IDs, and SASRec leverages a self-attention layer
over user’s historical interactions to encode sequential information in user
embedding $\mathbf{v}_{u}$. These backbones represent core components in many
recommender systems, and we test three variations built upon them: 1) Baseline
(w/o Aug) trains recsys with the original training data; 2) content-based
method employs bag-of-words (Zhang et al., 2010) representations for items,
incorporating their category and title, which is a common approach for
handling cold-start items and 3) LLM-augmentation (w Aug) incorporates LLM-
generated augmentations and supplement the training process with pairwise
comparison loss in Equ 1. We use PaLM2 (Anil et al., 2023) with different
model size (i.e., XXS, S and L) to investigate the performance on the
synthetic data generation.

Top-K Evaluation Metrics. For each test user query, we retrieve the top-K
items from $\mathcal{I}=\mathcal{I}_{cold}\cup\mathcal{I}_{warm}$ with the
highest compatibility scores. And to compare the performance of the
recommendation systems offline, we adopt recall (i.e., R@K) to check if the
ground-truth item of the testing query shows up in the top-K list. We group
the results by ground-truth label, i.e., grouping results when the purchased
items are cold-start items in the ”cold-start” columns, and the rest in the
”warm-start” columns in Table 1.

###  5.2. Results and Analysis

In the overall comparison, we use PaLM2-S to generate the synthetic data and
combine it with the regular training data. We randomly sample 20% of user
queries and generate one augmented data example for each query. In Table 1, we
report the results to test its effectiveness on both NeuMF and SASRec. Without
any augmentation data examples, cold-start items lack training signals,
leading to extremely low recall at all K values. While content-based
leveraging item titles and descriptions can offer decent performance on cold-
start items, it neglects collaborative signals, significantly hurting warm-
start item recommendations. In contrast, the augmented training signals for
cold-start items, when learned through the pairwise loss, can benefit the
representation learning for both NeuMF and SASRec, and boost the performance
on cold-start recommendation significantly. Furthermore, the augmented signals
and pairwise comparison loss improve recall more at higher K values, as they
enable the model to rank a wider range of cold-start items, including some
less relevant ones (i.e., which still match users’ preferences). The results
suggest that LLMs is an effective data augmenter to fill up the missing
knowledge on cold-start items. Although the augmented training signals for
cold-start items hurt the warm-start item recommendations slightly for some
recall metrics, the drop in performance is marginal compared to the huge gain
obtained on cold-start recommendations.

Figure 2. Cold-start Recommendation Under Different Model Sizes and
Augmentation Percentage.

To understand the impact of different LLM model sizes, we conduct experiments
on Amazon-Beauty using NeuMF based recommender with PaLM2 of various model
sizes (i.e., XS, S and L) as the data augmenter. In Figure 2 (a), we find that
the model size does influence the performance of augmentation. It is known
that many abilities of LLMs are emergent as these models scale up (Anil et
al., 2023; Brown et al., 2020). We hypothesize larger models are able to
reason through the user historical behaviors better and infer the preferences
more accurately. In Figure 2 (b), we also observe that by generating augmented
training signals with more user queries, we can further increase the
performance for cold-start recommendation. Even though adding more synthetic
data beyond certain point ($40\%$) did not lead to any further improvement.

##  6\. Conclusion

Addressing the lack of user interactions with cold-start items is crucial for
enhancing recommendation effectiveness. We propose to employ LLMs to generate
augmented training signals for cold-start items in recommender systems. We use
a pairwise comparison prompt to leverage LLMs to infer user preferences
between pairs of cold-start items. This model-agnostic design provides
informative training signals for cold-start items without introducing
additional computational overhead during serving time. Experiments on public
datasets show that our method generates effective augmented training signals
and improves cold-start item recommendation.

## References

  * (1)
  * Anil et al. (2023) Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. 2023\.  Palm 2 technical report.  _arXiv preprint arXiv:2305.10403_.
  * Bao et al. (2023) Keqin Bao, Jizhi Zhang, Yang Zhang, Wenjie Wang, Fuli Feng, and Xiangnan He. 2023.  Tallrec: An effective and efficient tuning framework to align large language model with recommendation.  _arXiv preprint arXiv:2305.00447_.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners. In _NeurIPS_.
  * Dai et al. (2023) Sunhao Dai, Ninglu Shao, Haiyuan Zhao, Weijie Yu, Zihua Si, Chen Xu, Zhongxiang Sun, Xiao Zhang, and Jun Xu. 2023.  Uncovering ChatGPT’s Capabilities in Recommender Systems.  _arXiv preprint arXiv:2305.02182_.
  * 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 _ACL_.
  * Ding et al. (2022) Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. 2022.  Data augmentation for deep graph learning: A survey. In _ACM SIGKDD Explorations Newsletter_.
  * Du et al. (2020) Xiaoyu Du, Xiang Wang, Xiangnan He, Zechao Li, Jinhui Tang, and Tat-Seng Chua. 2020.  How to learn item representation for cold-start multimedia recommendation?. In _MM_.
  * Geng et al. (2022) Shijie Geng, Shuchang Liu, Zuohui Fu, Yingqiang Ge, and Yongfeng Zhang. 2022.  Recommendation as language processing (rlp): A unified pretrain, personalized prompt & predict paradigm (p5). In _ResSys_.
  * Geng et al. (2023) Shijie Geng, Juntao Tan, Shuchang Liu, Zuohui Fu, and Yongfeng Zhang. 2023.  VIP5: Towards Multimodal Foundation Models for Recommendation.  _arXiv preprint arXiv:2305.14302_.
  * Gope and Jain (2017) Jyotirmoy Gope and Sanjay Kumar Jain. 2017.  A survey on solving cold start problem in recommender systems. In _ICCCA_.
  * He et al. (2017) Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017.  Neural collaborative filtering. In _WWW_.
  * Hou et al. (2023) Yupeng Hou, Junjie Zhang, Zihan Lin, Hongyu Lu, Ruobing Xie, Julian McAuley, and Wayne Xin Zhao. 2023.  Large language models are zero-shot rankers for recommender systems.  _ECIR_.
  * Kamalloo et al. (2023) Ehsan Kamalloo, Nouha Dziri, Charles LA Clarke, and Davood Rafiei. 2023.  Evaluating Open-Domain Question Answering in the Era of Large Language Models. In _arXiv preprint arXiv:2305.06984_.
  * Kang and McAuley (2018) Wang-Cheng Kang and Julian McAuley. 2018.  Self-attentive sequential recommendation. In _ICDM_.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012.  Imagenet classification with deep convolutional neural networks.  _NeurIPS_.
  * Lee et al. (2019) Hoyeop Lee, Jinbae Im, Seongwon Jang, Hyunsouk Cho, and Sehee Chung. 2019.  MeLU: Meta-Learned User Preference Estimator for Cold-Start Recommendation. In _KDD_.
  * Li et al. (2023a) Chen Li, Yixiao Ge, Jiayong Mao, Dian Li, and Ying Shan. 2023a.  TagGPT: Large Language Models are Zero-shot Multimodal Taggers.  _arXiv preprint arXiv:2304.03022_.
  * Li et al. (2023b) Jiacheng Li, Ming Wang, Jin Li, Jinmiao Fu, Xin Shen, Jingbo Shang, and Julian McAuley. 2023b.  Text Is All You Need: Learning Language Representations for Sequential Recommendation. In _KDD_.
  * Li et al. (2023c) Jinming Li, Wentao Zhang, Tian Wang, Guanglei Xiong, Alan Lu, and Gerard Medioni. 2023c.  GPT4Rec: A generative framework for personalized recommendation and user interests interpretation.  _arXiv preprint arXiv:2304.03879_.
  * Liu et al. (2023) Junling Liu, Chao Liu, Renjie Lv, Kang Zhou, and Yan Zhang. 2023.  Is chatgpt a good recommender? a preliminary study.  _arXiv preprint arXiv:2304.10149_.
  * Ni et al. (2019) Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019.  Justifying recommendations using distantly-labeled reviews and fine-grained aspects. In _EMNLP_.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022\.  Training language models to follow instructions with human feedback. In _NeurIPS_.
  * Qin et al. (2023) Zhen Qin, Rolf Jagerman, Kai Hui, Honglei Zhuang, Junru Wu, Jiaming Shen, Tianqi Liu, Jialu Liu, Donald Metzler, Xuanhui Wang, et al. 2023\.  Large language models are effective text rankers with pairwise ranking prompting.  _arXiv preprint arXiv:2306.17563_.
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian personalized ranking from implicit feedback. In _UAI_.
  * Schnabel et al. (2022) Tobias Schnabel, Mengting Wan, and Longqi Yang. 2022.  Situating Recommender Systems in Practice: Towards Inductive Learning and Incremental Updates. In _arXiv preprint arXiv:2211.06365_.
  * Sun (2023) Aixin Sun. 2023.  Take a Fresh Look at Recommender Systems from an Evaluation Standpoint. In _SIGIR_.
  * Wang et al. (2022) Jianling Wang, Ya Le, Bo Chang, Yuyan Wang, Ed H Chi, and Minmin Chen. 2022.  Learning to Augment for Casual User Recommendation. In _TheWebConf_.
  * Wang et al. (2019) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019.  Neural graph collaborative filtering. In _SIGIR_.
  * Xi et al. (2023) Yunjia Xi, Weiwen Liu, Jianghao Lin, Jieming Zhu, Bo Chen, Ruiming Tang, Weinan Zhang, Rui Zhang, and Yong Yu. 2023.  Towards Open-World Recommendation with Knowledge Augmentation from Large Language Models.  _arXiv preprint arXiv:2306.10933_.
  * Yi et al. (2019) Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, Li Wei, and Ed Chi. 2019.  Sampling-bias-corrected neural modeling for large corpus item recommendations. In _RecSys_.
  * Yu et al. (2022) Yang Yu, Fangzhao Wu, Chuhan Wu, Jingwei Yi, and Qi Liu. 2022.  Tiny-newsrec: Effective and efficient plm-based news recommendation. In _EMNLP_.
  * Yuan et al. (2023) Zheng Yuan, Fajie Yuan, Yu Song, Youhua Li, Junchen Fu, Fei Yang, Yunzhu Pan, and Yongxin Ni. 2023.  Where to Go Next for Recommender Systems? ID-vs. Modality-based recommender models revisited.  _arXiv preprint arXiv:2303.13835_.
  * Zhang et al. (2010) Yin Zhang, Rong Jin, and Zhi-Hua Zhou. 2010.  Understanding bag-of-words model: a statistical framework. In _IJMLC_.
  * 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, et al. 2023\.  A survey of large language models. In _arXiv preprint arXiv:2303.18223_.
  * Zhao et al. (2022) Xu Zhao, Yi Ren, Ying Du, Shenzheng Zhang, and Nian Wang. 2022.  Improving Item Cold-start Recommendation via Model-agnostic Conditional Variational Autoencoder. In _SIGIR_.


# Necessary and Sufficient Conditions For Global Controllability of a Class of
Affine Systems

Zhengping Ji  Key Laboratory of Systems and Control, Academy of Mathematics
and Systems Science, Chinese Academy of Sciences, Beijing 100190, P. R. China
<EMAIL_ADDRESS>and  Daizhan Cheng  Key Laboratory of Systems and
Control, Academy of Mathematics and Systems Science, Chinese Academy of
Sciences, Beijing 100190, P. R. China<EMAIL_ADDRESS>
###### Abstract.

In this article we give conditions for global controllability of affine
nonlinear control systems on Euclidean spaces with drifts. Under regular and
nowhere-dense assumptions, the condition is necessary and sufficient in
codimension-1 and codimension-2 cases, and holds for systems of higher
codimensions under mild restrictions.

##  1\. Introduction

Finding necessary and sufficient conditions for global controllability of
affine control system

(1.1) $\displaystyle\dot{x}(t)=f|_{x(t)}+\sum_{i=1}^{m}u^{i}(t)g_{i}|_{x(t)}$

with smooth vector fields $f$, $\\{g_{i}\\}_{i=1}^{m}$ and measurable,
essentially bounded controls $\\{u^{i}\\}_{i=1}^{m}$ is a basic problem in
control theory. It has been solved in some simple cases, such as when the
drift vector field $f$ is zero or lies in the Lie algebra generated by
$\\{g_{i}\\}_{i=1}^{m}$ [2], for planar systems [12], and codimension-$1$
systems under assumptions requiring global generating families [9]. But the
general case remains open.

Suppose the system (1.1) is defined on a manifold $M$. $\forall x\in M$, the
accessible set of $x$ is defined as

$\mathcal{A}(x):=\bigcup_{T\geqslant 0}\mathcal{A}(x,T),$

where

$\mathcal{A}(x,T):=\Bigg{\\{}x(T)~{}\Bigg{|}\begin{array}[]{l}\exists u^{i}\in
L^{1}([0,T],\mathbb{R}),i=1,\cdots,m,\\\ (x(t),u(t))~{}\text{satisfying
(\ref{0.1})},~{}x(0)=x\end{array}\Bigg{\\}}.$

When $\mathcal{A}(x)=M$, $\forall x\in M$, we say that (1.1) is globally
controllable.

In this article we consider affine systems defined on $\mathbb{R}^{n}$ with
nonzero drifts. We will show that when the control Lie algebras of the
corresponding driftless systems are regular, the sufficient conditions stated
in [6, Theorem 6.1] are also necessary for global controllability of
codimension-$1$ systems, and of codimension-$2$ or higher systems under
certain restrictions.

##  2\. Necessary and Sufficient Conditions for Controllability

Consider System (1.1) defined on $\mathbb{R}^{n}$. From now on, denote by
$G:=\operatorname{Lie}\\{g_{i}\\}$ the Lie algebra generated by
$\\{g_{i}\\}_{i=1}^{m}$. We make the following assumption:

  1. (A1)

$G$ is regular, i.e. $\dim G|_{x}=\operatorname{Const}$, $\forall
x\in\mathbb{R}^{n}$.

Let $M$ be a manifold and $\varDelta$ an involutive distribution on $M$ (in
this article we suppose all distributions are smooth). Given $x\in M$, denote
by $\mathcal{I}_{\varDelta}(x)$ the maximal integral submanifold passing
through $x$ corresponding to $\varDelta$. Under the assumption (A1), we can
define the codimension of the system (1.1) as $n-\dim G$, and if the system is
of codimension $k$, then every integral manifold $\mathcal{I}_{G}(x)$ is a
$(n-k)$-dimensional injectively immersed edgeless submanifold in
$\mathbb{R}^{n}$, which endows $\mathbb{R}^{n}$ with a codimension-$k$
foliation structure [4], where each maximal integral submanifold is a leaf. As
a matter of fact, $\mathcal{I}_{G}(x)$ is the accessible set of $x$
corresponding to the driftless system

(2.1) $\displaystyle\dot{x}(t)=\sum_{i=1}^{m}u^{i}(t)g_{i}|_{x(t)},$

where $\\{g_{i}\\}_{i=1}^{m}$ are as in (1.1). This is the classical Chow-
Rashevskii theorem [1].

###  2.1. Codimension-$1$ Systems

######  Lemma 2.1.

Consider a codimension-1 involutive distribution $\varDelta$ on a manifold
$M$. Then a maximal integral manifold corresponding to $\varDelta$ is either
dense in $M$ or proper, i.e. an embedded submanifold.

###### Proof.

If a leaf $\mathcal{I}_{\varDelta}(x)$ of the foliation corresponding to
$\varDelta$ is improper, then
$\Omega(\mathcal{I}_{\varDelta}(x))=\overline{\mathcal{I}_{\varDelta}(x)}$
where $\Omega(\mathcal{I}_{\varDelta}(x))$ is the $\omega$-limit points of
$\mathcal{I}_{\varDelta}(x)$, which means that each point of
$\mathcal{I}_{\varDelta}(x)$ is a limit point of $\mathcal{I}_{\varDelta}(x)$
under the topology of $M$. Choose a closed cube $U$ in $M$, then
$U\cap\mathcal{I}_{\varDelta}(x)\simeq V\times\\{x_{\lambda}\\}$, where $V$ is
diffeomorphic to a closed $(n-1)$-dimensional disk, and $\\{x_{\lambda}\\}$
are points which make up a closed bounded set in $\mathbb{R}$. Since $\forall
a\in\mathcal{I}_{\varDelta}(x)$ there exists
$\\{a_{m}\\}\subset\mathcal{I}_{\varDelta}(x)$ s.t.
$\lim\limits_{m\rightarrow\infty}a_{m}=a$ with respect to the topology of $M$
but not with respect to the topology of $\mathcal{I}_{\varDelta}(x)$,
$\\{x_{\lambda}\\}$ must be dense in an interval of $\mathbb{R}$, making
$\operatorname{Int}(\overline{U\cap\mathcal{I}_{\varDelta}(x)})$ nonempty,
where $\operatorname{Int}$ is the interior of a set under the topology of $M$.
Since
$\operatorname{Int}(\overline{\mathcal{I}_{\varDelta}(x)})\neq\varnothing$, by
a well-known fact in foliation theory [11, Lemma 3.2],
$\overline{\mathcal{I}_{\varDelta}(x)}=M$. ∎

Given a manifold $M$ and a vector field $X\in\mathfrak{X}(M)$, denote by
$\psi^{X}_{t}(x)$ the flow of $X$ starting from $x\in M$ after time $t$. The
critical issue in the problem of controllability of affine nonlinear system
(1.1) is that, whether $\\{\psi_{t}^{f}(x)\\}_{t<0}$ can intersect the
accessible set of $x$ (we suppose that all vector fields mentioned are
complete). When there exists $x\in M$ such that $\mathcal{I}_{G}(x)$ is dense
in $M$, then $\\{\psi_{t}^{f}(x)\\}_{t>0}$ and $\\{\psi_{t}^{f}(x)\\}_{t<0}$
can be connected by $\mathcal{I}_{G}(x)$; this implies that the drifted system
(1.1) is controllable at $x$, i.e. $\mathcal{A}(x)=M$.

Therefore, we make another assumption:

  1. (A2)

$\forall x\in\mathbb{R}^{n}$, $\mathcal{I}_{G}(x)$ is not dense in
$\mathbb{R}^{n}$.

The following lemma is crucial to our proof of the controllability criteria.

######  Lemma 2.2.

A maximal integral manifold corresponding to a codimension-$1$ involutive
distribution satisfying (A2) separates $\mathbb{R}^{n}$ into at least two
connected components.

###### Proof.

According to [8], consider an immersion $f:M\rightarrow N$ where $M$ and $N$
are edgeless manifolds of dimensions $n-1$ and $n$ respectively, if the
inverse images of compact sets are compact, and
$H_{1}(N;\mathbb{Z}/2\mathbb{Z})=0$, then $N\backslash f(M)$ is not connected.
In our context, since the codimension-$1$ integral manifolds satisfying (A2)
is an embedding, they enjoy the separating property. ∎

######  Definition 2.3.

Let $M$ be a smooth manifold and $\varDelta$ a distribution on $M$. Given a
vector field $X\in\mathfrak{X}(M)$, by $X\in\varDelta$ we mean that
$X|_{x}\in\varDelta|_{x}$, $\forall x\in M$.

  1. (1)

Given $x,y\in M$ and tangent vectors $\xi\in T_{x}M$, $\eta\in T_{y}M$, if
$\exists g_{1},\cdots,g_{m}\in\varDelta$, $t_{1},\cdots,t_{m}\geqslant 0$,
s.t.

(2.2) $\displaystyle
x=\varphi_{t_{m}}^{g_{m}}\cdots\varphi_{t_{1}}^{g_{1}}(y),\quad\xi=(\varphi_{t_{m}}^{g_{m}})_{*}\cdots(\varphi_{t_{1}}^{g_{1}})_{*}(\eta),$

then $\xi$ is called the $\varDelta$-shift of $\eta$ from $y$, denoted by
$\xi=\varDelta_{*}(y,x)(\eta)$.

  2. (2)

Given a subset $S\subset\mathfrak{X}(M)$, the $\varDelta$-shift of $S$ to a
point $x$ is defined as

(2.3)
$\displaystyle\varDelta_{*}S(x):=\\{\varDelta_{*}(y,x)(S|_{y})|y\in\mathcal{I}_{\varDelta}(x)\\}\subset
T_{x}M.$

  3. (3)

A vector field $X$ is called $\varDelta$-invariant, if
$\varDelta_{*}X(x)=X|_{x}$, $\forall x\in M$. This is equivalent to that
$[X,Y]=0$, $\forall Y\in\varDelta$.

With the above notions, now we state the main theorem for codimension-$1$
cases.

######  Theorem 2.4.

Consider the system (1.1) of codimension $1$ satisfying (A1)(A2). It is
globally controllable if and only if

(2.4) $\displaystyle
0\in\operatorname{Int}\operatorname{Con}\\{G_{*}f(x),G|_{x}\\},\quad\forall
x\in\mathbb{R}^{n},$

where $\operatorname{Con}$ is the convex hull of vectors in $T_{x}M$.

###### Proof.

Sufficiency has been proved in [6, Theorem 6.1]. Here we show the necessity.

Assume the condition (2.4) is not satisfied, then $\forall x\in\mathbb{R}^{n}$
there exists a non-vanishing $G$-invariant smooth vector field $\xi$ on
$\mathcal{I}_{G}(x)$, such that $\forall x\in\mathbb{R}^{n}$, $f|_{x}\in
G^{*}|_{x}$, where $G^{*}|_{x}$ is the complement in $T_{x}\mathbb{R}^{n}$ of
the connected component of $T_{x}\mathbb{R}^{n}\backslash G|_{x}$ containing
$\xi|_{x}$; this is briefly denoted as $f\in G^{*}$.

Since according to Lemma 2.2 the whole space is separated by
$\mathcal{I}_{G}(x)$, and $\xi$ actually gives an orientation of
$\mathcal{I}_{G}(x)$, one can see that a trajectory of (1.1) starting from
$\mathcal{I}_{G}(x)$ cannot cross it in positive time since $f\in G^{*}$ means
the direction of $f$ on $\mathcal{I}_{G}(x)$ is either zero or the same as the
orientation normal vector field. Therefore the system is not globally
controllable. ∎

######  Remark 2.5.

The condition (2.4) actually aims to separate the accessible sets of the
system with drift $f$ and the one with drift $-f$, the latter of which is the
negative-time accessible set of (1.1).

Due to topological reasons, we cannot always find $n-1$ non-vanishing smooth
vector fields that pointwise generate a codimension-$1$ distribution. But when
this is achievable, the above criterion (2.4) can be simplified to a form
which is easier to verify.

######  Corollary 2.6.

Consider a codimension-$1$ system. If there exists $n-1$ vector fields
$\tilde{g}_{1},\cdots,\tilde{g}_{n-1}$ such that $\forall x\in\mathbb{R}^{n}$,
$G|_{x}=\operatorname{Span}_{\mathbb{R}}\\{\tilde{g}_{1}|_{x},\cdots,\tilde{g}_{n-1}|_{x}\\}$,
construct the following criterion function

(2.5) $\displaystyle
C(x):=\det(f|_{x},\tilde{g}_{1}|_{x},\cdots,\tilde{g}_{n-1}|_{x}),$

then the system is globally controllable if and only if $\forall
x\in\mathbb{R}^{n}$, $\exists y_{1},y_{2}\in\mathcal{I}_{G}(x)$, s.t.
$C(y_{1})C(y_{2})<0$, i.e. the criterion function (2.5) changes its sign on
each leaf.

The proof is straightforward by noticing that (2.5) aims to verify whether $f$
gives an orientation of the submanifold $\mathcal{I}_{G}(x)$. This corollary
confirms the conjectures in [12, 13].

###  2.2. Codimension-$k$ Systems

Now consider systems of higher codimensions. As an analogue of (A2), to ensure
that integral manifolds are embeddings, we make the following assumption on
the system (1.1).

  1. (A2’)

$\forall p\in\mathbb{R}^{n}$, given any $(n-k+1)$-dimensional cube,
$\mathcal{I}_{G}(p)$ is not dense in it.

######  Remark 2.7.

In fact, one may change (A2’) to a weaker form: $\forall x$,
$\mathcal{I}_{G}(x)$ is of finite depth. Given a foliation and denote the set
of its leaves by $F$, then by finite depth we mean that

$\underset{L\in F}{\sup}\sup\\{k~{}|~{}\exists L_{1},\cdots,L_{k}\in
F,~{}\text{s.t.}~{}L_{1}<\cdots<L_{k}=L\\},$

where the relation $<$ between leaves is defined as follows: $\forall
L_{1},L_{2}\in F$, $L_{1}<L_{2}\Leftrightarrow$ $L_{1}\in\overline{L_{2}}$
[10]. When each leaf of $\\{I_{G}(x)\\}_{x\in M}$ is of finite depth, then
each of them is an embedding (while the converse is not always true).

We will show that Theorem 2.4 still holds for codimension-$2$ systems under
the assumption (A2’), and the condition (2.4) is necessary and sufficient for
global controllability of codimension-$k$ ($k>2$) systems under certain
restrictions.

First, we define the supporting distribution of vector fields.

######  Definition 2.8.

Consider a codimension-$k$ distribution $D$ on a manifold $M$, denote its
complement in $\mathfrak{X}(M)$ by $D^{\perp}$, i.e. $D|_{x}\oplus
D^{\perp}|_{x}=T_{x}M$, $\forall x\in M$. Given a $(k-1)$-dimensional
distribution $S\subset D^{\perp}$, a set $F\subset\mathfrak{X}(M)$ is called
$S$-supported along $D$ if $S$ is $D$-invariant and there exists a
$D$-invariant non-vanishing smooth vector field $\xi\in H\backslash S$, such
that $\forall x\in U$, $F|_{x}\subset S^{+}|_{x}$, where $S^{+}|_{x}$ is the
complement in $D^{\perp}$ of the connected component of $(D^{\perp}\backslash
S)|_{x}$ containing $\xi|_{x}$, and this is briefly denoted as $f\in S^{+}$.

One can see that under assumption (A1) any system (1.1) which does not satisfy
(2.4) will allow a supporting distribution $S$ along $G$. Further, we have the
following statement on the necessity of (2.4) for a class of codimension-$k$
systems.

######  Theorem 2.9.

Consider the system (1.1) of codimension $k$ satisfying (A1)(A2’). If the
condition (2.4) is not satisfied and for the supporting distribution $S$ we
have

(2.6) $\displaystyle f|_{x}\notin\operatorname{Lie}(S)|_{x},~{}\forall
x\in\mathbb{R}^{n},$

then the system is not globally controllable.

###### Proof.

If $f\notin\operatorname{Lie}(S)$, then $G\oplus S$ is a codimension-$1$
involutive distribution; therefore each of its maximal integral manifolds will
separate $\mathbb{R}^{n}$ into two components. By similar arguments as in the
proof of Theorem 2.4, since $f$ is $S$-supported along $G$, a trajectory
starting from $x\in\mathbb{R}^{n}$ will remain in one connected component of
$\mathbb{R}^{n}\backslash\mathcal{I}_{G\oplus S}(x)$ and its boundary,
preventing the system from being controllable. ∎

Since $1$-dimensional distributions are always involutive, we have the
following corollary immediately.

######  Corollary 2.10.

For codimension-$2$ systems satisfying (A1)(A2’), the condition (2.4) is
necessary and sufficient for global controllability.

Further, when the supporting distribution is involutive we claim that there
exists a partial order on the set of the leaves of the foliation.

######  Proposition 2.11.

Consider the control-affine system (1.1) satisfying (A1)(A2). Let
$G=\operatorname{Lie}\\{g_{i}\\}$ be of codimension $k$ and the condition
(2.4) is not satisfied. If the corresponding supporting distribution $S$ of
$f$ is involutive, then $\forall x\in\mathbb{R}^{n}$, there exists a
neighbourhood of $\mathcal{I}_{G}(x)$ such that all leaves in this
neighbourhood are partially ordered.

###### Proof.

For $G$ of codimension $k$, $\exists H\subset\mathfrak{X}(M)$ which is a
$k$-dimensional regular smooth distribution satisfying $G|_{x}\oplus
H|_{x}=T_{x}M$, $\forall x\in\mathbb{R}^{n}$.

Since (2.4) is not satisfied, there exists a distribution $S$ supporting $f$
along $G$. For $x_{0}\in M$ and a local coordinate $(U,\psi)$ of $x_{0}$ in
$M$, $\forall x,y\in U$, define

(2.7) $\displaystyle y\prec
x\quad\Leftrightarrow\quad\exists\xi_{1},\cdots,\xi_{\ell}\in
S^{+},~{}t_{1}\cdots,t_{\ell}\geqslant
0,~{}\text{s.t.}~{}y=\varphi_{t_{\ell}}^{\xi_{\ell}}\cdots\varphi_{t_{1}}^{\xi_{1}}(x).$

We will show that this will derive a partial order on $U$. Its self-
reflexivity and transitivity are easy to verify; as for antisymmetry, without
loss of generality suppose $\xi_{1},\xi_{2}\in S^{+}$, $t_{1},t_{2}\geqslant
0$, $y=\varphi_{t_{1}}^{\xi_{1}}(x)$, $x=\varphi_{t_{2}}^{\xi_{2}}(y)$, then
since $S$ is involutive, by Frobenius’ theorem we may choose the coordinate
$(U,\psi)$ as such that
$\psi_{*}(S^{+}|_{x})=\\{(v^{1},\cdots,v^{n})|v^{n}>0\\}$, $\forall x\in U$.
Thus $\psi_{*}(\xi_{1}|_{x}),\psi_{*}(\xi_{2}|_{x})\in\psi_{*}(S|_{x})$ and
$\psi(x)=\varphi_{t_{2}}^{\psi_{*}(\xi_{2})}\varphi_{t_{1}}^{\psi_{*}(\xi_{1})}(\psi(x))$
will imply that $t_{1}=t_{2}=0$, whence $x=y$.

Since $G\oplus H=\mathfrak{X}(M)$ and $S$ is $G$-invariant, we have $y\prec
x\Rightarrow\varphi_{t}^{g}(y)\prec\varphi_{t}^{g}(x)$, $\forall g\in G$,
$t\geqslant 0$. Therefore, $\forall x\in M$, (2.7) defines a partial order on
its corresponding neighbourhood $U$, and hence on a neighbourhood of
$\mathcal{I}_{G}(x)$ since we may translate $U$ using vector fields belonging
to $G$. ∎

However, if the supporting distribution Lie-generates $f$, one cannot ensure
that there exists a manifold separating the accessible sets of positive time
and negative time, and this local partial order on the foliation cannot be
properly defined, since in that case $f$ may be recurrent [3], allowing a
point to move from leaves of lower order to those of higher order.

Finally, as sufficiency of the condition (2.4) for global controllability has
been proved for codimension-$k$ systems [6], we conjecture that the condition
in theorem 2.9 is the one needs to make (2.4) necessary and sufficient.

######  Conjecture 2.12.

Consider (1.1) satisfying (A1)(A2’). If (2.4) is not satisfied and for the
corresponding supporting distribution $S$ one has $f\in\operatorname{Lie}(S)$,
then the system is globally controllable.

##  3\. Applications and Outlooks

###  3.1. Applications to dimension-varying systems

Consider a dimension-varying affine system $\bar{\Sigma}$ as [7]

(3.1)
$\displaystyle\dot{\bar{x}}=\bar{f}(\bar{x})+\sum_{j=1}^{m}\bar{g}_{j}(\bar{x})u^{j},$

where $\bar{f},~{}\bar{g}_{j},\in\mathfrak{X}(\Omega)$, $j=1,\cdots,m$.
Suppose the minimum generator of $\bar{\Sigma}$ is of dimension $q$. Then if
on $\mathbb{R}^{q}$ the system satisfies (A1)(A2’), then the aforementioned
controllability criteria is applicable to the lifted system of $\bar{\Sigma}$
on $\mathbb{R}^{q}$, providing conditions for global controllability of the
dimension-varying affine systems.

###  3.2. Outlooks

In the end we propose several problems for further study. Some of them are
derived from the discussions in previous sections concerning the criteria for
global controllability, others are linked to general problems concerning the
topology and geometry of “drifted subspaces” of sub-Riemannian manifolds.

####  3.2.1. Controllability on simply connected compact manifolds

The key point of the controllability condition is the separation property of
foliations. The discussions in this article can all be extended to systems on
simply connected manifolds, since Lemma 2.2 holds for any (edgeless) manifold
$M$ satisfying $H_{1}(M,\mathbb{Z}/2\mathbb{Z})=0$. Further, when $M$ is
compact, the assumption (A2) can be replaced by that each leaf
$\mathcal{I}_{G}(x)$ is of finite depth, since this is equivalent to that each
$\mathcal{I}_{G}(x)$ is proper.

####  3.2.2. Sub-Riemannian length of optimal trajectories of drifted
subsystems

Suppose the system (1.1) on a manifold $M$ is globally controllable. Then the
driftless control system

(3.2)
$\displaystyle\dot{x}(t)=u(t)f|_{x(t)}+\sum_{i=1}^{m}u^{i}(t)g_{i}|_{x(t)}$

is also globally controllable, inducing a sub-Riemannian distance on $M$,
denoted by $d_{\mathrm{SR}}$.

$\forall x,y\in\mathbb{R}^{n}$, define

(3.5) $\displaystyle
d(x,y):=\min\Bigg{\\{}\int_{0}^{T}\big{(}\sum_{i=1}^{m}|u^{i}(t)|^{2}\big{)}^{\frac{1}{2}}\mathrm{d}t~{}\Bigg{|}\begin{array}[]{l}(x,u)~{}\text{satisfying
(\ref{0.1})},\\\ ~{}x(0)=x,~{}x(T)=y,~{}0<T<\infty\end{array}\Bigg{\\}}.$

Unlike the driftless case, $d(x,y)$ is not symmetric, hence cannot derive a
distance structure; the problem is, does $d(x,y)$ has anything to do with
$d_{\mathrm{SR}}(x,y)$? For example, one may consider the circle connecting
$x$ and $y$ which is the concatenation of the optimal trajectories from $x$ to
$y$ and from $y$ to $x$, denoted by $S(x,y)$ (note that every point on this
1-dimensional submanifold is a characteristic point of the ambient space), and
see whether the “length” $d(x,y)+d(y,x)$ of it can be estimated through the
sub-Riemannian length of $S(x,y)$ or $d_{\mathrm{SR}}(x,y)$. In particular,
the sub-Riemannian length of $S(x,x)$, denoted by
$\ell(x):=l_{\mathrm{SR}}(S(x,x))$, gives a function
$M\rightarrow\mathbb{R}^{*}$, which may characterize some properties, local or
global, of the system (for example, $\ell(x)=0$ if and only $f|_{x}=0$; if
$\psi_{t}^{f}(x)$ is periodic then $L_{f}\ell(x)=0$; if $\ell$ is bounded over
$M$, then the system (1.1) is globally controllable). Further estimates of
$\ell$ concern the steering method design of affine systems with drifts.

Moreover, the criterion in Theorem 2.4 and 2.9 are also applicable to switched
systems [5]

(3.6)
$\displaystyle\dot{x}(t)=f^{\sigma(t)}|_{x(t)}+\sum_{i=1}^{m}u^{i}(t)g_{i}|_{x(t)}$

where $\sigma:[0,+\infty\\}\rightarrow\\{1,\cdots,N\\}$ is a measurable right-
continuous mapping called the switching signal, and $\\{f^{j}\\}_{j=1}^{N}$
are smooth vector fields on $\mathbb{R}^{n}$. Define
$G:=\operatorname{Lie}\\{g_{i}\\}$, $F:=\\{f^{j}\\}_{j=1}^{N}$, and substitute
the condition (2.4) by

(3.7) $\displaystyle
0\in\operatorname{Int}\operatorname{Con}\\{G_{*}F(x),G|_{x}\\},\quad\forall
x\in\mathbb{R}^{n},$

then under assumptions (A1)(A2’), (3.7) will be necessary and sufficient for
global controllability of codimension-$1$ and codimension-$2$ switching
systems, and for those of higher codimensions under the condition (2.6).

Therefore, given a sub-Riemannian system with a generating family of $\ell$
vector fields $\\{g_{i}\\}_{i=1}^{\ell}$, if the distribution defined by
$\\{g_{1},\cdots,g_{\ell-p}\\}$ is regular and involutive, then let them serve
as the driftless part of a switched system (3.7) and the rest $p$ vector
fields in the family be the switchable drifts. When this drifted subsystem is
globally controllable, one may make analogues of the above discussions (which
is a special case as $p=1$) on sub-Riemannian distance estimates and
comparisons to the optimal trajectories of it.

## References

  * [1] A. Agrachev, D. Barilari, and U. Boscain, A comprehensive introduction to sub-Riemannian geometry, Cambridge Studies in Advanced Mathematics, vol. 181, Cambridge University Press, Cambridge, 2020.
  * [2] A. A. Agrachev and Y. Sachkov, Control Theory from the Geometric Viewpoint, Encyclopaedia of Mathematical Sciences 87, Control Theory and Optimization II, Springer-Verlag, Berlin, 2004.
  * [3] U. Boscain, M. Sigalotti, Introduction to controllability of nonlinear systems, in: Contemporary Research in Elliptic PDEs and Related Topics, Springer, Cham, 2019, 203-219.
  * [4] A. Candel, and L. Conlon, Foliations I, Graduate Studies in Mathematics, vol. 23, American Mathematical Society, Providence, RI, 2000.
  * [5] D. Cheng, Global controllability of switched nonlinear systems, in: Proceedings of the 45th IEEE Conference on Decision and Control (CDC), IEEE, San Diego, CA, USA, 2006, pp. 3742-3747.
  * [6] D. Cheng, X. Hu, and T. Shen, Analysis and Design of Nonlinear Control Systems, Springer, 2010.
  * [7] D. Cheng, and Z. Ji, From dimension-free manifolds to dimension-varying (control) systems, arXiv:2206.04461 (2022).
  * [8] M. E. Feighn, Separation properties of codimension-1 immersions, Topology 27 (1988), no. 3, 319-321.
  * [9] L. R. Hunt. $n$-dimensional controllability with $n-1$ controls, IEEE Trans. Automat. Contr. 27 (1982), no. 1, 113-117.
  * [10] T. Nishimori, Behaviour of leaves of codimension-one foliations, Tohoku Math. J. 29 (1977), no. 2, 255-273.
  * [11] C. A. M. Rojas, and B. Scárdua. Geometry, dynamics, and topology of foliations - a first course, World Scientific, 2017.
  * [12] Y. Sun, Necessary and sufficient condition for global controllability of planar affine nonlinear systems, IEEE Trans. Automat. Contr. 52 (2007), no. 8, 1454-1460.
  * [13] Y. Sun, On the global controllability for a class of 3-dimensional nonlinear systems with two inputs, in: Proceedings of 35th Chinese Control Conference (CCC), IEEE, Chengdu, China, 2016, pp. 941-944.


* Orio et al. (2022a) Orio, M., Behar, E., Luna, G. J. M., et al. 2022a, ApJ, 938, 34, doi: 10.3847/1538-4357/ac8f46
  * Orio et al. (2022b) Orio, M., Gendreau, K., Giese, M., et al. 2022b, ApJ, 932, 45, doi: 10.3847/1538-4357/ac63be
  * Orlando et al. (2009) Orlando, S., Drake, J. J., & Laming, J. M. 2009, A&A, 493, 1049, doi: 10.1051/0004-6361:200810109
  * Osborne et al. (2011) Osborne, J. P., Page, K. L., Beardmore, A. P., et al. 2011, ApJ, 727, 124, doi: 10.1088/0004-637X/727/2/124
  * Page (2012) Page, K. L. 2012, Mem. Soc. Astron. Italiana, 83, 815
  * Page et al. (2022) Page, K. L., Beardmore, A. P., Osborne, J. P., et al. 2022, MNRAS, 514, 1557, doi: 10.1093/mnras/stac1295
  * Pandey et al. (2022) Pandey, R., Habtie, G. R., Bandyopadhyay, R., et al. 2022, MNRAS, doi: 10.1093/mnras/stac2079
  * Pei et al. (2021) Pei, S., Orio, M., Gendreau, K., et al. 2021, The Astronomer’s Telegram, 14901, 1
  * Peretz et al. (2016) Peretz, U., Orio, M., Behar, E., et al. 2016, ApJ, 829, 2, doi: 10.3847/0004-637X/829/1/2
  * Prigozhin et al. (2016) Prigozhin, G., Gendreau, K., Doty, J. P., et al. 2016, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 9905, Space Telescopes and Instrumentation 2016: Ultraviolet to Gamma Ray, ed. J.-W. A. den Herder, T. Takahashi, & M. Bautz, 99051I, doi: 10.1117/12.2231718
  * Rauch (2003) Rauch, T. 2003, A&A, 403, 709, doi: 10.1051/0004-6361:20030412
  * Rauch et al. (2010) Rauch, T., Orio, M., Gonzales-Riestra, R., et al. 2010, ApJ, 717, 363, doi: 10.1088/0004-637X/717/1/363
  * Rupen et al. (2008) Rupen, M. P., Mioduszewski, A. J., & Sokoloski, J. L. 2008, ApJ, 688, 559, doi: 10.1086/525555
  * Scargle (1982) Scargle, J. D. 1982, ApJ, 263, 835, doi: 10.1086/160554
  * Schaefer (2004) Schaefer, B. E. 2004, IAU Circ., 8396, 2
  * Shen & Quataert (2022) Shen, K. J., & Quataert, E. 2022, ApJ, 938, 31, doi: 10.3847/1538-4357/ac9136
  * Shidatsu et al. (2021) Shidatsu, M., Negoro, H., Mihara, T., et al. 2021, The Astronomer’s Telegram, 14846, 1
  * Shore et al. (2012a) Shore, S. N., Augusteijn, T., Ederoclite, A., & Uthas, H. 2012a, The spectroscopic evolution of the recurrent nova T Pyxidis during its 2011 outburst (Corrigendum). I. The optically thick phase and the origin of moving lines in novae, Astronomy & Astrophysics, Volume 537, id.C2, 1 pp., doi: 10.1051/0004-6361/201117721e
  * Shore et al. (2018) Shore, S. N., Kuin, N. P., Mason, E., & De Gennaro Aquino, I. 2018, A&A, 619, A104, doi: 10.1051/0004-6361/201833204
  * Shore et al. (2021) Shore, S. N., Teyssier, F., & Thizy, O. 2021, The Astronomer’s Telegram, 14881, 1
  * Shore et al. (2012b) Shore, S. N., Wahlgren, G. M., Augusteijn, T., et al. 2012b, A&A, 540, A55, doi: 10.1051/0004-6361/201118060
  * Smith et al. (2016) Smith, R. K., Valencic, L. A., & Corrales, L. 2016, ApJ, 818, 143, doi: 10.3847/0004-637X/818/2/143
  * Sokoloski et al. (2006) Sokoloski, J. L., Luna, G. J. M., Mukai, K., & Kenyon, S. J. 2006, Nature, 442, 276, doi: 10.1038/nature04893
  * Sokolovsky et al. (2023) Sokolovsky, K. V., Johnson, T. J., Buson, S., et al. 2023, MNRAS, 521, 5453, doi: 10.1093/mnras/stad887
  * Starrfield et al. (2012) Starrfield, S., Timmes, F. X., Iliadis, C., et al. 2012, Baltic Astronomy, 21, 76, doi: 10.1515/astro-2017-0361
  * van Rossum (2012) van Rossum, D. R. 2012, ApJ, 756, 43, doi: 10.1088/0004-637X/756/1/43
  * Vurm & Metzger (2018) Vurm, I., & Metzger, B. D. 2018, ApJ, 852, 62, doi: 10.3847/1538-4357/aa9c4a
  * Wolf et al. (2013) Wolf, W. M., Bildsten, L., Brooks, J., & Paxton, B. 2013, ApJ, 777, 136, doi: 10.1088/0004-637X/777/2/136
  * Yaron et al. (2005) Yaron, O., Prialnik, D., Shara, M. M., & Kovetz, A. 2005, ApJ, 623, 398, doi: 10.1086/428435
  * Zemko et al. (2016) Zemko, P., Orio, M., Mukai, K., et al. 2016, MNRAS, 460, 2744, doi: 10.1093/mnras/stw1199