Recently, data-enabled predictive control (DeePC) schemes based on Willems' fundamental lemma have attracted considerable attention. At the core are computations using Hankel-like matrices and their connection to the concept of persistency of excitation.
We propose an iterative solver for the underlying data-driven optimal control problems resulting from linear discrete-time systems. To this end, we apply factorizations based on the discrete Fourier transform of the Hankel-like matrices, which enable fast and memory-efficient computations.
To take advantage of this factorization in an optimal control solver and to reduce the effect of inherent bad conditioning of the Hankel-like matrices, we propose an augmented Lagrangian lBFGS-method. We illustrate the performance of our method by means of a numerical study.

§ INTRODUCTION

Data-driven methods have recently received a lot of attention in the field of optimal and predictive control, see, e.g., [8, 3] as well as the survey articles [11, 18]. Far-reaching results for linear discrete-time systems have been achieved using a key result, also coined as Willems' fundamental lemma and deduced by J.C. Willems, P. Rapisarda, I. Markovsky, and  B.L.M. De Moor in [19]. This is due to
an exact representation of the input-output behavior by means of Hankel-like matrices, see, e.g., [4, 2, 16, 17] and the recent survey articles [10, 6] and the references therein.
Herein, the input-output behavior is parameterized by suitably constructed Hankel-like matrices. Then, large-scale optimal control problems with highly structured matrices have to be solved to determine the sought-after optimal controls. However, the dimension of the problem and condition number rapidly grow with increasing number of data points such that memory- and time-efficient algorithms are required for a fast solution, e.g., in model predictive control.
To this end, various approaches to reduce computational complexity and storage memory demand have been proposed for Hankel-based data-driven optimal control. One possibility is a compression of the data-matrix via singular value decomposition [21, 20]. Another approach proposes a segmentation into multiple shorter prediction horizons [13], which leads to smaller Hankel-like matrices.

In this work, we show how one can alleviate the high dimensionality and thus the immense memory requirements by means of discrete Fourier transform (DFT)-based matrix-vector multiplications combined with an iterative optimal control solver. We leverage a factorization based on circulant matrices exploiting the Hankel structure of the underlying matrices in data-driven optimal control.
Consequently, DFT allows to implement evaluations of matrix-vector products without setting up the system matrix explicitly and hence serves as a memory-efficient and fast foundation for iterative solvers.

Since the convergence rate of iterative solvers often hinges on a good condition number of the system, preconditioned methods are necessary. As in addition to the bad conditioning of Hankel-based problems, the dimension is very large, preconditioning techniques that circumvent storing the matrix explicitly are necessary.
To tackle the high dimensionality and the bad conditioning, we propose an augmented Lagrangian-based approach with a limited-memory Broyden–Fletcher–Golfarb–Shanno (lBFGS) algorithm as inner solver. Both components of this solver are highly successful in large-scale optimal control, see, e.g., [12, 9]. The lBFGS-algorithm allows for an iterative build-up of a preconditioner without having to store the matrices explicitly and thus benefits from exploiting our efficient DFT-based matrix-vector multiplication.

The contribution of this work can thus be summarized as follows. First, we formulate a DFT-based factorization for fast and memory-efficient implementation of matrix-vector multiplication involving Hankel-like matrices. We then apply this factorization to data-driven optimal control.
After formulating the proposed Lagrangian approach with lBFGS as inner solver, we provide a numerical study showcasing the convergence properties. Whereas other iterative solvers, such as the gradient method or MINRES, fail due to the bad conditioning, we illustrate that the proposed augmented Lagrangian lBFGS-method yields fast convergence while being memory-efficient.

Notation. For a finite sequence in $\R^d$ of length $N$ we use the short-hand notation $\bm u_N = (u_0,\dots, u_{N-1})$. The identity matrix in $\R^{d\times d}$ and the zero matrix in $\R^{m\times n}$ are denoted by $I_d$ and $0_{m\times n}$, respectively (where we sometimes omit subscripts if clear from context). For the Kronecker product of two matrices $A$ and $B$ we write $A\otimes B$.

§ MOTIVATION: DATA-DRIVEN PREDICTIVE CONTROL

Recently, Willems et al.'s fundamental lemma [19] has attracted a lot of interest in the data-driven control community as it paves the way to data-enabled controller design for discrete-time linear time-invariant systems [4] of the form

\begin{equation}
\label{eq:LTI}
x_{k+1} = Ax_k + Bu_k, \quad k=0,1,\ldots,
\end{equation}

with matrices $A\in\mathbb R^{n\times n}$ and $B\in\mathbb R^{n\times m}$ and where $x_k$ and $u_k$ denote the states and inputs, respectively. Under the assumption of controllability, the fundamental lemma allows for a complete, non-parametric, and data-based description of the system's behavior only by measured data including a persistently exciting input signal. An input sequence $\bm u_N$ is called persistently exciting of order $L$, $L\geq 1$, if the Hankel-like matrix

\begin{equation*}
H_L(\bm u_N) := \begin{bmatrix}
u_0 & u_1& \dots & u_{N-L}\\
u_1 & u_2& \dots & u_{N-L+1}\\
\vdots & \vdots &  &\vdots\\
u_{L-1} & u_L& \dots & u_{N-1}
\end{bmatrix}\in\mathbb R^{mL \times (N-L+1)}
\end{equation*}

has full row rank $mL$. Next we recall Willems et al.'s fundamental lemma, see [19].

Suppose that the system (<ref>) is controllable and let $(\tilde{\bm x}_N, \tilde{\bm u}_N)$ be a trajectory of (<ref>) such that $\tilde{\bm u}_N$ is persistently exciting of order $L+n$. Then $(\bm x_L,\bm u_L)$ is a length-$L$ trajectory of system (<ref>) if and only if there is $z\in\mathbb R^{N-L+1}$ satisfying

\begin{equation}
\label{eq:Hankel_description}
\begin{bmatrix}
x_0\\\vdots \\ x_{L-1}
\end{bmatrix} = H_L(\tilde{\bm x}_N) z,\quad
\begin{bmatrix}
u_0\\\vdots \\ u_{L-1}
\end{bmatrix} = H_L(\tilde{\bm u}_N) z.
\end{equation}

A persistency of excitation order $L+n$ results in a signal length

\begin{align}\label{rm:length}
N \geq (m+1)(L+n)-1.
\end{align}

A commonly used approach to control systems of the form (<ref>) is model predictive control (MPC), where the feedback is computed by solving the optimal control problem (OCP)

\begin{equation}
\label{eq:ocp}
\operatorname*{minimize}_{\bm x_L,\bm u_L}\ \frac{1}{2}\sum_{k = 0}^{L-1} \Big(x_k^\top Qx_k + u_k^\top Ru_k\Big)
\end{equation}

subject to the dynamics (<ref>) and some initial constraint $x_0 = x^0$ is solved. The matrices $Q$ and $R$ in the quadratic stage cost are assumed to be symmetric, positive definite. The fundamental lemma leverages the MPC approach to a data-enabled predictive control scheme, where the model described by the dynamics (<ref>) is replaced by the description of
the finite-length trajectories in (<ref>) involving only data stored in Hankel-like matrices. In particular, there is no need to identify the system matrices $A$ and $B$. Given a data trajectory $(\tilde{\bm x}_N, \tilde{\bm u}_N)$ with an input signal $\tilde{\bm u}_N$ of sufficient persistency of excitation order, the OCP (<ref>) can be equivalently formulated as the quadratic optimization problem

\begin{equation}
\label{eq:docp}
\operatorname*{minimize}_z\ \frac{1}{2}z^\top \mathcal Sz\qquad \text{subject to } \mathcal P z = x^0,
\end{equation}

\begin{equation}
\label{eq:S}
\mathcal S = \begin{bmatrix}
H_L(\tilde{\bm x}_N)\\ H_L(\tilde{\bm u}_N)
\end{bmatrix}^\top {\begin{bmatrix}
I_{L}\otimes Q\\
& I_{L}\otimes R
\end{bmatrix}}\begin{bmatrix}
H_L(\tilde{\bm x}_N)\\ H_L(\tilde{\bm u}_N)
\end{bmatrix}
\end{equation}

\begin{equation*}
\mathcal P = \begin{bmatrix}
I_n & 0_{n\times n(L-1)}
\end{bmatrix}H_L(\tilde{\bm x}_N).
\end{equation*}

We emphasize that OCP (<ref>) can be simply modified regarding setpoint tracking, which results in an additional linear term $q^\top z$ in the quadratic problem (<ref>). As a consequence of the persistency of excitation, the matrix $\mathcal S$ has rank $mL + n$, while the rank of $\mathcal P$ equals $n$, cf. [19].

Accounting for the required persistency of excitation order of at least $L+n$, the square matrix $\mathcal S$ has dimension $N-L+1\geq (L+n) m+n$, cf. (<ref>). Therefore, the memory demand for storing $\mathcal S$ as a dense numerical matrix, see Table <ref>, is proportional to
\begin{equation*}
(N-L+1)^2\geq\big((L+n) m+n\big)^2.
\end{equation*}

Depending on the available hardware this may render problem (<ref>) infeasible to standard solvers (e.g. ) involving 'naive' matrix-vector multiplication for large system order $n$, high input dimension $m$, or long prediction horizon $L$. In this situation, iterative methods which allow for a matrix-free implementation are favorable.

The memory consumption of $\mathcal S$ stored as a dense numerical matrix and the trajectory $(\tilde{\bm x}_N ,\tilde{\bm u}_N)$ taking 8 bytes per entry for various problem sizes.

$n$     $m$     $L$     mem. $\mathcal S$     mem. $(\tilde{\bm x}_N ,\tilde{\bm u}_N)$

100     50     50     0.46 GB     9.12 MB

200     50     50     1.29 GB     25.40 MB

300     50     50     2.53 GB     49.84 MB

500     50     50     6.27 GB     123.20 MB

100     100     100     3.23 GB     32.16 MB

200     100     100     7.30 GB     72.48 MB

300     100     100     12.99 GB     128.96 MB

500     100     100     29.28 GB     290.40 MB

§ DFT-BASED FACTORIZATION OF HANKEL-LIKE MATRICES

Let $\bm w_N$ denote the combined signal of $\tilde{\bm x}_N$ and $\tilde{\bm u}_N$ in $\mathbb R^d$, i.e., $w_k := \begin{bmatrix}
\tilde x_k^\top & \tilde u_k^\top
\end{bmatrix}{}^\top$ and $d:=n+m$. A straight-forward approach to calculate the matrix-vector product $H_L(\bm w_N) v$ without storing the full Hankel-like matrix is to make use of the structure of $H_L(\bm w_N)$ and access its coefficients directly from the generating sequence $\bm w_N$. In the following we recall a factorization result for $H_L(\bm w_N)$, which solves the memory issue likewise and in addition is favorable for the speed of the matrix-vector multiplication.

§.§ Factorization

A row permutation of $H_L(\bm w_N)$ leads to the Toeplitz-like matrix

\begin{equation}
\label{eq:perm}
T := \begin{bmatrix}
w_{L-1} &  \dots & w_{N-1}\\
\vdots &  & \vdots\\
w_{0} & \dots & w_{N-L}
\end{bmatrix}=\begin{bmatrix}
\end{bmatrix}H_L(\bm w_N),
\end{equation}
which can be embedded into the circulant block-Toeplitz matrix $C\in \R^{Nd \times N}$,

\begin{equation*}
w_{L-1} & w_L & \ldots & w_{N-1} & w_0 & w_1 & \ldots & w_{L-2} \\
w_{L-2} & w_{L-1} & \ldots & w_{N-2} & w_{N-1} & w_0 & \ldots & w_{L-3} \\
\vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\
w_{0} & w_1 & \ldots & w_{N-L} & w_{N-L+1} & w_{N-L+2} & \ldots & w_{N-1} \\ \hline
w_{N-1} & w_0 & \ldots & w_{N-L-1} & w_{N-L} & w_{N-L+1} & \ldots & w_{N-2} \\
w_{N-2} & w_{N-1} & \ldots & w_{N-L-2} & w_{N-L-1} & w_{N-L} & \ldots & w_{N-3} \\
\vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\
w_L & w_{L+1} & \ldots & w_0 & w_1 & w_2 & \ldots & w_{L-1}
\end{array}\right],
\end{equation*}

that is, $T=\begin{bmatrix}
I_{Ld} & 0
\end{bmatrix}C \begin{bmatrix}
I_{N-L+1} & 0
\end{bmatrix}^\top$. The matrix $C$ can be factorized as

\begin{align*}
C = \tilde{F} \Lambda F^{-1}
\end{align*}

where $F:=\big[\e^{-2\pi \ri kj/N}\big]_{k,j = 0,\dots, N-1}$ is a Fourier matrix in $\R^{N\times N}$, $\tilde F\ := F\otimes I_d\in\C^{Nd \times Nd}$ and $\Lambda := \diag(\Lambda_0,\,\ldots,\,\Lambda_{N-1}) \in \C^{Nd \times N}$ with

\begin{equation*}
\begin{bmatrix} \Lambda_0 \\ \vdots \\ \Lambda_{N-1}  \end{bmatrix} := \tilde{F} \begin{bmatrix} w_{L-1}\\ \vdots \\ w_{N-1} \\ w_0 \\ \vdots \\ w_{L-2}  \end{bmatrix},
\end{equation*}

see also <cit.>.

§.§ Complexity

The matrix-vector product $Cv$ can be efficiently computed, since $F^{-1}v = \frac{1}{N}F^*v$ can be evaluated in $\cO(N \log N)$
time, $\Lambda v$ can be evaluated in $\cO(Nd)$ time and

\begin{align*}
\tilde{F}v = (F \otimes I_d)v =  \left[\left(\e^{-2\pi\ri/N} \right)^{kj} I_d\right]_{k,j=0,\ldots,N-1} v
\end{align*}

can be evaluated in $\cO(Nd \log N)$ time. As a consequence, the matrix-vector product $H_L(\bm w_N)z$ can be efficiently calculated via the following three steps: 1.) zero-padding $v=\begin{bmatrix}
z^\top& 0
\end{bmatrix}{}^\top$, 2.) computing $Cv$, 3.) truncating the result and permuting its components, cf. (<ref>). Therefore, the matrix-vector multiplication $H_L(\bm w_N)w$ has complexity $\cO(Nd\log N)$. The same complexity applies to matrix-vector products involving $H_L(\bm w_N)^\top$ and $\mathcal S$ in (<ref>).

In terms of the parameters $n$, $m$, $L$, this complexity can be also be expressed as

\begin{equation*}
\cO\Big(\big((L+n)m+n\big)(n+m)\log\big((L+n)m+n\big)\Big).
\end{equation*}

In contrast to that, naive matrix-vector multiplication $\mathcal S z$ using the factorization in (<ref>) has complexity

\begin{equation*}
\cO(L(n+m)(N-L+1)) = \cO(L(n+m)(m(L+n)+n)),
\end{equation*}
while a precomputed matrix $\mathcal S$ leads to the complexity

\begin{equation*}
\cO((N-L+1)^2)=\cO((m(L+n)+n)^2).
\end{equation*}

In Table <ref> we list the complexities in the cases where one of the individual parameters $n$, $m$, or $L$ tends to infinity.

Comparison of the complexity of DFT-based and naive matrix-vector multiplication $\mathcal Sz$ w.r.t. the state dimension $n$, the input dimension $m$, and prediction horizon $L$, where in each case the remaining two parameters are fixed.

method     $n\rightarrow \infty$     $m\rightarrow \infty$     $L\rightarrow \infty$

DFT-based     $\cO(n^2\log n)$     $\cO(m^2\log m)$     $\cO(L\log L)$

naive, using (<ref>)     $\cO(n^{2})$     $\cO(m^2)$     $\cO(L^2)$

naive, precomp. $\mathcal S$     $\cO(n^2)$     $\cO(m^2)$     $\cO(L^2)$

Most standard implementations of the DFT run significantly faster when the signal length $N$ has only small prime factors (not greater than $7$). Therefore, apart from the persistency of excitation this fact should be taken into account while choosing the length of the data trajectory.

§ AUGMENTED LAGRANGIAN WITH LBFGS

Here, we briefly describe the solution method which enables a memory-efficient algorithm for solving the equality constrained optimization problem (<ref>). As an outer loop, we implement an augmented Lagrangian method, where in an inner loop, the arising unconstrained problems of the outer loop are solved by the Broyden–Fletcher–Goldfarb–Shanno (BFGS) method. We highlight that the combination of these two algorithms allows for solving (<ref>) without storing the matrix and by just implementing a function that evaluates the matrix-vector products based on the given data and DFT. This is due to the fact that, whereas the BFGS method is a quasi-Newton method and hence does not suffer from ill-conditioning as much as the gradient method, the preconditioner is built up successively via rank-one updates. These updates of the preconditioner, given by an approximation of the inverse Hessian, can be performed efficiently with the DFT-based factorizations presented before.

The presentation in this section is based on [12]. In this part, we abbreviate $q := N-L+1$ being the dimension of the variable $z$ in (<ref>).

§.§ Outer loop: Augmented Lagrangian

To solve the linearly constrained quadratic problem (<ref>), we apply the augmented Lagrangian method. To this end, let $\lambda \in \R^n$ and $\mu > 0$ and define the augmented Lagrangian function

\begin{align*}
\mathcal{L}(z,\lambda;\mu) &:= \frac{1}{2}z^\top \mathcal Sz + \frac{\mu}{2} \|\mathcal Pz-x^0\|^2_2 -\lambda^\top (\mathcal Pz-x^0)\\
&\phantom{:}= \frac12 z^\top(\mathcal{S} + \mu \mathcal{P}^\top \mathcal{P})z - (\mu x^0 + \lambda)^\top\mathcal{P}z \\&
\qquad + \left(\frac{\mu}{2}x^0-\lambda\right)^\top x^0.
\end{align*}

Then, the unconstrained problem

\begin{align*}    \operatorname*{minimize}_z\  \mathcal{L}(z,\lambda_k;\mu_k)
\end{align*}

is successively solved for an increasing sequence of penalty parameters $\mu_k>0$ and corresponding suitable choice of the Lagrange multiplier $\lambda_k \in \R^n$. The algorithm is shown in Algorithm <ref>.

Augmented Lagrangian method
[1]
$\mu_0>0$, $\mu_\Delta>0$, tolerance $\delta >0$, $z_0^s\in \R^{q}$, $\lambda_0\in \R^n$.
approximate minimizer $z_*$ of (<ref>).
$k \gets 0$.
not converged
$z_k \gets $ approx. min. of $\mathcal{L}(\cdot,\lambda_k;\mu_k)$ starting at $z_0^s$ satisfying $\|\nabla_z \mathcal{L}(z_k,\lambda_k;\mu_k)\| \leq \delta$.
$\lambda_{k+1} \gets \lambda_k - \mu_k (\mathcal Pz-x^0)$.
$\mu_{k+1} \gets \mu_k + \mu_\Delta$.
$z_0^s \gets z_k$.
$k \gets k+1$.
$z_* \gets z_{k-1}$.

Note that, in contrast to plain quadratic penalty methods (i.e., setting $\lambda_k = 0$) which often suffer from inherent ill-conditioning when increasing the penalty parameter$\mu_k$, see <cit.>, the augmented Lagrangian method includes a Lagrange multiplier $\lambda_k$ which alleviates this problem, cf. <cit.>.

§.§ Inner loop: Limited memory BFGS

We briefly derive the BFGS-method to solve the subproblem in Algorithm <ref> considered with the minimization of

\begin{align*}
f_k(z) := \mathcal{L}(z,\lambda_k;\mu_k)
\end{align*}

over $z\in \R^q$.
Direct calculations yield that the gradient w.r.t. $z$ is given by

\begin{align*}
\nabla f_k(z) &= \nabla_z \mathcal{L}(z,\lambda_k;\mu_k) \\ &=  (\mathcal{S} + \mu_k \mathcal{P}^\top \mathcal{P})z - \mathcal P^\top(\mu_k x^0 + \lambda_k).
\end{align*}

As the model is quadratic, and as standard in optimization, we can compute directly the minimizer for line searches, i.e., for the iterate $z_j$ and a search direction $p_j$

\begin{align*}
\alpha_j = \operatorname*{argmin}_{\alpha \in \R} f_k(z_j + \alpha p_j) =  \frac{-\nabla f_k(z_j)^\top p_j}{p_j^\top (\mathcal S + \mu_k \mathcal P^\top \mathcal P)p_j}.
\end{align*}

The BFGS method is stated in Algorithm <ref>. Whereas this algorithm is standard in numerical optimization and can be shown to converge superlinearly <cit.>, we state it here to highlight the fact that we may implement it without storing the matrices $\mathcal{S}$ and $\mathcal{P}$, i.e., by using the memory efficient DFT-based approach highlighted in Section <ref>.

BFGS method to solve $\min_z f_k(z)$
[1]
$z_0\in \R^q$, $H_0 = I_{q}$, tolerance $\varepsilon>0$, parameters $\lambda_k,\,\mu_k$ defining $f_k = \mathcal L(\,\cdot\,, \lambda_k;\mu_k)$.
approximate minimizer $z_*$ of $f_k$.
$j \gets 0$.
$\|\nabla f_k(z_j)\| \geq \varepsilon$
$p_j \gets -H_j \nabla f_k(z_j)$. Compute search direction.
$\alpha_j \gets \frac{-\nabla f_k(z_j)^\top p_j}{p_j^\top (\mathcal S + \mu_k \mathcal P^\top \mathcal P)p_j}$. Exact line search.
$z_{j+1} \gets z_j + \alpha_j p_j$. Update iterate.
$s_j \gets z_{j+1}-z_j$.
$y_j \gets \nabla f_k(z_{j+1}) - \nabla f_k(z_j)$.
$\rho_j \gets (s_j^\top y_j)^{-1}$.
$H_{j+1} \gets \big(I-\rho_js_jy_j^\top\big)H_j\big(I-\rho_jy_js_j^\top\big) + \rho_js_js_j^\top $.
$j\gets j+1$.
$z_* \gets z_{j}$.

In limited memory BFGS [9], the update step for the inverse Hessian approximation $H_j$ is modified. Instead of including the full history of $\{s_0,\ldots,s_j\}$ and $\{y_0,\ldots,y_j\}$, only a window of fixed size of the most recent quantities is used.

§ NUMERICAL SIMULATIONS

We demonstrate the proposed algorithm for the quadratic problem (<ref>) with various state dimensions $n$, input dimensions $m$, and prediction horizons $L$.
For each experiment, the LTI system $(A,B)$ is drawn randomly such that $A$ has spectral radius equal to $0.9$ to ensure stability of the system, and such that $A$ and $B$ are sparse with roughly half of their entries equal to zero. The input sequence $\tilde{\bm u}_N$ of the data trajectory $(\tilde{\bm x}_N, \tilde{\bm u}_N)$ is drawn randomly, where the signal length $N$ is optimized regarding the speedup of the DFT, cf. Remark <ref>. Further, the control task (<ref>) is extended to setpoint tracking, where the setpoint is some equilibrium of system (<ref>). All calculations were performed in  on a  CPU.

In Figure <ref>, the progression of the residuals regarding the iteration number is shown for the proposed method (aL lBFGS), MINRES [14], and gradient descent combined with an augmented Lagrangian (aL GD) for the parameters $n=100$, $m=L = 50$. The residual $r_k$, which is defined as

\begin{equation*}
r_k := \begin{bmatrix}
\mathcal S z_k - \mathcal P^\top \lambda_k\\
\mathcal P z_k - x^0
\end{bmatrix}
\end{equation*}

with approximated primal and dual solutions $z_k$ and $\lambda_k$ at iteration $k$, indicates the violation of the first-order Karush–Kuhn–Tucker condition for the constrained problem (<ref>). It is evident that neither gradient descent nor MINRES perform well.

Residuals over iterations for the proposed method (aL lBFGS), MINRES, and gradient descent employing an augmented Lagrangian approach (aL GD) for $n=100$, $m=L = 50$.

While running, the BFGS algorithm constructs a preconditioner $\mathcal B$ of the matrix $\mathcal S$ which is improved in every iteration step. In Figure <ref> the condition numbers[The condition number is defined as the ratio between the largest and smallest non-zero singular value.] $\kappa(\mathcal{S})$ and $\kappa(\mathcal B\mathcal{S})$ of $\mathcal S$ and $\mathcal B\mathcal S$ are depicted in the case $m=L=50$. Even though the  condition drastically improves during a BFGS run, $\kappa(\mathcal B\mathcal S)$ seems to grow similarly to $\kappa(\mathcal S)$ in the state dimension.

The condition number of the matrix $\mathcal S$ (blue circles) and $\mathcal B\mathcal S$ (red diamonds) for increasing state dimension $n$ and fixed values $m = L = 50$.

Total number of BFGS iterations in dependence of the state dimension $n$ in (<ref>) for fixed $m=L=50$ (blue circles) and for $m=L=100$ (red diamonds).

Total execution time in dependence of the state dimension $n$ in (<ref>) for fixed $m=L=50$ (blue circles) and for $m=L=100$ (red diamonds).

Mean execution time per BFGS iteration (total execution time divided by the total
number of iterations divided) for increasing $n$ and fixed $m,L$ with $m=L=50$ (blue circles) and $m=L=100$ (red diamonds).

In Figures <ref> and <ref>, the total number of BFGS iterations and the total execution time for solving (<ref>) with the proposed method are shown. The connection between Figures <ref> and <ref> can be seen in Figure <ref>, which illustrates the mean execution time per BFGS iteration given as the ratio of total execution time and total number of BFGS iterations. The theoretical asymptotical behavior of $\cO(n^2\log n)$ as $n\to\infty$ for the DFT-based matrix-vector multiplication is reflected in Figure <ref>, cf. Table <ref>.

§ CONCLUSION

We proposed an iterative algorithm to solve data-driven optimal control problems involving Hankel-like matrices.
To this end, we tackled both the high dimension and bad conditioning of the problem by means of a DFT-based factorization of the respective
matrices (enabling fast matrix-vector multiplication) in combination
with an lBFGS method.
The latter allows to construct a preconditioner iteratively, without relying on  storing the matrix, which allows for the solution of problems with high dimension stemming from many data samples.

Future work may exploit recently-proposed concepts by [1, 5] in combination with the proposed algorithmic advancements or the application of the derived results w.r.t. energy systems based on our previous work [15].

§ CODE AVAILABILITY

The code that produced the numerical results is available at

§ AKNOWLEDGEMENT

Philipp Schmitz is grateful for the support from the Carl Zeiss Foundation (VerneDCt, Project No. 2011640173). Karl Worthmann gratefully acknowledges funding by the German Research Foundation (DFG, Project-ID 507037103).

[1]
J. Berberich, A. Iannelli, A. Padoan, J. Coulson, F. Dörfler, and
F. Allgöwer.
A quantitative and constructive proof of Willems’ fundamental
lemma and its implications.
In 2023 American Control Conference (ACC), pages 4155–4160,

[2]
J. Berberich, J. Köhler, M. A. Müller, and F. Allgöwer.
Data-driven model predictive control with stability and robustness
IEEE Transactions on Automatic Control, 66(4):1702–1717, 2020.

[3]
L. Bold, L. Grüne, M. Schaller, and K. Worthmann.
Practical asymptotic stability of data-driven model predictive
control using extended DMD.
arXiv preprint arXiv:2308.00296, 2023.

[4]
J. Coulson, J. Lygeros, and F. Dörfler.
Data-enabled predictive control: In the shallows of the DeePC.
In 2019 18th European Control Conference (ECC), pages 307–312,

[5]
J. Coulson, H. J. Van Waarde, J. Lygeros, and F. Dörfler.
A quantitative notion of persistency of excitation and the robust
fundamental lemma.
IEEE Control Systems Letters, 7:1243–1248, 2022.

[6]
T. Faulwasser, R. Ou, G. Pan, P. Schmitz, and K. Worthmann.
Behavioral theory for stochastic systems? A data-driven journey
from Willems to Wiener and back again.
Annual Reviews in Control, 55:92–117, 2023.

[7]
G. H. Golub and J. F. Van Loan.
Matrix Computations.
The John Hopkins University Press, Baltimore, 4th edition, 2013.

[8]
L. Hewing, K. P. Wabersich, M. Menner, and M. N. Zeilinger.
Learning-based model predictive control: Toward safe learning in
Annual Review of Control, Robotics, and Autonomous Systems,
3:269–296, 2020.

[9]
D. C. Liu and J. Nocedal.
On the limited memory BFGS method for large scale optimization.
Mathematical Programming, 45(1–3):503–528, 1989.

[10]
I. Markovsky and F. Dörfler.
Behavioral systems theory in data-driven analysis, signal processing,
and control.
Annual Reviews in Control, 52:42–64, 2021.

[11]
T. Martin, T. B. Schön, and F. Allgöwer.
Guarantees for data-driven control of nonlinear systems using
semidefinite programming: A survey.
Annual Reviews in Control, 56:100911, 2023.

[12]
J. Nocedal and S. J. Wright.
Numerical Optimization.
Springer Series in Operations Research and Financial Engineering.
Spinger, New York, 2nd edition, 2006.

[13]
E. O’Dwyer, E. C. Kerrigan, P. Falugi, M. Zagorowska, and N. Shah.
Data-driven predictive control with improved performance using
segmented trajectories.
IEEE Transactions on Control Systems Technology,
31(3):1355–1365, 2022.

[14]
C. C. Paige and M. A. Saunders.
Solution of sparse indefinite systems of linear equations.
SIAM Journal on Numerical Analysis, 12(4):617–629, 1975.

[15]
P. Schmitz, A. Engelmann, T. Faulwasser, and K. Worthmann.
Data-driven MPC of descriptor systems: A case study for power
IFAC-PapersOnLine, 55(30):359–364, 2022.

[16]
P. Schmitz, T. Faulwasser, and K. Worthmann.
Willems’ fundamental lemma for linear descriptor systems and its
use for data-driven output-feedback MPC.
IEEE Control Systems Letters, 6:2443–2448, 2022.

[17]
H. J. van Waarde, C. De Persis, M. K. Camlibel, and P. Tesi.
Willems’ fundamental lemma for state-space systems and its
extension to multiple datasets.
IEEE Control Systems Letters, 4(3):602–607, 2020.

[18]
P. Verheijen, V. Breschi, and M. Lazar.
Handbook of linear data-driven predictive control: Theory,
implementation and design.
Annual Reviews in Control, 56:100914, 2023.

[19]
J. C. Willems, P. Rapisarda, I. Markovsky, and B. L. M. De Moor.
A note on persistency of excitation.
Systems & Control Letters, 54(4):325–329, 2005.

[20]
M. Yin, A. Iannelli, and R. S. Smith.
Maximum likelihood signal matrix model for data-driven predictive
In Proceedings of Machine Learning Research, volume 144, pages
1–11, 2021.

[21]
K. Zhang, Y. Zheng, C. Shang, and Z. Li.
Dimension reduction for efficient data-enabled predictive control.
IEEE Control Systems Letters, 7:3277–3282, 2023.

get arXiv to do 4 passes: Label(s) may have changed. Rerun


# Reconstruction of IACT events using deep learning techniques with CTLearn

D. Nieto,1 T. Miener,1 A. Brill2, J. L. Contreras,1 T. B. Humensky,2 and R.
Mukherjee,3 for the CTA Consortium

###### Abstract

Arrays of imaging atmospheric Cherenkov telescopes (IACT) are superb
instruments to probe the very-high-energy gamma-ray sky. This type of
telescope focuses the Cherenkov light emitted from air showers, initiated by
very-high-energy gamma rays and cosmic rays, onto the camera plane. Then, a
fast camera digitizes the longitudinal development of the air shower,
recording its spatial, temporal, and calorimetric information. The properties
of the primary very-high-energy particle initiating the air shower can then be
inferred from those images: the primary particle can be classified as a gamma
ray or a cosmic ray and its energy and incoming direction can be estimated.
This so-called full-event reconstruction, crucial to the sensitivity of the
array to gamma rays, can be assisted by machine learning techniques. We
present a deep-learning driven, full-event reconstruction applied to simulated
IACT events using CTLearn. CTLearn is a Python package that includes modules
for loading and manipulating IACT data and for running deep learning models
with TensorFlow, using pixel-wise camera data as input.

1Instituto de Física de Partículas y del Cosmos and Departamento de EMFTEL,
Universidad Complutense de Madrid, Spain<EMAIL_ADDRESS><EMAIL_ADDRESS>
2Physics Department, Columbia University, New York, USA;
<EMAIL_ADDRESS>
3Department of Physics and Astronomy, Barnard College, Columbia University,
New York, USA

##  1 Introduction

The ability of deep learning to assist in the analysis of data from imaging
atmospheric Cherenkov telescopes (IACT) was first demonstrated by the
detection of muon rings in real data (Feng & Lin 2016) and by the
classification of gamma-ray and cosmic-ray simulated events (Nieto et al.
2017). Subsequent studies proved its capability to reconstruct the energy and
arrival direction of simulated gamma-ray events (Mangano et al. 2018;
Jacquemont et al. 2020) and to improve IACT sensitivity on real data (Shilon
et al. 2019). CTLearn111https://github.com/ctlearn-project/ctlearn (Nieto et
al. 2019a; Brill et al. 2019) is a high-level, open-source Python package
providing a backend for training deep learning models for IACT event
reconstruction using TensorFlow. CTLearn allows its user to focus on
developing and applying new models while making use of functionality
specifically designed for IACT event reconstruction. The user can customize
the training and built-in models hyperparameters. Hyperparameter optimization
is available through the accompanying CTLearn-optimizer package. Data loading
and pre-processing are performed using an associated external package,
DL1-Data-Handler (Kim et al. 2020). A diagram summarizing CTLearn architecture
is shown in Fig. 1.

Figure 1.: Diagram summarizing CTLearn’s framework design.

##  2 Full-event reconstruction

Model architecture. CTLearn works with any TensorFlow model obeying a generic
signature. In addition, CTLearn includes two built-in models for gamma/hadron
classification of stereoscopic data (Brill et al. 2019) and a third one for
full-event reconstruction of monoscopic data, dubbed _TRN-single-tel_ model
(see Fig. 2, left panel). This last model is based on a deep convolutional
neural network (CNN)-based architecture with residual connections (He et al.
2015) adapted from a thin ResNet (Xie et al. 2019). A squeeze-and-excitation
attention mechanism (Hu et al. 2017) was added into the CNN blocks. The
architecture ends on a selectable fully-connected head that performs either
particle classification or regression (energy or arrival direction
reconstruction).

Figure 2.: _Left)_ _TRN-single-tel_ architecture. Prediction results are
either particle type or energy or arrival direction. _Right)_ Example of ROC
curves for the same given random seed.

Experiments. We trained and tested our _TRN-single-tel_ model with a dataset
of simulated events for the Cherenkov Telescope Array222www.cta-
observatory.org (Acharya et al. 2018, CTA), the next generation ground-based
observatory for gamma-ray astronomy at very-high energies: 2 million images
from events having triggered an array of 4 large-sized telescopes (LSTs) in
monoscopic mode We considered diffuse gamma-ray and proton-initiated events,
simulated within a cone of 10∘ radius - covering the whole field of view (FoV)
of the instrument - in a balanced way. An 80% of the data were used for
training and a 20% for testing. We trained the model on 200k batches of 64
images, validating periodically. The pixel layout in the original images is a
hexagonal lattice, mapped to a Cartesian lattice using bilinear interpolation
(Nieto et al. 2019b). The model was trained independently for each
reconstruction task. Two experiments were conducted: a) training and testing
on all triggered events and b) training and testing on events where the images
of the showers were mostly contained within the field of view of the telescope
(no more than 20% of the total image charge within the two outermost rings of
pixels on the camera). Training was repeated 10 times for each experiment,
setting a different random seed that varied the weight initialization and
training set shuffling.
Results. The _TRN-single-tel_ model successfully learned to perform full-event
reconstruction across the entire FoV of the telescope. The classification
accuracy (0.5 threshold) on the test set of diffuse events was $0.748\pm
0.002~{}(0.756\pm 0.001)$, with an area under the ROC curve of $0.848\pm
0.002~{}(0.856\pm 0.001)$ for the all-events (contained-events) experiment
(average and standard deviation computed from the results of all training
runs). An example of ROC curves can be found in Fig. 2, right panel. The
energy resolution and bias, and angular resolution provided by the model on
the test set of diffuse gamma-ray events can be found in Fig. 3, where the
data points represent the median of all training runs and 16% – 84%
containment bands are shown, illustrating the inference robustness of the
model. We remark that these results come from the reconstruction of diffuse
events and note that the reconstruction for events showing arrival directions
close to the center of the FoV would perform substantially better.

Figure 3.: _Left)_ Energy resolution; _center)_ Energy bias; _right)_ Angular
resolution (all vs. reconstructed energy). Tested on diffuse gamma-ray events.

##  3 Conclusions and outlook

CTLearn’s design and main features have been presented, showing its high level
of configurability and flexibility, and demonstrating its potential for
monoscopic full-event reconstruction using CTA simulated events. Areas where
development is planned or already ongoing are: building models for
stereoscopic full-event reconstruction; exploiting multitask learning;
implementing models that could combine event-level data from a heterogeneous
collection of telescope types, enabling IACT-specific metrics and loss
functions; and ultimately applying full-event reconstruction to real IACT
data.

### Acknowledgments

This work was conducted in the context of the CTA Analysis and Simulations
Working Group. We gratefully acknowledge financial support from the agencies
and organizations listed here:
http://www.cta-observatory.org/consortium_acknowledgments.
DN and JLC acknowledge support from The European Science Cluster of Astronomy
& Particle Physics ESFRI Research Infrastructures funded by the European
Union’s Horizon 2020 research and innovation program under Grant Agreement no.
824064. TM acknowledges support from FPA2017-82729-C6-3-R. AB acknowledges
support from NSF award PHY-1229205. DN acknowledges the support of NVIDIA
Corporation with the donation of a Titan X Pascal GPU used for this research.
The ASP would like to thank the dedicated researchers who are publishing with
the ASP.

## References

  * Acharya et al. (2018) Acharya, B., et al. (CTA Consortium) 2018, Science with the Cherenkov Telescope Array (WSP). https://arxiv.org/abs/1709.07997
  * Brill et al. (2019) Brill, A., et al. 2019, CTLearn: Deep learning for imaging atmospheric Cherenkov telescopes event reconstruction. URL https://doi.org/10.5281/zenodo.3345947
  * Brill et al. (2019) Brill, A., et al. 2019, in 2019 New York Scientific Data Summit (NYSDS), 1. URL https://doi.org/10.1109/NYSDS.2019.8909697
  * Feng & Lin (2016) Feng, Q., & Lin, T. T. Y. 2016, Proceedings of the International Astronomical Union, 12, 173–179. URL http://dx.doi.org/10.1017/S1743921316012734
  * He et al. (2015) He, K., et al. 2015, arXiv e-prints, arXiv:1512.03385. https://arxiv.org/abs/1512.03385
  * Hu et al. (2017) Hu, J., et al. 2017, arXiv e-prints, arXiv:1709.01507. https://arxiv.org/abs/1709.01507
  * Jacquemont et al. (2020) Jacquemont, M., et al. 2020, in these proceedings
  * Kim et al. (2020) Kim, B., et al. 2020, DL1-Data-Handler: DL1 HDF5 writer, reader, and processor for IACT data. URL https://doi.org/10.5281/zenodo.3979698
  * Mangano et al. (2018) Mangano, S., et al. 2018, Lecture Notes in Computer Science, arXiv:1810.00592. URL http://dx.doi.org/10.1007/978-3-319-99978-4
  * Nieto et al. (2017) Nieto, D., et al. 2017, in Proceedings of 35th International Cosmic Ray Conference — PoS(ICRC2017), vol. 301, 809. URL https://doi.org/10.22323/1.301.0809
  * Nieto et al. (2019a) — 2019a, in Proceedings of 36th International Cosmic Ray Conference — PoS(ICRC2019), vol. 358, 752. https://arxiv.org/abs/1912.09877
  * Nieto et al. (2019b) — 2019b, in Proceedings of 36th International Cosmic Ray Conference — PoS(ICRC2019), vol. 358, 753. https://arxiv.org/abs/1912.09898
  * Shilon et al. (2019) Shilon, I., et al. 2019, Astroparticle Physics, 105, 44. https://arxiv.org/abs/1803.10698
  * Xie et al. (2019) Xie, W., et al. 2019, arXiv e-prints, arXiv:1902.10107. https://arxiv.org/abs/1902.10107


# Large-scale Training Data Search for Object Re-identification

Yue Yao1 Huan Lei1 Tom Gedeon2 Liang Zheng1
1Australian National University 2Curtin University
{first name.second name}@{anu | curtin}.edu.au

###### Abstract

We consider a scenario where we have access to the target domain, but cannot
afford on-the-fly training data annotation, and instead would like to
construct an alternative training set from a large-scale data pool such that a
competitive model can be obtained. We propose a search and pruning (SnP)
solution to this training data search problem, tailored to object re-
identification (re-ID), an application aiming to match the same object
captured by different cameras. Specifically, the search stage identifies and
merges clusters of source identities which exhibit similar distributions with
the target domain. The second stage, subject to a budget, then selects
identities and their images from the Stage I output, to control the size of
the resulting training set for efficient training. The two steps provide us
with training sets 80% smaller than the source pool while achieving a similar
or even higher re-ID accuracy. These training sets are also shown to be
superior to a few existing search methods such as random sampling and greedy
sampling under the same budget on training data size. If we release the
budget, training sets resulting from the first stage alone allow even higher
re-ID accuracy. We provide interesting discussions on the specificity of our
method to the re-ID problem and particularly its role in bridging the re-ID
domain gap. The code is available at https://github.com/yorkeyao/SnP

##  1 Introduction

Figure 1: We present a search and pruning (SnP) solution to the training data
search problem in object re-ID. The source data pool is 1 order of magnitude
larger than existing re-ID training sets in terms of the number of images and
the number of identities. When the target is AlicePerson [1], from the source
pool, our method (SnP) results in a training set 80% smaller than the source
pool while achieving a similar or even higher re-ID accuracy. The searched
training set is also superior to existing individual training sets such as
Market-1501 [57], Duke [58], and MSMT [48].

The success of a deep learning-based object re-ID relies on one of its
critical prerequisites: the labeled training data. To achieve high accuracy,
typically a massive amount of data needs to be used to train deep learning
models. However, creating large-scale object re-ID training data with manual
labels is expensive. Furthermore, collecting training data that contributes to
the high test accuracy of the trained model is even more challenging. Recent
years have seen a large amount of datasets proposed and a significant increase
in the data size of a single dataset. For example, the RandPerson [40] dataset
has 8000 identities, which is more than $6\times$ larger than the previous
PersonX [40] dataset.

However, these datasets generally have their own dataset bias, making the
model trained on one dataset unable to generalize well to another. For
example, depending on the filming scenario, different person re-ID datasets
generally have biases on camera positions, human races, and clothing style.
Such dataset biases usually lead to model bias, which results in the model’s
difficulty performing well in an unseen filming scenario. To address this,
many try to improve learning algorithms, including domain adaptation and
domain generalization methods [11, 59, 38, 36, 29, 2]. Whereas these
algorithms are well-studied and have proven successful in many re-ID
applications, deciding what kind of data to use for training the re-ID model
is still an open research problem, and has received relatively little
attention in the community. We argue that this is a crucial problem to be
answered in light of the ever-increasing scale of the available datasets.

In this paper, we introduce SnP, a search and pruning solution for sampling an
efficient re-ID training set to a target domain. SnP is designed for the
scenario in that we have a target dataset that does not have labeled training
data. Our collected source pool, in replace, provides suitable labeled data to
train a competitive model. Specifically, given a user-specified budget
(_e.g_., maximum desired data size), we sample a subset of the source pool,
which satisfies the budget requirement and desirably has high-quality data to
train deep learning models. This scenario is especially helpful for deploying
a re-ID system for unknown test environments, as it is difficult to manually
label a training set for these new environments. We note that due to the
absence of an in-distribution training set, the searched data are directly
used for training the re-ID model rather than pre-training.

In particular, we combine several popular re-ID datasets into a source pool,
and represent each image in the pool with features. Those features are
extracted from an Imagenet-pretrained model [42]. The images with features are
stored on the dataserver to serve as a gallery. When there is a query from the
target, we extract the feature of the query image, and search in the gallery
for similar images on a feature level. Specifically, in the search stage, we
calculate feature-level distance, _i.e_., Fréchet Inception Distance (FID)
[18]. Given the constraint of a budget, we select the most representative
samples in the pruning stage, based on the outputs from the search stage. This
limits the size of the constructed training set and enables efficient
training.

Combining search and pruning, we construct a training dataset that empirically
shows significant accuracy improvements on several object re-ID targets,
compared to the baselines. Without budget constraints, our searched training
sets allow higher re-ID accuracy than the complete source pool, due to its
target-specificity. With budget constraints, the pruned training set still
achieves comparable or better performance than the source pool. The proposed
SnP is demonstrated to be superior to random or greedy sampling. We show in
Fig. 1 that the training set constructed by SnP leads to the best performance
on the target compared to the others. We provide discussions on the
specificity of our method and its role in bridging the re-ID domain gap.

##  2 Related Work

Active learning gradually searches over unlabeled data to find samples to be
labeled by the oracle [35]. It is an iterative training process, where data
search is performed at each iteration to train a task model. Our task is
different from active learning. First, active learning is designed to acquire
a training set and train models gradually. This requires multiple real
training processes which are computationally expensive. In comparison, we
directly search the whole training set all at once. Then the searched training
set is used for model training. Second, many active learning methods require
access to the target task model to provide selection metrics, _e.g_.,
uncertainty-based metrics [13, 52, 10, 15]. Our task does not require task
model information, in other words, a real training process, during the process
of the training set search. Thus enabling a fast training data retrial.

Neural data server is the closest inspiring work [51, 35]. They also aim to
search training data all at once from a large database. However, compared with
us, firstly, [51] and [35] are designed for searching pretraining data rather
than direct training data. Such a design is understandable as they are mainly
for the classification task. Searching direct training data require careful
class alignment. In comparison, We are targeting the re-ID task, where its
training set can have a different class from the target, and then be directly
used for training models. Furthermore, [51] and [35] require unsupervised
pretrained experts to measure the domain gap. While we do not require so,
which saves extraction time and simplify the solution.

Transfer learning is a long-standing problem for re-ID tasks, and many
attempts on learning algorithms have been made to reduce the effect of domain
gap [45, 32, 33, 8, 28]. Common strategies contain feature-level [26] and
pseudo-label based [11, 59, 38] domain adaptation, and domain generalization
[36, 29, 2]. In this paper, we focus on training data that is orthogonal to
existing training algorithms. To be shown in experiments, together with some
domain adaptation (_i.e_., pseudo-label) methods, SnP can achieve higher re-ID
accuracy.

Learning to generate synthetic training data. Data simulation is also an
inexpensive alternative to increasing a training set scale while providing
accurate image labels [53, 54, 40, 55, 25]. These methods aim to lower the
domain gap between synthetic data and real data by searching a set of
parameters that control the 3D rendering process [53, 54]. In comparison, our
search is not conducted on predefined parameters but on data directly. This
enables more direct research on how to form a good training set.

Object re-ID has received increasing attention in the past few years, and many
effective systems have been proposed [19, 47, 43, 60]. In this paper, we study
object re-ID datasets rather than algorithms. Depending on the camera
condition, location and environment, existing object re-ID datasets usually
have their own distinct characteristics or bias [40, 54, 39]. We show details
in §3.

Figure 2: Dataset bias in existing object re-ID datasets. (A) Viewpoint
distribution of different re-ID datasets. Each blue dot indicates a sample
filmed from a specific viewpoint. Compared with the bi-modal viewpoint
distribution in Market camera 1, Duke camera 4 has more diverse viewpoints.
(B) Different human races and clothing styles of different person re-ID
datasets. (C) Different vehicle makes in different datasets. For example,
taxis in VeRi are unlikely to be found in CityFlow. (D) Different backgrounds
in different datasets. We show a city background in AliceVehicle versus an
urban background in CityFlow. To tackle such bias in the target domain, we
design an automatic way to generate a training set with similar distribution
or bias.

##  3 Motivation: Tackling Target Bias

Data bias commonly exists in the re-ID datasets (for examples see below) [55,
46, 50, 27], and it becomes problematic when the training and testing have
different biases. Given a target domain with a certain bias, we aim to find a
target-specific training set that has similar distribution or bias. Depending
on the filming scenario, there are four major types of data biases in existing
re-ID datasets. We show examples of each type in Fig. 2.

Viewpoint. Viewpoint bias applies to generic objects, including persons and
vehicles. We visualize the viewpoint distributions of two representative
person re-ID datasets in Fig. 2(A), _i.e_., Market-1501 [57] (denoted as
Market) and Duke-reID [58] (denoted as Duke)111We understand that it is no
longer encouraged to use the Duke dataset. In fact, we are not using it
individually for algorithm design, but moving forward to find solutions to
replace such individual use..

Human races and clothing style. Subject to the places where the data is
collected, identities in the person re-ID datasets can have distinctive
patterns. We show in Fig. 2(B) that the humans in Market and Duke datasets
evince different races and clothing styles.

Vehicle model. Similar to the identity bias (_i.e_., human races and clothing
style) in person re-ID, the vehicle identities in vehicle re-ID also hold
distinct patterns across different datasets. We show examples in Fig. 2(C)
using the VeRi [24] (denoted as VeRi) and the CityFlow [44].

Background. Background bias exists in both person and vehicle re-ID datasets,
which is similar to viewpoint bias. Fig. 2(D) compares the background
difference of images from two different vehicle re-ID datasets.

##  4 Method

Given a target unlabeled dataset, we aim to construct a source labeled dataset
that has minimal data bias inconsistencies with the target, under certain
budget constraints. It induces the model trained on the source to show good
performance on the target. To achieve the construction of the source
(training) dataset, we propose the search and pruning (SnP) framework.

###  4.1 Overview

We denote the target set as
$\mathcal{D}_{T}=\\{({\bm{x}}_{i},y_{i})\\}_{i\in[m_{t}]}$ where $m_{t}$
indicates the number of image-label pairs in the target and
$[m_{t}]=\\{1,2,\dots,m_{t}\\}$. It follows the distribution $p_{T}$, _i.e_.,
$\mathcal{D}_{T}\sim p_{T}$. Let $\mathcal{D}_{S}$ be the source set to be
constructed under a budget $b$. The budget is specified by the number of
identities $n$ and the number of images $m$ allowed in $\mathcal{D}_{S}$,
denoted as $b=(n,m)$. A high budget can lead to an unwanted increase in the
training cost, in terms of either training time or model size.

To construct the training set $\mathcal{D}_{S}$, we create a source pool
$\mathcal{S}$, which is a collection of multiple object re-ID datasets. It is
represented as
$\mathcal{S}=\mathcal{D}_{S}^{1}\bigcup\mathcal{D}_{S}^{2}\dots\bigcup\mathcal{D}_{S}^{K}$.
Here each $\mathcal{D}_{S}^{k}$, $k\in[K]$, indicates the $k$-th source re-ID
dataset. Given the source pool, we firstly build a subset ${\mathbf{S}}^{*}$
of $\mathcal{S}$ regardless of the budget constraint. Let $h_{\mathbf{S}}$ be
a model $h$ trained on an arbitrary dataset ${\mathbf{S}}$. The prediction
risk of $h_{\mathbf{S}}$ on the test sample $\bm{x}$ with ground truth label
$y$ is computed as $\ell(h_{\mathbf{S}}({\bm{x}}),y)$. We build
${\mathbf{S}}^{*}$ by ensuring that the model $h_{{\mathbf{S}}^{*}}$ has
minimized risk on $\mathcal{D}_{T}$, _i.e_.,

${\mathbf{S}}^{*}=\operatorname*{arg\,min}_{\mathbf{S}\in
2^{\mathcal{S}}}\mathbb{E}_{{\bm{x}},y\sim
p_{T}}[\ell(h_{\mathbf{S}}({\bm{x}}),y)].$ (1)

We apply target-specific search in §4.3 to construct ${\mathbf{S}}^{*}$.

It can be seen that the construction of ${\mathbf{S}}^{*}$ does not take the
budget constraint $b=(n,m)$ into consideration, which is otherwise important
in reality. Therefore, we build the training set $\mathcal{D}_{S}$ by pruning
${\mathbf{S}}^{*}$ to comprise no more than $n$ identities and no more than
$m$ images. Details of the budgeted pruning process are introduced in §4.4.

Figure 3:  Relationships between the domain gap (measured using FID), the
number of ID and the rank-1 accuracy on the target. Top: correlations when
AlicePerson [1] is targeted. Bottom: correlations when AliceVehicle [1] is
targeted. The Pearson correlation is used to measure the relationship between
them. (A) FID _vs_. the rank-1 accuracy. They have a relatively strong
negative correlation $(\leq-0.636)$. (B) The number of ID _vs_. the rank-1
accuracy. There exists a positive correlation but such a correlation is not
stable. (C) FID _vs_. number of ID. The correlation is weak between them. (D)
The joint influence of FID and the number of ID on rank-1 accuracy. The top
left corner, _i.e_., training sets that have low FID scores and a large number
of IDs have high rank-1 accuracy on the target.

###  4.2 Correlation Study

In order to know how to obtain ${\mathbf{S}}^{*}$, we conduct the correlation
study to learn the relationships between the dataset bias differences (_i.e_.,
domain gap measured in measured in FID [18]), the number of IDs and the
training set quality (_i.e_., rank-1 test accuracy with the model trained on
the such training set). Shown in Fig. 3, in each subfigure, each point
represents a training set, which is clustered from the source pool. For each
training set, we calculate its domain gap to the target domain, count its
number of IDs, and evaluate the rank-1 accuracy. We use the Pearson
correlation coefficient ($\gamma$) [5] to measure the correlation between
them. The Pearson correlation coefficients range from $[-1,1]$. A value closer
to -1 or 1 indicates a stronger negative or positive correlation,
respectively, and 0 implies no correlation.

From this Fig. 3(A), we observe a relatively strong negative correlation
between domain gap and rank-1 accuracy. This indicates minimizing the domain
gap between the source and target is highly likely to improve training set
quality, _i.e_., test set rank-1 accuracy. From this Fig. 3(B), we observe a
positive but unstable correlation between the number of ID and the rank-1
accuracy. For example, when AlicePerson is targeted, they have a relatively
strong positive correlation $(0.720)$. However, such correlation is only
$0.383$ when AliceVehicle is targeted. Fig. 3(C) shows the correlation between
FID and the number of ID is weak. They are independent factors that influence
training set quality. Fig. 3(D) shows the joint influence of FID and the
number of ID on the training set quality. The top left corner, _i.e_.,
training sets that have a low domain gap to the target and a large number of
IDs are of high quality, thereby can train a model that has higher rank-1
accuracy on the target.

###  4.3 Target-specific Subset Search

The theory of domain adaptation [3] states that:

$\varepsilon_{T}(h)<\varepsilon_{S}(h)+\frac{1}{2}d_{\mathcal{H}\Delta\mathcal{H}}({\mathbf{S}},{\mathcal{D}_{T}}).$
(2)

Here $h\in\mathcal{H}$ represents the hypothesis function (_i.e_., the model).
$\varepsilon_{T}(h)$ is the risk of model $h$ on the target set
$\mathcal{D}_{T}$, while $\varepsilon_{S}(h)$ is its risk on the source set
${\mathbf{S}}$.
$d_{\mathcal{H}\Delta\mathcal{H}}({\mathbf{S}},{\mathcal{D}_{T}})$ is the
unlabelled $\mathcal{H}\Delta\mathcal{H}$ divergence [3] between
${\mathbf{S}}$ and ${\mathcal{D}_{T}}$. Equation 2 shows that the target risk
$\varepsilon_{T}(h)$ is upper bounded by
$d_{\mathcal{H}\Delta\mathcal{H}}({\mathbf{S}},{\mathcal{D}_{T}})$.

In the common practice of feature-level domain adaptation, the source training
set $\mathbf{S}$ is fixed while the joint feature extraction model is used to
minimize $d_{\mathcal{H}\Delta\mathcal{H}}(\mathbf{S},\mathcal{D}_{T})$ [26].
In our design, the feature extraction model is fixed instead. To minimize
$\varepsilon_{T}(h)$, the problem is reformulated as

${\mathbf{S}}^{*}=\operatorname*{arg\,min}_{{\mathbf{S}}\in
2^{\mathcal{S}}}d_{\mathcal{H}\Delta\mathcal{H}}({\mathbf{S}},{\mathcal{D}}_{T}).$
(3)

Generally,
$d_{\mathcal{H}\Delta\mathcal{H}}({\mathbf{S}}^{*},\mathcal{D}_{T})$ is
difficult to compute, but many alternatives exist in the literature [26]. We
use Fréchet Inception Distance (FID) [18], which is defined as:

$\mbox{FID}({\mathbf{S}}^{*},\mathcal{D}_{T})=\left\|\bm{\mu}_{s}-\bm{\mu}_{t}\right\|^{2}_{2}+\operatorname{Tr}(\bm{\Sigma}_{s}+\bm{\Sigma}_{t}-2(\bm{\Sigma}_{s}\bm{\Sigma}_{t})^{\frac{1}{2}}).$
(4)

In Eq. 4, $\bm{\mu}_{s}\in\mathbb{R}^{d}$ and
$\bm{\Sigma}_{s}\in\mathbb{R}^{d\times d}$ are the mean and covariance matrix
of the image descriptors of ${\mathbf{S}}^{*}$, respectively. $\bm{\mu}_{t}$
and $\bm{\Sigma}_{t}$ are those of $\mathcal{D}_{T}$. $\operatorname{Tr}(.)$
represents the trace of a square matrix. $d$ is the dimension of the image
descriptors. Consequently, the objective function is reduced as,

${\mathbf{S}}^{*}=\operatorname*{arg\,min}_{{\mathbf{S}}\in
2^{\mathcal{S}}}\mbox{FID}({\mathbf{S}},\mathcal{D}_{T}).$ (5)

We build ${\mathbf{S}}^{*}$ with the greedy algorithm below.

Firstly, we divide the entire dataset $\mathcal{S}$ into $J$ clusters
$\\{{\mathbf{S}}^{1},\cdots,{\mathbf{S}}^{J}\\}$, as shown in Fig. 4 (A).
Specifically, we average all image descriptors that belong to the same
identity, and use this ID-averaged descriptor to represent all corresponding
images. Afterwards, we cluster the ID-averaged features into $J$ groups using
the k-means method [22]. Each subset ${\mathbf{S}}^{j}$, $j\in[J]$, is
composed of all images with the corresponding IDs in that group. Secondly, we
calculate the FID between each subset ${\mathbf{S}}^{j}$ and the target
$\mathcal{D}_{T}$, and sort
$\\{\mbox{FID}({\mathbf{S}}^{j},\mathcal{D}_{T})\\}_{j\in[J]}$ in ascending
order. To build ${\mathbf{S}}^{*}$, we keep adding the subsets with lower FID
to ${\mathbf{S}}^{*}$ until $\mbox{FID}({\mathbf{S}}^{*},\mathcal{D}_{T})$
stops to decrease. This indicates that the constructed ${\mathbf{S}}^{*}$
holds the minimum FID to the target set. Algorithm 1 summarizes the above
procedures. We empirically demonstrate in Fig. 5 that, the subset
${\mathbf{S}}^{*}$ with the minimum
$\mbox{FID}({\mathbf{S}}^{*},\mathcal{D}_{T})$ results in the model to produce
highest accuracy on the target dataset.

Figure 4: Workflow of the proposed SnP method. We are given sources composed
of $K$ existing datasets. From these sources, we aim to construct a training
set, which satisfies the budget of no more than $n$ IDs and $m$ images. To
achieve this, we perform (A) target-specific subset search to obtain a subset
$\mathbf{S}^{*}$ with similar distributions to the target, then perform (B)
budgeted pruning to select $n$ IDs and $m$ representative images, forming the
final training set.  Figure 5: Performance of constructed training set at
different iterations on the target set. We greedily add clustered subset to
form ${\mathbf{S}}^{*}$ which has the smallest domain gap to the target
$\mathcal{D}_{T}$. During this process, we have relatively high FID and low
accuracy at (A). Gradually, we reach situation (B) of the smallest domain gap
and highest accuracy. After (B), adding subsets leads to an increase in the
domain gap, and the accuracy drops, _e.g_., (C). To study the correlation
between FID and mAP during the search process, we hope to eliminate the impact
of dataset size. Thus we use the same number of IDs from the searched set
(_i.e_., 2% ID).

###  4.4 Budget-constrained Pruning

Using the target-specific subset search, we construct a candidate training set
${\mathbf{S}}^{*}$. Yet, it can violate the budget constraint of $b=(n,m)$,
which prefers the training set to include no more than $n$ identities and no
more than $m$ images. Let
$\mathcal{Y}({\mathbf{S}}^{*})=\\{y^{1},y^{2},\dots,y^{a}\\}$, be the set of
unique identities in ${\mathbf{S}}^{*}$, and ${\bm{s}}(y^{i})$, $i\in[a]$ be
the set of all images with identity $y^{i}$. Generally, we have $a\geq n$. To
get the training set $\mathcal{D}_{S}$ under budget $b$, we randomly sample a
subset ${\bm{y}}$ of $n$ identities from $\mathcal{Y}$. All images with
identities in ${\bm{y}}$ are combined to form a subset
$\hat{\mathbf{s}}=\\{{\bm{s}}(y^{i})|y^{i}\in{\bm{y}}\\}$. We also initialize
$\mathcal{D}_{S}$ by random sampling a seed image from each
${\bm{s}}(y^{i}),~{}y^{i}\in{\bm{y}}$. This guarantees $\mathcal{D}_{S}$ to
cover all the identities in the subset $\hat{\mathbf{s}}$.

Suppose the number of images in $\hat{\mathbf{s}}$ is larger than $m$. We
construct $\mathcal{D}_{S}$ by sampling images iteratively from
$\hat{\mathbf{s}}$ until $|\mathcal{D}_{S}|=m$. To ensure similar performance
between the model trained on $D_{S}$ and the model trained on
$\hat{\mathbf{s}}$, we minimize the risk differences between them,

$\mathcal{D}_{S}=\operatorname*{arg\,min}_{\mathcal{D}_{S}\in
2^{\hat{\mathbf{s}}}}\big{|}L(h_{\hat{\mathbf{s}}}({\bm{x}}),y)-L(h_{\mathcal{D}_{S}}({\bm{x}}),y)\big{|}.$
(6)

$L(h_{\hat{\mathbf{s}}}({\bm{x}}),y)$ and $L(h_{\mathcal{D}_{S}}({\bm{x}}),y)$
are the respective risks of model $h$ on the dataset ${\hat{\mathbf{s}}}$ and
$\mathcal{D}_{S}$. For explicity, we define the risk of model $h$ on an
arbitrary dataset $\mathbf{S}$ as

$L(h_{{\mathbf{S}}}({\bm{x}}),y)=\frac{1}{|{\mathbf{S}}|}\sum_{({\bm{x}}_{i},y_{i})\in{\mathbf{S}}}\ell(h_{{\mathbf{S}}}({\bm{x}}_{i}),y_{i}).$
(7)

As in Eq. 1, $\ell(h_{{\mathbf{S}}}({\bm{x}}_{i}),y_{i})$ is the risk on
individual samples.

From the theory of core set [34], if $\mathcal{D}_{S}$ is the $\delta_{s}$
cover of the set $\hat{\mathbf{s}}$ and shares the same number of classes with
$\hat{\mathbf{s}}$, the risk difference between model $h_{\hat{\mathbf{s}}}$
and $h_{\mathcal{D}_{S}}$ is bounded by

$\big{|}L(h_{\hat{\mathbf{s}}}({\bm{x}}),y)-L(h_{\mathcal{D}_{S}}({\bm{x}}),y)\big{|}\leq\mathcal{O}(\delta_{s})+\mathcal{O}(\frac{1}{\sqrt{|\mathcal{D}_{S}|}}).$
(8)

Algorithm 1 Target-specific Subset Search

1:Input: Source pool $\mathcal{S}$, target set $\mathcal{D}_{T}$, and the
number of clusters $J$.

2:Begin:

3:Cluster
($\mathcal{S},J)\longrightarrow\\{{\mathbf{S}}^{1},\cdots,{\mathbf{S}}^{J}\\}$

4:${\mathbf{s}}=\emptyset,\epsilon=\infty,{\mathbf{S}}^{*}=\emptyset$

5:$\mathcal{J}=\mbox{argsort}\big{(}\\{\mbox{FID}({\mathbf{S}}^{j},{\mathcal{D}_{T}})\\}_{j\in[J]}\big{)}$
$\triangleright$ Ascending

6:for $j$ in $\mathcal{J}$ do

7: ${\mathbf{s}}={\mathbf{s}}\mathop{\cup}{\mathbf{S}}^{j}$

8: if $\mbox{FID}({\mathbf{s}},T)<\epsilon$ then

9: $\epsilon=\mbox{FID}({\mathbf{s}},{\mathcal{D}}_{T})$

10: ${\mathbf{S}}^{*}={\mathbf{s}}$

11:return ${\mathbf{S}}^{*}$

$\delta_{s}$ is the radius of the cover, and $\mathcal{O}(\delta_{s})$ is a
polynomial function over $\delta_{s}$. The problem can be reduced as a
K-center problem [12] by optimizing $\mathcal{O}(\delta_{s})$. We apply a
2-approximation algorithm [49] to iteratively find optimal samples in
${\hat{\mathbf{s}}}$ and add to $\mathcal{D}_{S}$. Specifically, each optimal
sample ${\mathbf{z}}^{*}$ is computed as

${\mathbf{z}}^{*}=\operatorname*{arg\,max}\limits_{{\mathbf{z}}_{i}\in{\hat{\mathbf{s}}}\setminus\mathcal{D}_{S}}\min_{{\mathbf{z}}_{j}\in\mathcal{D}_{S}}\|f({\bm{x}}_{i})-f({\bm{x}}_{j})\|_{2},$
(9)

where ${\mathbf{z}}=({\bm{x}},y)$, and $f({\bm{x}})$ represents the descriptor
of an image ${\bm{x}}$. Equation 9 relates to the furthest point sampling
method [9], which enables the most representative samples from a dataset to be
selected. We summarize the prunning process in Algorithm 2.

###  4.5 Discussion

What to prune first, ID or image? In our design, we select the IDs first and
then images, aiming to build a dataset that has a small domain gap to target
and is meanwhile in small-scale. Selecting the images first and then IDs is
possible. However, it leads to a significant increase in the time complexity.
As shown in Algorithm 2, the most time-consuming part of our algorithm is the
FPS for finding image core sets, which takes
$\mathcal{O}(m|\hat{\mathbf{s}}|)$. If we select images first, the time
complexity becomes $\mathcal{O}(m|{\mathbf{S}}^{*}|)$, which is significantly
higher than $\mathcal{O}(m|\hat{\mathbf{s}}|)$ as
$|{\mathbf{S}}^{*}|\gg|\hat{\mathbf{s}}|$.

Is SnP applicable to tasks beyond object re-ID? It is possible to apply our
search and pruning (SnP) framework to other tasks, _e.g_., classification.
Yet, achieving this requires the SnP algorithm to be partially redesigned. The
reason is that, in object re-ID, the major domain gap comes from the class
difference, _i.e_., IDs. However, such a gap does not exist in the
classification tasks as the train/val/test datasets always share the same
classes. Therefore, our current design of selecting similar IDs for similar
distributions is not directly applicable, and has to be adapted.

##  5 Experiment

We evaluate the effectiveness of SnP on person re-ID and vehicle re-ID. In
both tasks, given target data, we use the SnP pipeline to find a training set
that has a similar distribution to the target and simultaneously meets a
budget.

###  5.1 Source and Target Datasets

Person re-ID. We create the source pool for person re-ID using $10$ public
datasets, including Market [57], Duke [58], MSMT17 [48] (denoted as MSMT),
CUHK03 [21], RAiD [6], PersonX [40], UnrealPerson [55], RandPerson [46], PKU-
Reid [31] and VIPeR [4]. Those datasets cover both synthetic and real-world
data. Ten re-ID datasets constitute a source pool that contains in total of
15,060 IDs and 399,715 images.

We use two real-world datasets as targets: AlicePerson [1] and Market [57].
Specifically, AlicePerson is specially designed for domain adaptation as it
contains unlabeled training images. Note that in Market, the label for its
training set is not be used. When Market is the target, Market training set is
excluded from the source pool.

Algorithm 2 Budgeted Pruning

1:Input: Initial source set ${\mathbf{S}}^{*}$, budget $b=(n,m)$.

2:Begin:

3:${\bm{y}}=\mathcal{U}(\mathcal{Y}({\mathbf{S}}^{*}),n)$ $\triangleright$
Sample $n$ IDs

4:$\hat{\mathbf{s}}=\\{{\bm{s}}(y_{i})|y_{i}\in{\bm{y}}\\}$

5:$\mathcal{D}_{S}=\\{\mathcal{U}({\mathbf{s}}(y^{i}),1)|y_{i}\in{\bm{y}}\\}$

6:if $|\hat{\mathbf{s}}|>m$ then $\triangleright$ Sample $m$ images

7: repeat

8:
${\mathbf{z}}^{*}=\operatorname*{arg\,max}\limits_{{\mathbf{z}}_{i}\in\hat{\mathbf{s}}\setminus\mathcal{D}_{S}}\min\limits_{{\mathbf{z}}_{j}\in\mathcal{D}_{S}}\|{\bm{x}}_{i}-{\bm{x}}_{j}\|_{2}$

9: $\mathcal{D}_{S}=\mathcal{D}_{S}\cup\\{{\mathbf{z}}^{*}\\}$

10: until $|\mathcal{D}_{S}|=m$

11:else

12: $\mathcal{D}_{S}=\hat{\mathbf{s}}$

13:return $\mathcal{D}_{S}$

Vehicle re-ID. For vehicle re-ID, we create the source pool by combining $8$
datasets, which are VeRi [24], CityFlow [44], VehicleID [23], VeRi-Wild [27],
VehicleX [53], Stanford Cars [20], PKU-vd1 [50] and PKU-vd2 [50]. It totally
has 156,512 IDs and 1,284,272 images.

AliceVehicle [1] and VeRi [24] are separately used as the target domains.
Similar to AlicePerson, AliceVehicle is also designed for domain adaptation.
When VeRi is the target, the VeRi training set is excluded from the source
pool.

Evaluation protocol. For object re-ID, we use mean average precision (mAP) and
cumulative match curve (CMC) scores to measure system accuracy, _e.g_.,
“rank-1” and “rank-5”. “rank-1” denotes the success rate of finding the true
match in the first rank, and “rank-5” means the success rate of ranking at
least one true match within top-5 matches.

Table 1: Comparing different methods in training data search: SnP, random sampling, and greedy sampling. We set the budget as $2\%$, $5\%$, and $20\%$ of the total source IDs. We use four targets: AlicePerson, Market, AliceVehicle and VeRi. The task model is IDE [56]. FID, rank-1 accuracy (%), and mAP (%) are reported.  Training data | Person re-ID targets | Vehicle re-ID targets
---|---|---
| AlicePerson | Market | AliceVehicle | VeRi
|  FID$\downarrow$ |  R1$\uparrow$ |  mAP$\uparrow$ |  FID$\downarrow$ |  R1$\uparrow$ |  mAP$\uparrow$ |  FID$\downarrow$ |  R1$\uparrow$ |  mAP$\uparrow$ |  FID$\downarrow$ |  R1$\uparrow$ |  mAP$\uparrow$
Source pool | 81.67 | 38.96 | 17.62 | 37.53 | 55.55 | 30.62 | 43.95 | 30.47 | 14.64 | 24.39 | 55.90 | 25.03
Searched | 60.95 | 48.19 | 25.51 | 30.42 | 61.49 | 34.40 | 23.44 | 46.78 | 25.46 | 17.92 | 74.13 | 41.71
Pruned |  | Random | 80.06 | 23.67 | 9.80 | 39.03 | 40.77 | 19.54 | 45.97 | 31.35 | 12.87 | 24.68 | 67.16 | 26.48
2% IDs |  Greedy [51] | 61.78 | 33.22 | 15.10 | 34.43 | 42.19 | 19.35 | 38.51 | 31.82 | 12.91 | 29.53 | 66.57 | 26.24
| SnP | 60.42 | 38.23 | 18.17 | 31.29 | 44.80 | 21.65 | 23.48 | 38.48 | 17.79 | 17.70 | 69.96 | 31.10
| Random | 81.41 | 33.16 | 14.49 | 39.65 | 47.39 | 23.97 | 44.52 | 36.36 | 14.17 | 25.27 | 70.38 | 30.44
5% IDs |  Greedy [51] | 61.01 | 44.63 | 22.81 | 31.63 | 49.17 | 24.77 | 32.48 | 41.32 | 17.77 | 26.06 | 71.23 | 32.53
| SnP | 60.64 | 47.26 | 25.45 | 30.37 | 51.96 | 26.56 | 23.92 | 44.58 | 21.79 | 18.09 | 72.05 | 36.01
| Random | 79.33 | 38.10 | 17.79 | 38.63 | 53.15 | 28.39 | 43.90 | 40.89 | 18.13 | 24.43 | 68.71 | 34.10
20% IDs |  Greedy [51] | 63.15 | 46.74 | 22.65 | 32.42 | 53.53 | 28.19 | 24.15 | 44.58 | 22.82 | 18.74 | 71.04 | 38.07
| SnP | 61.87 | 47.20 | 25.36 | 30.58 | 57.14 | 33.09 | 23.47 | 46.07 | 25.24 | 17.93 | 73.48 | 40.75
|  |  |  |  |  |  |  |  |  |  |  |  |  |
Table 2: The effectiveness of the target-specific subset search. mAP (%) and CMC scores are reported. “R1” and “R5” denote rank-1 accuracy (%) and rank-5 accuracy (%), respectively. | AlicePerson |  | AliceVehicle
---|---|---|---
Training data | R1 | R5 | mAP | Training data | R1 | R5 | mAP
Market [57] | 32.89 | 52.54 | 16.06 |  VeRi [24] | 30.69 | 43.66 | 11.05
Duke [58] | 23.27 | 41.13 | 8.59 |  CityFlow [44] | 23.95 | 36.00 | 7.45
MSMT [48] | 31.29 | 52.79 | 15.08 |  VehicleID [23] | 16.3 | 29.13 | 4.73
PersonX [40] | 16.08 | 27.42 | 6.41 |  VehicleX [53] | 18.85 | 32.18 | 8.89
Source pool | 38.96 | 57.48 | 17.62 | Source pool | 30.47 | 48.33 | 14.64
Searched | 48.19 | 67.57 | 25.51 | Searched | 46.78 | 64.41 | 25.46
|  |  |  |  |  |  |

###  5.2 Results

SnP framework _vs._ random sampling and greedy sampling. Given a target
domain, the SnP framework allows us to construct a budgeted dataset with a
similar distribution. We show the superiority of SnP framework in Table 1.
After sampling target-specific data with SnP, we train the subsequent re-ID
model with the sampled target-specific data only. In Table 1, we compare the
sampled dataset with those created by greedy sampling and random sampling.
Random sampling means we randomly select IDs according to the uniform
distribution. For greedy sampling, we reproduce [51]. Specifically, We assign
each ID a score, which is calculated using FID. IDs will then be selected
greedily from the lowest FID value to the highest FID value.

From the results shown in Table 1 and Table 3, we observe that training sets
selected using SnP achieve consistently lower domain gap to the target and
higher re-ID accuracy than those found by random sampling and greedy sampling.
For example, when creating a training set with only 2% source IDs for
AlicePerson as the target, SnP results in -19.64 and -1.36 improvement in FID
value, and +14.56% and +5.01% improvement in rank-1 accuracy over using random
sampling and greedy sampling, respectively. When sampling training set with 2%
of the source IDs for AliceVehicle as the target, the rank-1 accuracy
improvement is +7.13% and +6.66%, respectively.

Table 3: The superiority of SnP over random sampling and greedy sampling, when different direct transfer and pseudu-label re-ID models are used. We report accuracy when $2\%$ IDs are selected for target AlicerPerson. Notations and evaluation metrics are the same as those in the previous table.  Type | Model | Training data | R1 | R5 | mAP
---|---|---|---|---|---
Direct Transfer | IDE [56] | Random | 23.67 | 42.32 | 9.80
Greedy [51] | 33.22 | 54.45 | 15.10
SnP | 38.23 | 58.40 | 18.17
PCB [41] | Random | 24.79 | 41.60 | 9.91
Greedy [51] | 29.07 | 46.01 | 12.59
SnP | 32.43 | 49.90 | 15.18
TransReid [17] | Random | 52.04 | 69.73 | 28.47
Greedy [51] | 63.73 | 80.24 | 41.88
SnP | 64.31 | 80.46 | 42.74
Pseudo -labeling | UDA [37] | Random | 32.17 | 54.67 | 15.32
Greedy [51] | 36.47 | 52.06 | 17.34
SnP | 41.41 | 55.74 | 20.47
MMT [14] | Random | 35.94 | 51.91 | 17.25
Greedy [51] | 38.64 | 56.48 | 21.18
SnP | 43.36 | 60.38 | 23.34
|  |  |  |  |
Figure 6: Composition statistics and images samples of searched training sets.
For each subfigure (A), (B), (C) and (D), the columns on the left presents
unlabeled target samples; columns the middle provide samples of the searched
training set; the pie chart Community-verified icon Verified on the right
shows composition statistics of the searched training set.  Figure 7:
Comparing FPS with random sampling. The search step provides us with 2% of the
source IDs. We further select various ratios of images from these IDs. Four
different targets are used, and rank-1 accuracy is the evaluation metric.
Score is averaged over three runs.

Effectiveness of the search step. We analyze this step in Table 1 and Table 2.
In this search process that poses no limit on the number of IDs and images, we
aim to identify and merge clusters of source identities that exhibit similar
distributions with the target. We show the searched datasets contribute to
improved accuracy over the entire data pool. For example, for AlicePerson, we
observe a +9.23% improvement in rank-1 accuracy over the entire data pool. We
further show the searched data is superior to individual training sets in
Table 2. For example, when AliceVehicle is our target, we show our searched
dataset results in +16.09%, +22.83%, +30.48%, +27.93% higher rank-1 accuracy
than VeRi, CityFlow, VehicleID, and VehicleX, respectively.

Of note, accuracy under this application scenario is usually lower than that
produced by in-distribution training sets. This difference is understandable,
because searched data have a relatively lower resemblance to the target data
compared with in-distribution training sets. That said, annotating in-
distribution training sets is usually expensive, especially considering the
complex, specific and ever-changing target environments, where creating a
training set on-the-fly with good performance is of practical value.

Effectiveness of the pruning step is analyzed in Table 1 and Fig. 7. Pruning
aims to find a subset that has no more than $n$ IDs and $m$ images. From Table
1 and Fig. 7, admittedly, the pruning of both IDs and images will lead to an
accuracy decrease. For example, when the target is AlicePerson, if we select
2% IDs, there is a -9.23% decrease in rank-1 accuracy. From Fig. 7, when the
target is AlicePerson, if we further select 40% images, there is a -9.96%
decrease in rank-1 accuracy. However, even though only 2% IDs are used, rank-1
accuracy obtained from the pruned training data is still competitive over the
source pool, which is just -0.73% lower than the source pool. It shows the
pruning method significantly reduces the training set scale while being able
to train a model of reasonable accuracy.

Composition of searched training sets. We visualize four examples in in Fig.
6. It is clear that searched training sets have different compositions under
different targets. If we use AlicePerson as the target, in the searched
training set, images from Market and Duke take up 68% and 26%, respectively.
In comparison, when using Market as the target, the resulting training set
contains, 43% images from UnrealPerson, and 34% from MSMT. An interesting
observation is that synthetic data (UnrealPerson) has a major role under
Market as the target. It demonstrates the potential use of synthetic data for
real-world target domains.

Comparison between FPS and random sampling. Both can be used for sampling
images resulting from the search step. In Fig. 7, we sample different ratios
of the images resulting from the search step. We observe FPS is consistently
superior to random sampling, under different selection ratios and targets.
Improvement of FPS over random sampling first increase and then decreases,
with peak improvement happening at the 30-60% ratio.

##  6 Conclusion

This paper studies the training data set search problem, for object re-ID
applications. Under a certain budget, we aim to find a target-specific
training set that gives a competitive re-ID model. We show our method is
overall superior to existing strategies such as random sampling and greedy
sampling in terms of accuracy on the target domain. We analyze various
components in the SnP system and find them to be stable under various source
pools and targets. We also point out the correlation between domain gap,
dataset size, and training set quality, and would like to further study the
data-centric problems in the community.

##  7 Acknowledgement

This work was supported in part by the ARC Discovery Early Career Researcher
Award (DE200101283), the ARC Discovery Project (DP210102801), Oracle Cloud
credits, and related resources provided by Oracle for Research.

##  8 Experimental Details

SnP settings. For a dataset denoted as a target domain (_e.g_., Market and
VeRi), their unlabeled training sets are used as the search target. For image
feature extraction, we use IncepetionV3 [42] pretrained on ImageNet [7].

Task model configuration. We have two types of models: direct transfer models
and pseudo-label based models. For direct transfer, we use multiple task
models, including ID-discriminative embedding (IDE) [56], the part-based
convolution (PCB) [41], and TransReid [17]. For IDE, we adopt the strategy
from [30] which uses ResNet-50 [16], adds batch normalization and removes ReLU
after the final feature layer. For PCB, we use the ResNet-50 backbone and
vertically partition an image into six equal horizontal parts. For pseudo-
label methods, we use UDA [37] and MMT [14]. The unlabeled target training set
(_e.g_., AlicePerson training set) is used for pseudo-label model training.
Note that when implementing these task models, we use their official
implementation with default hyperparameters including learning rate and
training epochs.

Computation Resources. We run experiments on an 8-GPU machine and an oracle
cloud machine. The 8-GPU machine has 8 NVIDIA 3090 GPUs and its CPU is AMD
EPYC 7343 Processor. For the oracle cloud machine, it has 2 NVIDIA A10 GPUs
and its CPU is Intel Platinum 8358 Processor. For both the 3090 machine and
the oracle cloud machine, we use PyTorch version 1.12.1+cu116.

Table 4: Generalization comparison of various training sets: those generated by random sampling, greedy sampling, and SnP, as well as the source data pool. AlicePerson is used as the target. We directly test the trained models on Market, Duke, MSMT and report the individual and the average rank-1 accuracy (%) and mAP (%). Train. set | Market | Duke | MSMT | Average | AlicePerson
---|---|---|---|---|---
R1 | mAP | R1 | mAP | R1 | mAP | R1 | mAP | R1 | mAP
Sour. pool | 67.36 | 43.16 | 62.39 | 41.15 | 35.72 | 15.40 | 55.16 | 33.23 | 38.96 | 17.62
Random | 6.44 | 1.92 | 38.29 | 18.75 | 19.90 | 6.42 | 21.54 | 9.03 | 23.67 | 9.80
Greedy | 74.11 | 51.98 | 26.08 | 13.27 | 7.32 | 2.13 | 35.83 | 22.46 | 33.22 | 15.10
SnP | 74.32 | 51.03 | 27.06 | 13.43 | 8.19 | 2.28 | 36.52 | 22.24 | 38.23 | 18.17
|  |  |  |  |  |  |  |  |  |
Table 5: Comparison of different source pools. A: Market + Duke + MSMT. B: A + UnrealPerson. C: B + RandPerson + PersonX. All: C + CUHK03 + RAiD + VIPeR + PKU-Reid. SnP is consistently effective for different pools. 2% IDs are selected from the source pool. Notations and evaluation metrics are the same as those in the previous table.  Search method | Pool A | Pool B | Pool C | All
---|---|---|---|---
R1 | mAP | R1 | mAP | R1 | mAP | R1 | mAP
Random | 11.47 | 4.01 | 21.56 | 8.61 | 23.60 | 9.39 | 23.67 | 9.80
Greedy | 8.04 | 2.81 | 18.66 | 7.63 | 24.26 | 9.56 | 33.22 | 15.10
SnP | 14.17 | 4.47 | 25.44 | 10.16 | 36.32 | 17.22 | 38.23 | 18.17
|  |  |  |  |  |  |  |

##  9 Further Analysis

Figure 8: Impact of the number of clusters $J$ to the domain gap (FID) between
searched and target (left), and re-ID accuracy (right). AlicePerson is
targeted, and the IDE [56] model is trained.

Generalization analysis of the training set generated by SnP. In Table 4, we
directly apply the re-ID model obtained from the AlicePerson-specific training
set to various test sets, such as Market, Duke, and MSMT. Compared with the
model trained on the source pool, our target-specific model has higher
accuracy on the target test set, and lower accuracy on other domains (MSMT for
example shown in Table 4). It demonstrates the generated training set is
target-specific, improving re-ID accuracy on the given domain, while its
generalization ability is weakened. But still, its application is promising
given its target-specificity strength.

Analysis of different source pools. We compare various source pools when
AlicerPerson is the target domain. From Table 5, we observe that our method
gives very stable accuracy when using different source pools. In comparison,
the compared methods, i.e., random sampling and greedy sampling, as much less
stable. For example, random sampling performs well under Pool A which only
contains real-world images and might be similar to the target domain. But it
is much poorer under Pool C which has more synthetic data, meaning a larger
domain gap from the target.

Analysis of hyperparameter $J$. In Fig. 8, we show the increase of the number
of clusters $J$ lowers the domain gap between the target and searched training
set and generally increases the task accuracy. It reaches saturation after
$J=20$. In this paper, we use $J=50$ in all setups.

Correlation between the number of images and training set quality. While the
correlation between the number of IDs and training set quality has been shown
in Fig. 3. We show that when the number of ID is fixed, the correlation
between the number of images and the rank-1 accuracy in Fig. 7. when we have a
fixed number of IDs, the increase in the number of images brings a significant
increase in rank-1 accuracy.

Figure 9: The composition (tree map) of the source pool for the training set
search. (Left:) Person re-ID datasets were collected for constructing the
source pool. (Right:) Vehicle re-ID datasets. For both person re-ID and
vehicle re-ID, we use synthetic data and real data. Each innermost rectangle
represents a publicly available object re-ID dataset. The relative size of
rectangles denotes the relative image size of datasets. The relative color
shows the domain gap (measured in FID) value to the target test set. In person
re-ID, the target for calculating the domain gap is AlicePerson [1]. In
vehicle re-ID, the target for calculating the domain gap is AliceVehicle [1].

##  10 Source Pool Details

We show the composition (tree map) of the source pool for the training set
search in Fig. 9. On the left of Fig. 9, for person re-ID, we summarize the
details of each dataset in rectangles and show some examples. The size of each
rectangle refers to the number of images in the dataset, while the color of
the rectangle indicates the domain gap of that dataset to the target set.
Regarding the target set in person re-ID, we use AlicePerson [1] for
calculating the FID.

We summarize the details of vehicle re-ID datasets in the right of Fig. 9. The
size and color of each rectangle carry the same meanings as those on the left
of Fig. 9. The AliceVehicle [1] is used as the target set for calculating FID.

The datasets we use for the source pool are standard benchmarks, which are
publicly available. We list their open-source as follows. For person re-ID:

Market [57] https://zheng-lab.cecs.anu.edu.au/Project/project_reid.html;

Duke [58] https://exposing.ai/duke_mtmc/;

MSMT17 [48] http://www.pkuvmc.com/publications/msmt17.html;

CUHK03 [21] https://www.ee.cuhk.edu.hk/~xgwang/CUHK_identification.html;

RAiD [6] https://cs-people.bu.edu/dasabir/raid.php;

PersonX [40] https://github.com/sxzrt/Instructions-of-the-PersonX-dataset;

UnrealPerson [55] https://github.com/FlyHighest/UnrealPerson;

RandPerson [46] https://github.com/VideoObjectSearch/RandPerson;

PKU-Reid [31] https://github.com/charliememory/PKU-Reid-Dataset;

VIPeR [4] https://vision.soe.ucsc.edu/node/178.

For vehicle re-ID, we also list their open-source:

VeRi [24] https://github.com/JDAI-CV/VeRidataset;

CityFlow [44] https://www.aicitychallenge.org/;

VehicleID [23] https://www.pkuml.org/resources/pku-vehicleid.html;

VeRi-Wild [27] https://github.com/PKU-IMRE/VERI-Wild;

VehicleX [53] https://github.com/yorkeyao/VehicleX;

Stanford Cars [20] http://ai.stanford.edu/~jkrause/cars/car_dataset.html;

PKU-vd1 [50] https://www.pkuml.org/resources/pku-vds.html;

PKU-vd2 [50] https://www.pkuml.org/resources/pku-vds.html.

## References

  * [1] Alice benchmark.  https://competitions.codalab.org/competitions/27739?secret_key=289a61c4-4566-4431-89e2-be09ab16b848.
  * [2] Yan Bai, Jile Jiao, Wang Ce, Jun Liu, Yihang Lou, Xuetao Feng, and Ling-Yu Duan.  Person30k: A dual-meta generalization network for person re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2123–2132, 2021.
  * [3] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  Machine learning, 79(1):151–175, 2010.
  * [4] Yeong-Jun Cho and Kuk-Jin Yoon.  Pamm: Pose-aware multi-shot matching for improving person re-identification.  IEEE Transactions on Image Processing, 27(8):3739–3752, 2018.
  * [5] Israel Cohen, Yiteng Huang, Jingdong Chen, Jacob Benesty, Jacob Benesty, Jingdong Chen, Yiteng Huang, and Israel Cohen.  Pearson correlation coefficient.  Noise reduction in speech processing, pages 1–4, 2009.
  * [6] Abir Das, Anirban Chakraborty, and Amit K Roy-Chowdhury.  Consistent re-identification in a camera network.  In European conference on computer vision, pages 330–345. Springer, 2014.
  * [7] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2009.
  * [8] Weijian Deng, Liang Zheng, Qixiang Ye, Guoliang Kang, Yi Yang, and Jianbin Jiao.  Image-image domain adaptation with preserved self-similarity and domain-dissimilarity for person re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018.
  * [9] Yuval Eldar, Michael Lindenbaum, Moshe Porat, and Yehoshua Y Zeevi.  The farthest point strategy for progressive image sampling.  IEEE Transactions on Image Processing, 6(9):1305–1315, 1997.
  * [10] Ehsan Elhamifar, Guillermo Sapiro, Allen Yang, and S Shankar Sasrty.  A convex optimization framework for active learning.  In Proceedings of the IEEE International Conference on Computer Vision, pages 209–216, 2013.
  * [11] Hehe Fan, Liang Zheng, Chenggang Yan, and Yi Yang.  Unsupervised person re-identification: Clustering and fine-tuning.  ACM Transactions on Multimedia Computing, Communications, and Applications, 14(4):1–18, 2018.
  * [12] Reza Zanjirani Farahani and Masoud Hekmatfar.  Facility location: concepts, models, algorithms and case studies.  Springer Science & Business Media, 2009.
  * [13] Yarin Gal, Riashat Islam, and Zoubin Ghahramani.  Deep bayesian active learning with image data.  In International Conference on Machine Learning, pages 1183–1192. PMLR, 2017.
  * [14] Yixiao Ge, Dapeng Chen, and Hongsheng Li.  Mutual mean-teaching: Pseudo label refinery for unsupervised domain adaptation on person re-identification.  In Proceedings of the International Conference on Learning Representations, 2020.
  * [15] Yuhong Guo.  Active instance sampling via matrix partition.  Advances in Neural Information Processing Systems, 23, 2010.
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016.
  * [17] Shuting He, Hao Luo, Pichao Wang, Fan Wang, Hao Li, and Wei Jiang.  Transreid: Transformer-based object re-identification.  In Proceedings of the IEEE International Conference on Computer Vision, 2021.
  * [18] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  In Advances in neural information processing systems, 2017.
  * [19] Pirazh Khorramshahi, Amit Kumar, Neehar Peri, Sai Saketh Rambhatla, Jun-Cheng Chen, and Rama Chellappa.  A dual path modelwith adaptive attention for vehicle re-identification.  In Proceedings of the IEEE International Conference on Computer Vision, 2019.
  * [20] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei.  3d object representations for fine-grained categorization.  In Proceedings of the IEEE international conference on computer vision workshops, pages 554–561, 2013.
  * [21] Wei Li, Rui Zhao, Tong Xiao, and Xiaogang Wang.  Deepreid: Deep filter pairing neural network for person re-identification.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 152–159, 2014.
  * [22] Aristidis Likas, Nikos Vlassis, and Jakob J Verbeek.  The global k-means clustering algorithm.  Pattern recognition, 36(2):451–461, 2003.
  * [23] Hongye Liu, Yonghong Tian, Yaowei Yang, Lu Pang, and Tiejun Huang.  Deep relative distance learning: Tell the difference between similar vehicles.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2016.
  * [24] Xinchen Liu, Wu Liu, Huadong Ma, and Huiyuan Fu.  Large-scale vehicle re-identification in urban surveillance videos.  In The IEEE International Conference on Multimedia and Expo, 2016\.
  * [25] Yuchi Liu, Zhongdao Wang, Tom Gedeon, and Liang Zheng.  How to synthesize a large-scale and trainable micro-expression dataset?  In Proceedings of the European Conference on Computer Vision, 2022\.
  * [26] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan.  Learning transferable features with deep adaptation networks.  In Proceedings of International Conference on Machine Learning, pages 97–105, 2015.
  * [27] Yihang Lou, Yan Bai, Jun Liu, Shiqi Wang, and Lingyu Duan.  Veri-wild: A large dataset and a new method for vehicle re-identification in the wild.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3235–3243, 2019.
  * [28] Yihang Lou, Yan Bai, Jun Liu, Shiqi Wang, and Ling-Yu Duan.  Embedding adversarial learning for vehicle re-identification.  IEEE Transactions on Image Processing, 28(8):3794–3807, 2019.
  * [29] Chuanchen Luo, Chunfeng Song, and Zhaoxiang Zhang.  Generalizing person re-identification by camera-aware invariance learning and cross-domain mixup.  In European Conference on Computer Vision, pages 224–241. Springer, 2020.
  * [30] Hao Luo, Youzhi Gu, Xingyu Liao, Shenqi Lai, and Wei Jiang.  Bag of tricks and a strong baseline for deep person re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, 2019.
  * [31] Liqian Ma, Hong Liu, Liang Hu, Can Wang, and Qianru Sun.  Orientation driven bag of appearances for person re-identification.  arXiv preprint arXiv:1605.02464, 2016.
  * [32] Florent Perronnin, Jorge Sánchez, and Thomas Mensink.  Improving the fisher kernel for large-scale image classification.  In Proceedings of the European Conference on Computer Vision, 2010\.
  * [33] Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell.  Adapting visual category models to new domains.  In Proceedings of the European Conference on Computer Vision, 2010\.
  * [34] Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  In International Conference on Learning Representations, 2018.
  * [35] Burr Settles.  Active learning literature survey.  2009\.
  * [36] Jifei Song, Yongxin Yang, Yi-Zhe Song, Tao Xiang, and Timothy M Hospedales.  Generalizable person re-identification by domain-invariant mapping network.  In Proceedings of the IEEE/CVF conference on Computer Vision and Pattern Recognition, pages 719–728, 2019.
  * [37] Liangchen Song, Cheng Wang, Lefei Zhang, Bo Du, Qian Zhang, Chang Huang, and Xinggang Wang.  Unsupervised domain adaptive re-identification: Theory and practice.  Pattern Recognition, 102:107173, 2020.
  * [38] Liangchen Song, Yonghao Xu, Lefei Zhang, Bo Du, Qian Zhang, and Xinggang Wang.  Learning from synthetic images via active pseudo-labeling.  IEEE Transactions on Image Processing, 2020.
  * [39] Xiaoxiao Sun, Yunzhong Hou, Weijian Deng, Hongdong Li, and Liang Zheng.  Ranking models in unlabeled new environments.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11761–11771, 2021.
  * [40] Xiaoxiao Sun and Liang Zheng.  Dissecting person re-identification from the viewpoint of viewpoint.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
  * [41] Yifan Sun, Liang Zheng, Yi Yang, Qi Tian, and Shengjin Wang.  Beyond part models: Person retrieval with refined part pooling (and a strong convolutional baseline).  In European Conference on Computer Vision, 2018.
  * [42] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2016.
  * [43] Zheng Tang, Milind Naphade, Stan Birchfield, Jonathan Tremblay, William Hodge, Ratnesh Kumar, Shuo Wang, and Xiaodong Yang.  Pamtri: Pose-aware multi-task learning for vehicle re-identification using highly randomized synthetic data.  In Proceedings of the IEEE International Conference on Computer Vision, 2019.
  * [44] Zheng Tang, Milind Naphade, Ming-Yu Liu, Xiaodong Yang, Stan Birchfield, Shuo Wang, Ratnesh Kumar, David Anastasiu, and Jenq-Neng Hwang.  Cityflow: A city-scale benchmark for multi-target multi-camera vehicle tracking and re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
  * [45] Antonio Torralba and Alexei A Efros.  Unbiased look at dataset bias.  In Proceedings of the European Conference on Computer Vision, 2011\.
  * [46] Yanan Wang, Shengcai Liao, and Ling Shao.  Surpassing real-world source training data: Random 3d characters for generalizable person re-identification.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 3422–3430, 2020.
  * [47] Zhongdao Wang, Luming Tang, Xihui Liu, Zhuliang Yao, Shuai Yi, Jing Shao, Junjie Yan, Shengjin Wang, Hongsheng Li, and Xiaogang Wang.  Orientation invariant feature embedding and spatial temporal regularization for vehicle re-identification.  In Proceedings of the IEEE International Conference on Computer Vision, 2017.
  * [48] Longhui Wei, Shiliang Zhang, Wen Gao, and Qi Tian.  Person transfer gan to bridge domain gap for person re-identification.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 79–88, 2018.
  * [49] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.
  * [50] Ke Yan, Yonghong Tian, Yaowei Wang, Wei Zeng, and Tiejun Huang.  Exploiting multi-grain ranking constraints for precisely searching visually-similar vehicles.  In Proceedings of the IEEE International Conference on Computer Vision, pages 562–570, 2017.
  * [51] Xi Yan, David Acuna, and Sanja Fidler.  Neural data server: A large-scale search engine for transfer learning data.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3893–3902, 2020.
  * [52] Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G Hauptmann.  Multi-class active learning by uncertainty sampling with diversity maximization.  International Journal of Computer Vision, 113(2):113–127, 2015\.
  * [53] Yue Yao, Liang Zheng, Xiaodong Yang, Milind Naphade, and Tom Gedeon.  Simulating content consistent vehicle datasets with attribute descent.  In Proceedings of the European Conference on Computer Vision, 2020\.
  * [54] Yue Yao, Liang Zheng, Xiaodong Yang, Milind Napthade, and Tom Gedeon.  Attribute descent: Simulating object-centric datasets on the content level and beyond.  arXiv preprint arXiv:2202.14034, 2022.
  * [55] Tianyu Zhang, Lingxi Xie, Longhui Wei, Zijie Zhuang, Yongfei Zhang, Bo Li, and Qi Tian.  Unrealperson: An adaptive pipeline towards costless person re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11506–11515, 2021.
  * [56] Liang Zheng, Zhi Bie, Yifan Sun, Jingdong Wang, Chi Su, Shengjin Wang, and Qi Tian.  Mars: A video benchmark for large-scale person re-identification.  In European Conference on Computer Vision, 2016.
  * [57] Liang Zheng, Liyue Shen, Lu Tian, Shengjin Wang, Jingdong Wang, and Qi Tian.  Scalable person re-identification: A benchmark.  In Proceedings of the IEEE International Conference on Computer Vision, 2015.
  * [58] Zhedong Zheng, Liang Zheng, and Yi Yang.  Unlabeled samples generated by gan improve the person re-identification baseline in vitro.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3754–3762, 2017.
  * [59] Zhun Zhong, Liang Zheng, Zhiming Luo, Shaozi Li, and Yi Yang.  Invariance matters: Exemplar memory for domain adaptive person re-identification.  In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2019.
  * [60] Yi Zhou and Ling Shao.  Aware attentive multi-view inference for vehicle re-identification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2018.