\section{Introduction}
The concept of non-secret common randomness generation was initially introduced by Ahlswede and Csiszár in \cite{part2} for its high relevance in the theory of message identification \cite{identification}, since it may allow a significant increase in the identification capacity of channels\cite{part2,trafo,Ahlswede2021}.

The identification scheme is conceptually different from the classical transmission scheme proposed by Shannon \cite{shannon}. In fact, in the identification framework, the sender is not interested in what the received message is. He rather wants to know if a specific message of special interest to him has been sent or not. Naturally, the sender has no knowledge of that message. Otherwise, the problem would be trivial.
The identification  scheme has striking applications  in digital watermarking \cite{Moulin,watermarkingahlswede, watermarking}. It is also highly relevant in many practical applications which require robust and ultra-reliable low latency information exchange including several machine-to-machine
and human-to-machine systems \cite{applications}, the tactile internet \cite{tactiles} and industry 4.0 \cite{industrie40}.

Several models for CR generation were introduced in \cite{part2} including the two-source model, which consists of
two terminals who observe independent and identically distributed (i.i.d.) samples from a known
discrete random source, and who wish to generate a shared random variable with the largest possible probability of agreement by communicating as little as possible.

In \cite{part2}, the authors considered the case when the terminals are allowed to communicate over a classical perfect channel as well as the case when the terminals communicate over a  classical noisy channel. A single-letter expression for the CR capacity
  for both cases was derived in \cite{part2}.
  The CR capacity is defined as the maximum amount of shared random variable per channel use. It has been shown in \cite{part2} that the CR capacity can be always  attained with nearly uniform random variables. This is the most convenient form of CR  particularly in the context of key generation \cite{part1}\cite{Maurer}, where further constraints on secrecy are imposed. In our work, however, we will not impose any secrecy requirements.
Later, the results on CR capacity  have been extended in \cite{CRgaussian} to Gaussian channels for their practical relevance in many communication situations such as satellite and deep space
communication links\cite{practicalgaussian}, wired and wireless communications, etc.

  We consider the two-source model for uniform common randomness (UCR) generation in which the two terminals aim to agree on a common uniform or nearly uniform random variable with high probability by communicating as little as possible over an arbitrary single-user channel.
The main contribution of our work consists in establishing a general formula for the UCR capacity  that holds for arbitrary point-to-point channels. In our proof of the UCR capacity formula, we will make use of a well-known result of \cite{verduhan}, which is a general formula  characterizing the transmission capacity of arbitrary channels based on the inf-information rate between the channel inputs and outputs. It is worth-mentioning that no further assumption on stationarity, ergodicity or any kind of  information stability is imposed.
 For ease of notation, we will assume in the proof of the UCR capacity that the channel input and output alphabets are finite. However, our result does not depend on that assumption.

\textit{Outline:} The rest of the paper is structured as follows. In Section \ref{sec2}, we present our system model for CR generation, review the definition of an achievable transmission and UCR rate  and present our main result. Section \ref{converseproof} is devoted to the proof of the converse of the UCR capacity, where inspired by \cite{strongconverse}, we will use a change of measure argument. In Section \ref{directpart}, we prove the achievability part by extending the UCR generation scheme introduced by Ahlswede and Csiszár to arbitrary single-user channels. Section \ref{conclusion} contains concluding remarks and proposes a potential future work in this field.

\textit{Notation:} Throughout the paper,  $\log$ is taken to  base 2. For any set $\mathcal E,$ $\mathcal E^c$ refers to its complement.  For any random variable $X$ with distribution $P_X,$ $\text{supp}(P_X)$ refers to its support. For any random variables $X$ and $Y$ with respective probability distribution $P_{X}$ and $P_{Y}$, $D(P_{X}||P_{Y})$ denotes the relative entropy between $P_X$ and $P_Y.$
\section{System Model and Definitions}
\label{sec2}
\subsection{System Model}
\label{systemmodel}
Let a discrete memoryless multiple source (DMMS) $P_{XY}$ with two components, with  generic variables $X$ and $Y$ on alphabets $\mathcal{X}$ and $\mathcal{Y}$, respectively, be given. The DMMS emits i.i.d. samples of $(X,Y).$
Suppose that the outputs of $X$ are observed only by Terminal $A$ and those of $Y$ only by Terminal $B.$ We further assume that the joint distribution of $(X,Y)$ is known to both terminals.
Terminal $A$
can communicate with Terminal $B$ over an arbitrary single-user channel $W,$ defined as an arbitrary sequence of $n$-dimensional conditional distributions from $\mathcal T^n$ to $\mathcal Z^n$, where $\mathcal T$ and $\mathcal Z$ are the  input and output alphabets, respectively.
There are no other resources available to any of the terminals.
\begin{definition}
A CR-generation protocol of block-length $n$ consists of:
\begin{enumerate}
    \item A function $\Phi$ that maps $X^n$ into a random variable $K$ with alphabet $\mathcal{K}$ generated by Terminal $A.$
    \item A function $\Lambda$ that maps $X^n$ into the input sequence $T^n=(T_1,\hdots,T_n).$
    \item A function $\Psi$ that maps $Y^n$ and the  output sequence $Z^n=(Z_1,\hdots, Z_n)$ into a random variable $L$ with alphabet $\mathcal{K}$ generated by Terminal $B.$
\end{enumerate}
Such a protocol induces a pair of random variables $(K,L)$ whose joint distribution is determined by $P_{XY}$ and by the channel $W$. Such a pair of random variables $(K,L)$ is called permissible.
This is illustrated in Fig. \ref{CRprotocol}.
\end{definition}
\begin{figure}
\centering
\input{figcorrelated_SISO}
\caption{Two-source model for CR generation with unidirectional communication over an arbitrary point-to-point channel $W.$}
\label{CRprotocol}
\end{figure}
\subsection{Achievable Rate and Capacity}
We define first an acheivable UCR rate and the UCR capacity. The uniformity of the random variable $K$ is measured using the total variation distance between $P_K$ and $P_{\text{unif}}$, where $P_{\text{unif}}$ is the uniform distribution on $\mathcal K.$ This total variation distance is denoted by $$ d(P_{K},P_{\text{unif}})=\frac{1}{2}\sum_{k\in \mathcal K}\lvert P_{K}(k)-\frac{1}{\lvert \mathcal K \rvert} \rvert.$$
\begin{definition}
\label{ucrrate}
 A number $H$ is called an achievable UCR rate  if there exists a non-negative constant $c$ such that for every $\alpha>0,$ $\beta>0,$ $\delta>0$  and for sufficiently large $n$ there exists a permissible  pair of random variables $(K,L)$ such that
\begin{equation}
   \mathbb P\left[K\neq L\right]\leq \alpha,
    \label{errorcorrelated}
\end{equation}
\begin{equation}
    |\mathcal{K}|\leq 2^{cn},
    \label{cardinalitycorrelated}
\end{equation}
\begin{equation}
 d(P_{K},P_{\text{unif}}) \leq \beta,
  \label{uniformity}
\end{equation}
\begin{equation}
    \frac{1}{n}H(K)> H-\delta,
     \label{ratecorrelated}
\end{equation}
where the constant $\alpha>0$ in \eqref{errorcorrelated} corresponds to an upper bound on the error probability from the CR generation perspective and where $\beta>0$ in \eqref{uniformity} is an upper-bound on the total variation distance between the distribution of $K$ and the uniform distribution on $\mathcal K.$
\end{definition}
\begin{remark}
Together with \eqref{errorcorrelated}, the technical condition  \eqref{cardinalitycorrelated} ensures for every $\epsilon>0$ and sufficiently large block-length $n$ that
\begin{align}
    \bigg| \frac{H(K)}{n}-\frac{H(L)}{n} \bigg| \leq \epsilon. \nonumber
\end{align}
\end{remark}
\begin{definition}
The UCR capacity $C_{UCR}(P_{XY},W)$ is the maximum achievable UCR rate.
\end{definition}
Next, we define an achievable transmission rate and the transmission capacity of the channel $W.$ For this purpose, we begin by providing the definition of a transmission code for the channel $W.$
\begin{definition}
\label{defcode}
A transmission-code $\Gamma$ of block-length $n$ and size \footnote{\text{This is the same notation used in} \cite{codingtheorems}.} $\lVert \Gamma \rVert $  for the channel $W$ is a family of pairs of codewords and decoding regions $\left\{(\bs{t}_\ell,\ensuremath{\mathcal{D}}_\ell): \ell=1,\ldots,\lVert \Gamma \rVert \right\}$ such that for all $\ell,j \in \{1,\ldots,\lVert \Gamma \rVert\}$
\begin{align}
&\ensuremath{\mathcal{D}}_\ell \cap \ensuremath{\mathcal{D}}_j = \emptyset,\quad \ell \neq j. \nonumber
\end{align}The maximum error probability is expressed as
\begin{align}
    e(\Gamma)=\underset{\ell \in \{1,\ldots,\lVert \Gamma \rVert\}}{\max}W({\ensuremath{\mathcal{D}}_\ell^{c}}|\mathbf{t}_\ell). \nonumber
\end{align}
\end{definition}
\begin{definition}
\label{deftransmissionrate}
   A real number $R$ is called an \textit{achievable} transmission rate of the channel $W$ if for every $\theta,\delta>0$ there exists a code sequence $(\Gamma_n)_{n=1}^\infty$, where each code $\Gamma_n$ of block-length $n$ is defined according to Definition \ref{defcode},  such that
    \[
        \frac{\log\lVert \Gamma_n\rVert}{n}\geq R-\delta
    \]
    and
    \begin{align}
        e(\Gamma_n)\leq\theta
        \nonumber
    \end{align}
    for sufficiently large $n.$
\end{definition}
\begin{definition}
The transmission capacity of the channel $W$ is the maximum achievable transmission rate for $W$ and it is denoted by $C(W).$
\end{definition}
\begin{remark}
Throughout the paper, we consider the maximum error probability criterion. The transmission capacity remains unchanged under the average error probability criterion.
\end{remark}
A general formula for the transmission capacity was established in \cite{verduhan} and it is illustrated in the following theorem:
\begin{theorem}
\label{generalcapacityformula} \cite{verduhan}
A general formula of the transmission capacity of an arbitrary channel $W$ is equal to
\begin{align}
C(W)=\underset{\bs{T}}{\sup} \ \underline{I}(\bs{T},\bs{Z}),
\nonumber \end{align}
where $\bs{T}$ is an input process in the form of a sequence of finite-dimensional distributions $\bs{T}=\{T^n=(T_1,\hdots,T_n)\}_{n=1}^{\infty}$
and where $\bs{Z}=\{Z^n=(Z_1,\hdots,Z_n)\}_{n=1}^{\infty}$ is the corresponding output sequence of finite-dimensional distributions induced by $\bs{T}$ via the channel $W.$ Furthermore, $\underline{I}(\bs{T},\bs{Z})$ denotes the inf-information rate between $\bs{T}$ and $\bs{Z},$ which is defined as
$$ \sup\left\{R: \underset{n\rightarrow\infty}{\lim} \mathbb P\left[\frac{1}{n}i(T^n;Z^n)\leq R \right]=0  \right\},  $$
where $i(T^n;Z^n)$ is the information density of the channel $W.$
\end{theorem}
\subsection{Main Result}
\label{mainresult}
In this section, we give a general formula for the UCR capacity for the model presented in Section \ref{systemmodel}.
\begin{theorem}
For the model in Fig \ref{CRprotocol}, the UCR capacity $C_{UCR}(P_{XY},W)$ is equal to
\begin{equation}
    C_{UCR}(P_{XY},W)= \underset{\substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)}}}}{\max} I(U;X),
    \nonumber
\end{equation}
with $C(W)$ being the transmission capacity of the channel $W$.
\label{main theorem}
\end{theorem}
The converse proof of Theorem \ref{main theorem} is provided in Section \ref{converseproof} and the direct proof is provided in Section \ref{directpart}.
\section{Converse Proof of Theorem \ref{main theorem}}
\label{converseproof}
Let $(K,L)$ be a permissible pair according to a fixed CR-generation protocol of block-length $n,$ as introduced in Section \ref{systemmodel}. We recall that the latter consists of:
\begin{enumerate}
    \item A function $\Phi$ that maps $X^n$ into a random variable $K$ with alphabet $\mathcal{K}$ generated by Terminal $A.$
    \item A function $\Lambda$ that maps $X^n$ into the input sequence $T^n=(T_1,\hdots,T_n).$
    \item A function $\Psi$ that maps $Y^n$ and the  output sequence $Z^n=(Z_1,\hdots, Z_n) $ into a random variable $L$ with alphabet $\mathcal{K}$ generated by Terminal $B.$
\end{enumerate}
We further assume that $(K,L)$ satisfies $\eqref{errorcorrelated}$  $\eqref{cardinalitycorrelated},$ \eqref{uniformity} and $\eqref{ratecorrelated}$, with $\alpha>0$ being an upper-bound on the error probability from the CR generation perspective and with $\beta>0$ being  an upper-bound on the total variation distance between the distribution of $K$ and the uniform distribution on $\mathcal K.$
We are going to show for some $\alpha'(n)>0$ that
\begin{align}
    \frac{H(K)}{n} \leq \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)+\alpha'(n)}}}}{\max} I(U;X), \nonumber
\end{align}
 where $\underset{n\rightarrow \infty}{\lim}\alpha'(n)$ can be made arbitrarily small.
In our proof, we will use  the following lemma:
\begin{lemma} (Lemma 17.12 in \cite{codingtheorems})
For arbitrary random variables $S$ and $R$ and sequences of random variables $X^{n}$ and $Y^{n}$, it holds that
\begin{align}
 &I(S;X^{n}|R)-I(S;Y^{n}|R) \nonumber \\
 &=\sum_{i=1}^{n} I(S;X_{i}|X_{1},\dots, X_{i-1}, Y_{i+1},\dots, Y_{n},R) \nonumber \\ &\quad -\sum_{i=1}^{n} I(S;Y_{i}|X_{1},\dots, X_{i-1}, Y_{i+1},\dots, Y_{n},R) \nonumber \\
 &=n[I(S;X_{J}|V)-I(S;Y_{J}|V)],\nonumber
\end{align}
where $V=(X_{1},\dots, X_{J-1},Y_{J+1},\dots, Y_{n},R,J)$, with $J$ being a random variable independent of $R$,\ $S$, \ $X^{n}$ \ and $Y^{n}$ and uniformly distributed on $\{1 ,\dots, n \}$.
\label{lemma1}
\end{lemma}
Let $J$ be a random variable uniformly distributed on $\{1,\dots, n\}$ and independent of $K$, $X^n$ and $Y^n$. We further define $U=(K,X_{1},\dots, X_{J-1},Y_{J+1},\dots, Y_{n},J).$ It holds that $U \circlearrow{X_J} \circlearrow{Y_J}.$ \\
Notice  that
{{\begin{align}
H(K)&\overset{(a)}{=}H(K)-H(K|X^{n})\nonumber\\
&=I(K;X^{n}) \nonumber\\
&\overset{(b)}{=}\sum_{i=1}^{n} I(K;X_{i}|X_{1},\dots, X_{i-1}) \nonumber\\
&=n I(K;X_{J}|X_{1},\dots, X_{J-1},J) \nonumber\\
&\overset{(c)}{\leq }n I(U;X_{J}), \nonumber
\end{align}}} where $(a)$ follows because $K=\Phi(X^n)$ and $(b)$ and $(c)$ follow from the chain rule for mutual information.
Applying Lemma \ref{lemma1} for $S=K$, $R=\varnothing$ with $V=(X_1,\hdots, X_{J-1},Y_{J+1},\hdots, Y_{n},J)$ yields
\begin{align}
&I(K;X^{n})-I(K;Y^{n})
\nonumber \\&=n[I(K;X_{J}|V)-I(K;Y_{J}|V)] \nonumber\\
&\overset{(a)}{=}n[I(KV;X_{J})-I(K;V)-I(KV;Y_{J})+I(K;V)] \nonumber\\
&\overset{(b)}{=}n[I(U;X_{J})-I(U;Y_{J})],
\label{UhilfsvariableMIMO1}
\end{align}
where $(a)$ follows from the chain rule for mutual information and $(b)$ follows from $U=(K,V)$. \\
It results using (\ref{UhilfsvariableMIMO1}) that
\begin{align}
n[I(U;X_{J})-I(U;Y_{J})]
&=I(K;X^{n})-I(K;Y^{n}) \nonumber\\
&=H(K)-I(K;Y^{n})\nonumber \\
&=H(K|Y^n).
\nonumber
\end{align}
The next step is to show that
\begin{align}
    \frac{H(K|Y^n)}{n}\leq C(W)+\alpha'(n),
\label{toprove} \end{align}
where $\underset{n\rightarrow \infty}{\lim} \alpha'(n)$ can be made arbitrarily small.
In order to prove \eqref{toprove}, we will use a change of measure argument.
\begin{comment}
\subsection{If $\alpha+\beta \geq \frac{1}{2}$}
In this case, it holds
\begin{align}
    \frac{1}{n}H(K|Y^n)&=\frac{1}{n}H(K|Y^n,Z^n)+\frac{1}{n}I(K;Z^n|Y^n) \nonumber
\end{align}
On the one hand, we have
\begin{align}
    \frac{1}{n}H(K|Y^n,Z^n) &\leq \frac{1}{n} H(K|\Psi(Y^n,Z^n)) \nonumber \\
    &=\frac{1}{n} H(K|L) \nonumber \\
    &\overset{(a)}{\leq} \frac{1}{n}\left(1+\mathbb P\left[K\neq L\right] \log\lvert \mathcal K\rvert \right) \nonumber \\
    &\overset{(b)}{\leq} \frac{1}{n}+\alpha c,
\nonumber \end{align}
where $(a)$ follows from Fano's inequality and where $(b)$ follows from \eqref{errorcorrelated} and \eqref{cardinalitycorrelated}.
On the other hand, it holds that
\begin{align}
\frac{1}{n} I(K;Z^{n}|Y^{n})&\leq \frac{1}{n} I(X^{n}K;Z^{n}|Y^{n}) \nonumber\\
& \overset{(a)}{\leq }\frac{1}{n} I(T^n;Z^n|Y^{n})  \nonumber \\
& =  \frac{1}{n} h(Z^n|Y^{n})-\frac{1}{n}  h(Z^n|T^n,Y^{n}) \nonumber \\
& \overset{(b)}{=} \frac{1}{n}  h(Z^n|Y^{n})-\frac{1}{n}  h(Z^n|T^n) \nonumber \\
& \overset{(c)}{\leq }   \frac{1}{n} h(Z^n)-\frac{1}{n}  h(Z^n|T^n) \nonumber \\
& = \frac{1}{n} I(T^n;Z^n)  \nonumber
\end{align}
where $(a)$ follows from the Data Processing Inequality because $Y^{n}\circlearrow{X^{n}K}\circlearrow{T^n}\circlearrow{Z^{n}}$ forms a Markov chain, $(b)$ follows because $Y^{n}\circlearrow{X^{n}K}\circlearrow{T^n}\circlearrow{Z^{n}}$ forms a Markov chain and $(c)$ follow because conditioning does not increase entropy.
Therefore, for $\alpha+\beta\geq \frac{1}{2}$
\begin{align}
    \frac{1}{n}H(K|Y^n)\leq \frac{1}{n}+\alpha c+\frac{1}{n} I(T^n,Z^n).
\nonumber \end{align}
\end{comment}
Assume without loss of generality that $\alpha+\beta<\frac{1}{2}.$
Let $\epsilon$ any positive constant satisfying for sufficiently large $n$
\begin{align}
    2(\alpha+\beta) <\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon \right]. \nonumber
    \end{align}
    Since
\begin{align}
   \underline{I}(\bs{T};\bs{Z})
   = \sup\left\{R: \underset{n\rightarrow\infty}{\lim} \mathbb P\left[\frac{1}{n}i(T^n;Z^n)\leq R \right]=0  \right\},\nonumber
 \end{align}
  and since $0<2(\alpha+\beta)<1,$  we know that such an $\epsilon>0$ exists.
    It follows that
    \begin{align}
       0\leq \mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]<1-2(\alpha+\beta). \label{choiceepsilon}
    \end{align}
    Let $\gamma=2\log\left(\frac{4}{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}\right).$
    \begin{lemma}
    \label{boundgamma}
    It holds that
        \begin{align}
        4<\gamma<2\log\frac{4}{\alpha+\beta}.
    \nonumber \end{align}
    \end{lemma}
    \begin{proof}
    We have
        \begin{align}
       0\leq \mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]<1-2(\alpha+\beta).
    \nonumber \end{align}
    This implies that
    \begin{align}
       \alpha+\beta\leq \alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]<1-(\alpha+\beta)
    \nonumber \end{align}
    which yields
    \begin{align}
        \alpha+\beta< 1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]\leq 1-(\alpha+\beta).
    \nonumber \end{align}
    Therefore
    \begin{align}
        4<\frac{4}{1-(\alpha+\beta)}\leq \frac{4}{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}<\frac{4}{\alpha+\beta}.
    \nonumber \end{align}
    It follows that
    \begin{align}
        4=2\log4<\gamma<2\log\frac{4}{\alpha+\beta}.
    \nonumber \end{align}
    \end{proof}
Consider now the sets
\begin{align}
    \mathcal L=\{ k\in \mathcal K: \log\frac{1}{P_{K}(k)} \geq \log\lvert \mathcal K \rvert -\frac{\gamma}{2}     \}
\nonumber \end{align}
and
\begin{align}
    \mathcal D=\{ (k,y^n)\in \mathcal K\times \mathcal Y^n:  \log\frac{1}{P_{K|Y^n}(k|y^n)} \geq \log \lvert \mathcal K \rvert -\gamma \}.
\nonumber \end{align}
\begin{lemma}
\label{boundprobsett}
It holds that
\begin{align}
\mathbb P\left[K\in \mathcal L \right]\geq 1-(\beta+2^{-\frac{\gamma}{2}}).
\nonumber \end{align}
\end{lemma}
\begin{proof}
By using a standard argument in information-spectrum methods (see Lemma 2.1.2 in \cite{infspectrum}), we have using \eqref{uniformity}
\begin{align}
    \beta &\overset{(a)}{\geq}  d(P_{K},P_{\text{unif}})\nonumber \\
    &\overset{(b)}{\geq}  \mathbb P[ K \notin \mathcal L]-P_{\text{unif}}(\mathcal L^c) \nonumber \\
    &\overset{(c)}{\geq} \mathbb P[ K \notin \mathcal L]-2^{-\frac{\gamma}{2}},
\nonumber \end{align}
where $(a)$ follows from \eqref{uniformity}, $(b)$ follows from Lemma 2.1.2 in \cite{infspectrum} and $(c)$ follows because
\begin{align}
    P_{\text{unif}}(\mathcal L^c)&=\sum_{k\in \mathcal L^c} \frac{1}{\lvert \mathcal K \rvert} \nonumber \\
    &\leq \sum_{k\in \mathcal L^c} 2^{-\frac{\gamma}{2}} P_{K}(k) \nonumber \\
    &\leq 2^{-\frac{\gamma}{2}}. \nonumber
\end{align}
Therefore
\begin{align}
    \mathbb P[ K \notin \mathcal L] \leq \beta+2^{-\frac{\gamma}{2}}.
\nonumber \end{align}
This proves Lemma \ref{boundprobsett}.
\end{proof}
\begin{lemma}
\label{boundprobsetd}
It holds that
\begin{align}
  \mathbb P \left[(K,Y^n)\in \mathcal D\right]  \geq 1-(\beta+2\times 2^{-\frac{\gamma}{2}}). \nonumber
\end{align}
\end{lemma}
\begin{proof}
We have
\begin{align}
    &\mathbb P \left[(K,Y^n)\in \mathcal D\right]\nonumber \\ &\geq \sum_{k \in \mathcal L} \mathbb P \left [(K,Y^n)\in \mathcal D|K=k\right]P_{K}(k) \nonumber \\
    &=\sum_{k \in \mathcal L}  \mathbb P\left[\log\frac{1}{P_{K|Y^n}(k|Y^n)} \geq \log\lvert\mathcal K\rvert-\gamma  \right] P_{K}(k) \nonumber \\
    &=\sum_{k \in \mathcal L}  \mathbb P\left[P_{K|Y^n}(k|Y^n)\leq 2^{\gamma-\log\lvert\mathcal K\rvert} \right] P_{K}(k)\nonumber \\
     &\geq\sum_{k \in \mathcal L}  \mathbb P\left[P_{K|Y^n}(k|Y^n)< 2^{\gamma-\log\lvert\mathcal K\rvert} \right] P_{K}(k)\nonumber \\
    &\overset{(a)}{\geq}\sum_{k\in \mathcal L}\left(1-\frac{P_{K}(k)}{2^{\gamma-\log\lvert \mathcal K\rvert}}\right) P_{K}(k) \nonumber \\
    &\overset{(b)}{\geq}\left(1-\frac{2^{\frac{\gamma}{2}-\log\lvert\mathcal K\rvert}}{2^{\gamma-\log\lvert\mathcal K\rvert}}\right) \sum_{k\in \mathcal L} P_{K}(k) \nonumber \\
    &=(1-2^{-\frac{\gamma}{2}})\mathbb P\left[ K \in \mathcal L\right] \nonumber \\
    &\overset{(c)}{\geq}(1-2^{-\frac{\gamma}{2}})\left(1-(\beta+2^{-\frac{\gamma}{2}})\right) \nonumber \\
    &=1-(\beta+2^{-\frac{\gamma}{2}})-2^{-\frac{\gamma}{2}}+2^{-\frac{\gamma}{2}}(\beta+2^{-\frac{\gamma}{2}}) \nonumber \\
    &\geq 1-(\beta+2\times 2^{-\frac{\gamma}{2}}), \nonumber
   \end{align}
  where $(a)$ follows from Markov's inequality since $P_{K}(k)=\mathbb E\left[P_{K|Y^n}(k|Y^n)\right],$ $(b)$ follows because for $k\in \mathcal L,$  we know that $P_{K}(k) \leq 2^{\frac{\gamma}{2}-\log\lvert\mathcal K\rvert},$ $(c)$ and $(d)$ follows from Lemma \ref{boundprobsett}.
  This proves Lemma \ref{boundprobsetd}.
\end{proof}

Define the sets
\begin{align}
     \mathcal S_{1} =\{ (x^n,z^n): \frac{1}{n} i(\Lambda(x^n);z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon\},\nonumber
\end{align}
\begin{align}
    \mathcal S_{2}=\{(x^n,y^n,z^n): \Phi(x^n)=\Psi(y^n,z^n)   \}, \nonumber
\end{align}
and
\begin{align}
    \mathcal S_{3}=\{(x^n,y^n): (\Phi(x^n),y^n)\in \mathcal D\}. \nonumber
\end{align}

\begin{comment}
\begin{lemma}
\label{finitevariance}
\begin{align}
\sigma_{S}^2=\mathrm{var}(S)<\infty. \nonumber
\end{align}
\end{lemma}
\end{comment}
\begin{comment}
\begin{proof}
Define $P_{\mathrm{min}}= \underset{(x,y) \in \mathcal X\times \mathcal Y}{\min}\mathbb P\left[ X=x|Y=y\right]>0.$
We have
\begin{align}
    \mathrm{var}(S)
    &\leq \mathbb E \left[ S^2\right] \nonumber \\
    &=\mathbb E \left[ \log^2\left(\frac{1}{\mathbb P\left[\Phi(X^n)|Y^n\right]}\right)  \right) \nonumber \\
    &\leq  \mathbb E \left[ \log^2\left(\frac{1}{\mathbb P\left[X^n|Y^n\right]}\right)  \right] \nonumber \\
    &= \mathbb E \left[ \log^2\left(\frac{1}{\mathbb P\left[X|Y\right]^n}\right)  \right] \nonumber \\
    &\leq \mathbb E \left[ \log^2\left(\frac{1}{{P_{\mathrm{min}}}^n}\right)  \right] \nonumber \\
    &=n^2\log^2\left(\frac{1}{{P_{\mathrm{min}}}} \right) \nonumber \\
    &<\infty \nonumber.
\end{align}
\end{proof}
Let $\gamma>0.$ Let $\epsilon(n)$ be any positive constant such that \begin{align} \mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon(n) \right]> \frac{\sigma_S^2}{\sigma_S^2+n^2\gamma^2}.
\label{epsilonn}
\end{align}
Since $\frac{\sigma_S^2}{\sigma_S^2+n^2\gamma^2}<1$  and  since  $\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})\right]=0,$ we know that an $\epsilon(n)>0$ satisfying \eqref{epsilonn} exists.

Define
\begin{align}
    &\mathcal D_1 \nonumber \\
    &=\{ (x^n,y^n): H(K|Y^n) \leq \log\left(\frac{1}{\mathbb P\left[K=\Phi(x^n)|Y^n=y^n\right]}\right)+n\gamma\} \nonumber
\end{align}
and
\begin{align}
     &\mathcal D_2 \nonumber \\
    &=\{ (x^n,z^n): \frac{1}{n} i(\Lambda(x^n);z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon(n)\}
\nonumber \end{align}
\end{comment}

Let $\mathcal S=\mathcal S_{1} \cap \mathcal S_{2} \cap \mathcal S_{3}.$
Inspired by \cite{strongconverse}, we change the probability measure by defining
\begin{align}
  P_{\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n}(x^n,y^n,z^n)=\frac{P_{X^n,Y^n,Z^n}(x^n,y^n,z^n)\mathbbm{1}\left[(x^n,y^n,z^n)\in \mathcal S  \right]}{\mathbb P \left[(X^n,Y^n,Z^n) \in \mathcal S\right]}, \nonumber
\end{align}
where $\mathbbm{1}[\cdot]$ is the indicator function.

Let $(\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n) \sim P_{\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n}.$
In order to show that $(\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n)$ is well-defined, we will show that $\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S \right]>0$ in what follows.
\begin{lemma}
\label{probS}
It holds that
\begin{align*}
   \mathbb P \left[ (X^n,Y^n,Z^n)\in \mathcal S\right]>\frac{\alpha+\beta}{2}>0. \nonumber
\end{align*}
\end{lemma}
\begin{proof}
We have
\begin{align}
    &\mathbb P\left[ (X^n,Y^n,Z^n) \in \mathcal S\right] \nonumber \\
    &\geq 1- \mathbb P\left[(X^n,Y^n) \notin \mathcal S_{3}\right]-\mathbb P\left[(X^n,Y^n,Z^n) \notin \mathcal S_{2}\right] - \mathbb P\left[(X^n,Z^n)\notin \mathcal S_{1}\right]
    \nonumber \\
   &= 1-\mathbb P\left[(K,Y^n)\notin\mathcal D\right]-\mathbb P\left[K\neq L\right] -\mathbb P\left[(X^n,Z^n)\notin \mathcal S_{1}\right]  \nonumber \\
   &\overset{(a)}{\geq} 1-(\beta+2\times 2^{-\frac{\gamma}{2}})-\alpha -\mathbb P\left[(X^n,Z^n)\notin \mathcal S_{1}\right] \nonumber \\
   &=1-(\beta+2\times 2^{-\frac{\gamma}{2}})-\alpha-\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right] \nonumber \\
   &=1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]-  2\times2^{-\frac{\gamma}{2}}\nonumber \\
   &\overset{(b)}{=}\frac{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}{2} \nonumber \\
   &\overset{(c)}{>}\frac{\alpha+\beta}{2}.
\nonumber \end{align}
where $(a)$ follows from Lemma \ref{boundprobsetd} and from \eqref{errorcorrelated}, $(b)$ follows because for $\gamma=2\log\left(\frac{4}{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}\right),$ we have
\begin{align}
    2\times2^{-\frac{\gamma}{2}}=\frac{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}{2}
\nonumber \end{align}and $(c)$ follows from  \eqref{choiceepsilon}.

This proves Lemma \ref{probS}.
\end{proof}
Consider an execution of the protocol for input $(\tilde{X}^n,\tilde{Y}^n)\sim P_{\tilde{X}^n,\tilde{Y^n}}.$
Let $\tilde{K}=\Phi(\tilde{X}^n).$ Let $\tilde{T}^n=\Lambda(\tilde{X}^n)$ be the new channel input sequence. $\tilde{Z}^n$ is then its corresponding output sequence. We further define $\tilde{L}=\Psi(\tilde{Y}^n,\tilde{Z}^n).$ Here, $\tilde{K}$ is equal to $\tilde{L}$ with probability one. Furthermore, since for every $(x^n,y^n,z^n)\in \mathcal S,$
\begin{align}
      \frac{1}{n}i\left(\Lambda(x^n),z^n\right)\leq \underline{I}(\bs{T};\bs{Z})+\epsilon, \nonumber
\end{align}
we have
\begin{align}
    \mathbb E\left[ \frac{1}{n}i\left(\Lambda(\tilde{X}^n),\tilde{Z}^n\right)\right]\leq \underline{I}(\bs{T};\bs{Z})+\epsilon.
\nonumber \end{align}
Therefore
\begin{align}
    \frac{1}{n}I(\tilde{T}^n;\tilde{Z}^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon. \label{upperboundnewmutinf} \end{align}
\begin{lemma} It holds that
\label{upperboundlogcardinality}
\begin{align}
    \log \lvert \mathcal K \rvert  &\leq \log\frac{32}{ (\alpha+\beta)^3}+H(\tilde{K}|\tilde{Y}^n). \nonumber
\end{align}
\end{lemma}
\begin{proof}
For any $(k,y^n) \in \text{supp}(P_{\tilde{K},\tilde{Y}^n}),$ we have
\begin{align}
   \frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)}\nonumber
    &=\frac{1}{P_{Y^n}(y^n)}\sum_{\substack{x^n,z^n \\(x^n,y^n,z^n)\in \mathcal S \\ \Phi(x^n)=k}} P_{\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n}(x^n,y^n,z^n)\nonumber \\
    &=\frac{1}{P_{Y^n}(y^n)}\sum_{\substack{x^n,z^n \\(x^n,y^n,z^n)\in \mathcal S \\ \Phi(x^n)=k}} \frac{P_{X^n,Y^n,Z^n}(x^n,y^n,z^n)}{\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]} \nonumber \\
      &\leq \frac{P_{K,Y^n}(k,y^n)}{P_{Y^n}(y^n)\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]} \nonumber \\
       &= \frac{P_{K|Y^n}(k|y^n)}{\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]}  \nonumber\\
         &\overset{(a)}{\leq} \frac{2^{\gamma}}{\lvert \mathcal K \rvert \mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]} \nonumber \\
    &\overset{(b)}{\leq} \frac{\left(\frac{4}{\alpha+\beta}\right)^2}{\lvert \mathcal K \rvert \frac{(\alpha+\beta)}{2}} \nonumber \\
    &=\frac{32}{\lvert \mathcal K \rvert (\alpha+\beta)^3},
\nonumber \end{align}
where $(a)$ follows because $(k,y^n)\in \mathcal D$ and $(b)$ follows from Lemma \ref{boundgamma} and from Lemma \ref{probS}.

Therefore for every $(k,y^n) \in \text{supp}(P_{\tilde{K},\tilde{Y}^n}),$ we have
\begin{align}
    \lvert \mathcal K \rvert \leq \frac{32}{ (\alpha+\beta)^3} \frac{1}{\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)}}. \nonumber
\end{align}
This implies that for any $(k,y^n) \in \text{supp}(P_{\tilde{K},\tilde{Y}^n}),$ we have
\begin{align}
\log\lvert \mathcal K \rvert &\leq \log\frac{32}{ (\alpha+\beta)^3}-\log\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)} \nonumber
\end{align}
As a result, it follows that
\begin{align}
 \log \lvert \mathcal K \rvert  &\leq \log\frac{32}{ (\alpha+\beta)^3}+\underset{(k,y^n)\in \text{supp}(P_{\tilde{K},\tilde{Y}^n})}{\min}-\log\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)} \nonumber
\end{align}
Now, it holds that
\begin{align}
    &\underset{(k,y^n)\in \text{supp}(P_{\tilde{K},\tilde{Y}^n})}{\min}-\log\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)} \nonumber \\ &\leq \mathbb E\left[-\log\frac{P_{\tilde{K},\tilde{Y}^n}(\tilde{K},\tilde{Y}^n)}{P_{Y^n}(\tilde{Y}^n)}\right] \nonumber \\
    &=\mathbb E\left[-\log P_{\tilde{K}|\tilde{Y}^n}(\tilde{K}|\tilde{Y}^n) \right]-\mathbb E\left[\log\frac{P_{\tilde{Y}^n}(\tilde{Y}^n)}{P_{Y^n}(\tilde{Y}^n)}\right]\nonumber \\
    &=H(\tilde{K}|\tilde{Y}^n)-D(P_{\tilde{Y}^n}||P_{Y^n}) \nonumber \\ \nonumber \\
    &\leq H(\tilde{K}|\tilde{Y}^n). \nonumber
\end{align}
It follows that
\begin{align}
\log \lvert \mathcal K \rvert  &\leq \log\frac{32}{ (\alpha+\beta)^3}+H(\tilde{K}|\tilde{Y}^n). \nonumber
\end{align}
This completes the proof of the lemma.
\end{proof}
Now, we continue with the converse proof. It holds using lemma \ref{upperboundlogcardinality} that
\begin{align}
   \frac{1}{n} H(K|Y^n) &\leq \frac{1}{n}\log \lvert \mathcal K \rvert\nonumber \\
   &\leq \frac{1}{n}H(\tilde{K}|\tilde{Y}^n)+\frac{1}{n}\log\frac{32}{ (\alpha+\beta)^3}.
\label{entropyentropytilde}
\end{align}

We have
\begin{equation}
\frac{1}{n}H(\tilde{K}|\tilde{Y}^{n})=\frac{1}{n}I(\tilde{K};\tilde{Z}^{n}|\tilde{Y}^{n})+\frac{1}{n}H(\tilde{K}|\tilde{Y}^{n},\tilde{Z}^{n}) \label{entropyKtilconditionedYtilde}
\end{equation}
On the one hand, it holds that
\begin{align}
\frac{1}{n} I(\tilde{K};\tilde{Z}^{n}|\tilde{Y}^{n})&\leq \frac{1}{n} I(\tilde{X}^{n}\tilde{K};\tilde{Z}^{n}|\tilde{Y}^{n}) \nonumber\\
& \overset{(a)}{\leq }\frac{1}{n} I(\tilde{T}^n;\tilde{Z}^n|\tilde{Y}^{n})  \nonumber \\
& =  \frac{1}{n} H(\tilde{Z}^n|\tilde{Y}^{n})-\frac{1}{n}  H(\tilde{Z}^n|\tilde{T}^n,\tilde{Y}^{n}) \nonumber \\
& \overset{(b)}{=} \frac{1}{n}  H(\tilde{Z}^n|\tilde{Y}^{n})-\frac{1}{n}  H(\tilde{Z}^n|\tilde{T}^n) \nonumber \\
& \overset{(c)}{\leq }   \frac{1}{n} H(\tilde{Z}^n)-\frac{1}{n}  H(\tilde{Z}^n|\tilde{T}^n) \nonumber \\
& = \frac{1}{n} I(\tilde{T}^n;\tilde{Z}^n)  \nonumber \\
&\overset{(d)}{\leq} \underline{I}(\bs{T};\bs{Z})+\epsilon,
\nonumber
\end{align}
where $(a)$ follows from the Data Processing Inequality because $\tilde{Y}^{n}\circlearrow{\tilde{X}^{n}\tilde{K}}\circlearrow{\tilde{T}^n}\circlearrow{\tilde{Z}^{n}}$ forms a Markov chain, $(b)$ follows because $\tilde{Y}^{n}\circlearrow{\tilde{X}^{n}\tilde{K}}\circlearrow{\tilde{T}^n}\circlearrow{\tilde{Z}^{n}}$ forms a Markov chain, $(c)$ follows because conditioning does not increase entropy and $(d)$ follows from \eqref{upperboundnewmutinf}.

On the other hand, since $\tilde{K}$ is equal to $\tilde{L}=\Psi(\tilde{Y}^n,\tilde{Z}^n)$ with probability one, it holds that
$$H(\tilde{K}|\tilde{Y}^n,\tilde{Z}^n)=0.$$

As a result, we have using  \eqref{entropyKtilconditionedYtilde}
\begin{align}
    \frac{1}{n}H(\tilde{K}|\tilde{Y}^n)&\leq \underline{I}(\bs{T};\bs{Z})+\epsilon. \nonumber
\end{align}

From \eqref{entropyentropytilde}, it follows that for $\alpha+\beta<\frac{1}{2}$
\begin{align}
    \frac{1}{n}H(K|Y^n)\leq \underline{I}(\bs{T};\bs{Z})+\epsilon+\frac{1}{n}\log\frac{32}{ (\alpha+\beta)^3}. \nonumber
\end{align}

Since $\alpha,\beta>0$ can be chosen arbitrarily, we can choose them to be arbitrarily small. It follows that $ 2(\alpha+\beta)$ is arbitrarily small. From the definition of $\underline{I}(\bs{T};\bs{Z}),$ we know that
 for any $\zeta>0,$
 \begin{align}
    0< \underset{n\rightarrow\infty}{\lim}\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\zeta \right]. \nonumber
 \end{align}
 Therefore, by choosing $\alpha$ and $\beta$ to be arbitrarily small positive constants, we can choose an arbitrarily small $\epsilon>0$ satisfying
  \begin{align}
      2(\alpha+\beta)< \underset{n\rightarrow\infty}{\lim}\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon \right]. \nonumber
 \end{align}

 As a result,
 \begin{align}
     \frac{H(K|Y^n)}{n}\leq \underline{I}(\bs{T};\bs{Z})+\alpha'(n) \nonumber
 \end{align}
for some $\alpha'(n),$ where $\underset{n\rightarrow \infty}{\lim}\alpha'(n)$ can be made arbitrarily small for $\alpha,\beta,\epsilon$ chosen arbitrarily small.
 From Theorem \ref{generalcapacityformula}, we know that
 \begin{align}
     \underline{I}(\bs{T};\bs{Z})\leq C(W).\nonumber
 \end{align}
We deduce then that
  \begin{align}
     \frac{H(K|Y^n)}{n}\leq C(W)+\alpha'(n). \nonumber
 \end{align}

Since the joint distribution of $X_{J}$ and $Y_{J}$ is equal to $P_{XY}$, $\frac{H(K)}{n}$ is upper-bounded by $I(U;X)$ subject to $I(U;X)-I(U;Y) \leq C(W) + \alpha'(n)$ with $U$ satisfying $U \circlearrow{X} \circlearrow{Y}$. As a result, it holds that
\begin{align}
    \frac{H(K)}{n} \leq \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)+\alpha'(n)}}}}{\max} I(U;X).
    \nonumber
\end{align}
\section{Direct Proof of Theorem \ref{main theorem}}
\label{directpart}
The proof of the direct part is rather standard. It suffices to  extend the UCR generation scheme provided in \cite{part2} to arbitrary single-user channels.
\subsubsection{If $ C(W)=0$} In this case, no communication over the channel is possible. Therefore, it follows from \cite{part2} that
    \begin{align}
C_{UCR}(P_{XY},W) &=
  \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq 0}}}}{\max} I(U;X)  \nonumber \\
  &=  \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)}}}}{\max} I(U;X).  \nonumber
\end{align}
\subsubsection{If $ C(W)>0$} We extend the coding scheme provided in \cite{part2} to arbitary single-user channels. By continuity, it suffices to show that
$$ \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C'}}}}{\max} I(U;X)  $$ is an achievable  UCR rate for every $C'<C(W).$
Let $U$ be a random variable satisfying $U \circlearrow{X} \circlearrow{Y}$ and $I(U;X)-I(U;Y) \leq C'$. Let the maximum error probability $\alpha>0.$ Let $\delta,\beta>0.$ We are going to show that $H=I(U;X)$ is an achievable UCR rate. Without loss of generality, assume that the distribution of $U$ is a possible type for block-length $n$.
For some $\mu>0,$ we let
{{\begin{align}
N_{1}&=\lfloor 2^{n[I(U;X)-I(U;Y)+3\mu]} \rfloor \nonumber\\
N_{2}&=\lfloor 2^{n[I(U;Y)-2\mu]}\rfloor. \nonumber
\end{align}}}For each pair $(i,j)$ with $1\leq i \leq N_{1}$ and $1\leq j \leq N_{2}$, we define a random sequence $\bs{U}_{i,j}\in\mathcal{U}^n$ of type $P_{U}$. Let $\mathbf M=\bs{U}_{1,1},\hdots, \bs{U}_{N_{1},N_{2}}$  be the joint random variable of all $\bs{U}_{i,j}s.$ We further define the following two sets which depend on $\mathbf M$:
\begin{align}
    S_{1}(\mathbf M)&=\{(\bs{x},\bs{y}):(\Phi(\bs{x}),\bs{x},\bs{y}) \in \mathcal{T}_{U,X,Y}^{n}\} \nonumber
\end{align} and
\begin{align}
    S_{2}(\mathbf M)=\{(\bs{x},\bs{y}):(\bs{x},\bs{y}) \in S_{1}(\mathbf M) \ \text{s.t.} \ \exists \ \bs{U}_{i,\ell}\neq\bs{U}_{i,j}=\Phi(\bs{x}) \nonumber \\   \text{jointly} \ UY\text{-typical with} \ \bs{y} \ (\text{with the same first index} \ i)
\}.\nonumber
\end{align}
It is proved in \cite{part2} that
\begin{align}
    \mathbb{E}_{\mathbf M}\left[ \mathbb P\left[(X^n,Y^n)\notin  S_{1}(\mathbf M)\right]+\mathbb P\left[(X^n,Y^n)\in  S_{2}(\mathbf M)\right]\right]\leq \zeta(n),
    \label{averagebeta}
\end{align}
where $\zeta(n) \leq \frac{\alpha}{2}$ for sufficiently large $n$.
We choose a realization $\mathbf m=\bs{u}_{1,1},\hdots, \bs{u}_{N_1,N_2}$ satisfying:
\begin{align}
\mathbb P\left[(X^n,Y^n)\notin  S_{1}(\mathbf m)\right]+\mathbb P\left[(X^n,Y^n)\in  S_{2}(\mathbf m)\right]\leq \beta.
\nonumber \end{align}
From \eqref{averagebeta}, we know that such a realization exists.
We assume that each $\bs{u}_{i,j}, i=1\hdots N_1, j=1\hdots N_2,$  is known to both terminals.
This means that  $N_{1}$ codebooks $C_{i}, 1\leq i \leq N_{1}$, are known to both terminals, where each codebook contains $N_{2}$ sequences, $ \bs{u}_{i,j}, \ j=1,\hdots, N_2$.

Let $\bs{x}$ be any realization of $X^n$ and $\bs{y}$ be any realization of $Y^n.$
\begin{comment}
It holds for every $X$-typical $\bs{x}$ that $$\mathbb P[\exists (i,j) \ \text{s.t} \ \bs{U}_{ij} \in \mathcal{T}_{U|X}^{n}\left(\bs{x}\right)|X^{n}=\bs{x}]\geq 1-2^{-2^{nc'}},$$ for a suitable $c'>0,$ as in the proof of  Theorem 4.1 in \cite{part2}.
\end{comment}
 Let $\Phi(\bs{x})=\bs{u}_{ij}$, if $\bs{u}_{ij}$ is jointly $UX$-typical with $\bs{x}$ (either one if there are several).
 Let $f_1(\bs{x})=i$ if $\Phi(\bs{x}) \in C_{i}$.  If no such a $\bs{u}_{i,j}$ exists, then $f_1(\bs{x})=N_1+1$ and $\Phi(\bs{x})$ is set to a constant sequence $\bs{u}_0$ different from all the ${\bs{u}_{ij}}'s$, jointly $UX$-typical with none of the realizations of $X^n$ and known to both terminals.
  \begin{remark}
 It holds that  $$S_{3}^{c}(\mathbf m)\subseteq S_{1}^{c}(\mathbf m),$$
 where
 \begin{align}
     S_{3}(\mathbf m)=\{\bs{x}: \exists (i,j) \ \text{s.t} \ (\bs{u}_{ij},\bs{x}) \in \mathcal{T}_{U,X}^{n}\}. \nonumber
 \end{align}
 \end{remark}
  Since $ C'<C(W)$, we choose $\mu$ to be sufficiently small such that
      \begin{align}
     \frac{\log \lVert f_1 \rVert}{n}&=\frac{\log(N_1+1)}{n} \nonumber \\
     &\leq C(W)-\mu',
     \label{inequalitylogfSISO}
      \end{align}
for some $\mu'>0,$
 The message $i^\star=f_1(\bs{x})$, with $i^\star\in\{1,\hdots,N_1+1\}$, is encoded to a sequence $\bs{t}$ using a code sequence $(\Gamma^\star_n)_{n=1}^{\infty}$ with rate $\frac{\log \lvert \Gamma^\star_n \rvert}{n}=\frac{\log \lVert f_1 \rVert}{n}$ satisfying \eqref{inequalitylogfSISO}
 and with error probability $e(\Gamma^\star_n)$ satisfying for sufficiently large $n$
 \begin{align}
     e(\Gamma^\star_n) \leq \theta
 \nonumber \end{align}
where $\theta$ is  a positive constant satisfying $\theta\leq \frac{\alpha}{2}.$
  \color{black}
  Here, $\lVert f_1 \rVert$ refers to the cardinality of the set of messages $\{i^\star:i^\star=1,\hdots,N_1+1\}
$.
  From the definition of the transmission capacity, we know that such a code sequence exists. The sequence $\bs{t}$ is sent over the single-user channel. Let $\bs{z}$ be the channel output sequence. Terminal $B$ decodes the message $\tilde{i}^\star$ from the knowledge of $\bs{z}.$
Let $\Psi(\bs{y},\bs{z})=\bs{u}_{\tilde{i}^\star,j}$ if $\bs{u}_{\tilde{i}^\star,j}$ and $\bs{y}$ are jointly $UY$-typical . If there is no such a $\bs{u}_{\tilde{i}^\star,j}$ or there are several, we set $\Psi(\bs{y},\bs{z})=\bs{u}_0$ (since $K$ and $L$ must have the same alphabet).
Now, we are going to show that the requirements in $\eqref{errorcorrelated},$  $\eqref{cardinalitycorrelated},$ \eqref{uniformity} and $\eqref{ratecorrelated}$ are satisfied.
Clearly, (\ref{cardinalitycorrelated}) is satisfied  for $c=H(X)+\mu+1$  because
{{\begin{align}
|\mathcal{K}|&=N_1 N_2+1 \nonumber \\
             &\leq  2^{n\left[I(U;X)+\mu\right]}+1 \nonumber \\
             &\leq2^{n\left[H(X)+\mu+1\right]}.\nonumber
\end{align}}}We define next for any $(i,j)\in \{1,\hdots,n\}\times\{1,\hdots,n\}$  the set
$$\mathcal R=\{ \bs{x}\in\mathcal{X}^{n} \ \text{s.t.} \ (\bs{u}_{i,j},\bs{x}) \ \text{jointly} \ UX\text{-typical}\}.$$
Then, it holds that
\begin{align}
\mathbb P[K=\bs{u}_{i,j}] &=\sum_{\bs{x}\in\mathcal R}\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]P_{X}^n(\bs{x}) +\sum_{\bs{x}\in\mathcal R^c}\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]P_{X}^n(\bs{x}) \nonumber \\
&\overset{(\RM{1})}{=}\sum_{\bs{x}\in\mathcal R}\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]P_{X}^n(\bs{x}) \nonumber \\
&\leq \sum_{\bs{x}\in\mathcal R}P_{X}^n(\bs{x}) \nonumber \\
&=P_{X}^{n}(\{\bs{x}: (\bs{u}_{i,j},\bs{x}) \ \text{jointly} \ UX\text{-typical}\}) \nonumber\\
& = 2^{-nI(U;X)-\kappa(n)}, \nonumber
\end{align}
for some $\kappa(n)>0$ with $\underset{n\rightarrow \infty}{\lim} \frac{\kappa(n)}{n}=0$,
where (\RM{1}) follows because for  $(\bs{u}_{i,j},\mathbf{x})$ being not jointly $UX$-typical, we have $\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]=0.$ This yields
{{\begin{align}
H(K)\geq nI(U;X)-\kappa'(n)
\nonumber \end{align}}}
for some $\kappa'(n)>0$ with $\underset{n\rightarrow \infty}{\lim} \frac{\kappa'(n)}{n}=0.$
Therefore, for sufficiently large $n,$ it holds that
\begin{align}
    \frac{H(K)}{n}>H-\delta. \nonumber
\end{align}
Thus, (\ref{ratecorrelated}) is satisfied.
Now, we have
\begin{align}
    d(P_{K},P_{\text{unif}})=\frac{1}{2}\sum_{k\in \mathcal K}\lvert P_{K}(k)-\frac{1}{\lvert \mathcal K \rvert} \rvert \leq \kappa''(n)
\nonumber \end{align}
for some $\kappa''(n)>0$ with $\underset{n\rightarrow\infty}{\lim} \kappa''(n)=0.$ Therefore, for sufficiently large $n,$ $\kappa''(n)\leq \beta.$ This proves \eqref{uniformity}.

 Now, it remains to prove that \eqref{errorcorrelated} is satisfied. For this purpose, we define the following event:
\begin{align}
    \mathcal{D}_{\mathbf m}= ``\Phi(X^n) \ \text{is equal to none of the} \  {\bs{u}_{i,j}}'s". \nonumber
\end{align}
We denote its complement by $\mathcal D_{\mathbf m}^{c}.$
We further define $I^\star=f_1(X^n)$ to be the random message generated by Terminal $A$ and  $\tilde{I}^\star$ to be the random message decoded by Terminal $B$.
We have
\begin{align}
    \mathbb P[K\neq L] \nonumber &=\mathbb P[K\neq L|I^\star=\tilde{I}^\star]\mathbb P[I^\star=\tilde{I}^\star] + \mathbb P[K\neq L|I^\star\neq \tilde{I}^\star]\mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
        &\leq \mathbb P[K\neq L|I^\star=\tilde{I}^\star]+ \mathbb P[I^\star\neq\tilde{I}^\star].\nonumber
\end{align}
Here,
\begin{align}
    \mathbb P[K\neq L|I^\star=\tilde{I}^\star]
   &= \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}]\mathbb P[\mathcal{D}_{\mathbf m}|I^\star=\tilde{I}^\star] + \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c]\mathbb P[\mathcal{D}_{\mathbf m}^c|I^\star=\tilde{I}^\star] \nonumber \\
   &\overset{(\RM{1})}{=}\mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c]\mathbb P[\mathcal{D}_{\mathbf m}^c|I^\star=\tilde{I}^\star] \nonumber \\
   &\leq \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c],\nonumber
\end{align}
where $(\RM{1})$ follows from $\mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}]=0,$ since conditioned on  $I^\star=\tilde{I}^\star$ and $\mathcal{D}_{\mathbf m}$, we know that $K$ and $L$ are both equal to $\bs{u}_0$.
It follows that
\begin{align}
    \mathbb P[K\neq L]
    &\leq \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c]+ \mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
    &\leq \mathbb P\left[(X^n,Y^n)\in  S_{1}^{c}(\mathbf m)\cup S_{2}(\mathbf m)\right]+\mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
    &\overset{(a)}{=}\mathbb P\left[(X^n,Y^n)\notin  S_{1}(\mathbf m)\right]+\mathbb P\left[(X^n,Y^n)\in  S_{2}(\mathbf m)\right] +\mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
    &\leq \zeta(n)+ \mathbb P[I^\star\neq\tilde{I}^\star],\nonumber\\
    &\leq \zeta(n)+\theta \nonumber \\
    &\leq \alpha.
\nonumber \end{align}
where $(a)$ follows because $S_{1}^{c}(\mathbf m)$ and $S_{2}(\mathbf m)$ are disjoint.
This completes the direct proof of Theorem .

\section{Conclusion}
\label{conclusion}
In our work, we studied the problem of UCR generation over arbitrary point-to-point channels. We established a general expression for the UCR capacity that holds for arbitrary single-user channels by making use of the transmission capacity formula elaborated  in \cite{verduhan}.  As a future work, it would be interesting to investigate the problem of CR generation in the multi-user setting.


\section{keyword}
	\par
	Keywords:Coordination Motif, X-ray Absorption Spectroscopy,XANES, Machine Learning, Interpretable Machine Learning, Shapley, SHAP

	\section{Introduction}
	\par
	Quantitative rather than purely qualitative analysis of XANES data is the key for XANES data to play a practical role in the detection of three-dimensional geometry and electronic structure changes. The detection capability of XANES in local structure is irreplaceable. Compared with EXAFS data analysis, XANES data analysis lacks both breadth and depth in conventional XAS data processing. Because EXAFS data fitting is based on analytical mathematical expression based on fixed theoretical amplitude and phase, its computational amount and fitting complexity are less than XANES fitting. However, the information provided by XANES cannot be replaced by EXAFS, and the increasing perfection of XANES data processing methods can also increase its proportion in conventional XAS data processing. Currently, XANES calculations mainly include two categories. One is based on first-principles calculations, including DFT-MO method for calculating transition matrix elements on the basis of K-S orbits \cite{DFTMO,DFTMO2}. TDDFT\cite{TDDFT} and ROCIS\cite{ROCIS} are used to calculate the inner shell excitation of other occupied orbits other than the frozen inner shell orbit, focusing on the calculation of the excitation characteristics in spectroscopy. Another calculation method based on multiple scattering \cite{MS} focuses on the calculation of scattering characteristics in spectroscopy, which is closely related to the geometric structure of the system. Common XAS calculation software based on multiple scattering theory includes FEFF\cite{FEFF}, FDMNES\cite{FDMNES} and CONTINUUE. Based on the computational core mentioned above, some XANES fitting programs are developed in combination with mathematical optimization methods. For example, MXAN program combined with MINUIT optimization algorithm package \cite{MXAN}, FITIT program combined with interpolation method \cite{FITIT}, XANES fitting program combined with Bayesian optimization \cite{rehr2005bayes}. The above methods have also been applied in XANES data processing. For example, MXAN was applied to study the structure change of excited state of photosensitizer $Ru^{II}(bpy)_3$ \cite{benfatto2006}. FITIT was applied to the study of photosensitive $Ru(DCBPY)_2(NCS)_2$\cite{Zhang2011}, and Bayesian fitting was applied to the study of the excited state structure of binuclear Pt complexes \cite{van2010}. XANES fitting software for instance MXAN and FITIT program interfaces adopt the rigid body as fixed groups and ligands to fit the geometric parameters of the rigid body. This model is suitable for XANES fitting of protein and complex molecules, but it is not convenient for materials cluster system. The XANES quantitative analysis of nanomaterial system may require other methods, machine learning and neural network are among the choices.

	\par
	It is worth mentioning that the spectral analysis method based on neural network has a good play in the field of materials and cluster system. Research on deep learning based on neural network has been revived since 2006. In this wave trend, neural networks and other machine learning algorithms are applied to X-ray spectral data analysis, and many achievements have been achieved. As the first work of neural network in quantitative analysis of XANES, Timoshenko, Frenkel et al. applied fully connected neural network to the nearest neighbor coordination number of metal clusters with good results \cite{timoshenko2017JPCL}. The preliminary exploration by Timoshenko et al. shows the application value of neural network in XANES data processing and verifies the feasibility of extracting coordination number from experimental near edge spectrum by constructing neural network. In 2020, Timoshenko's work demonstrated the simultaneous capture of coordination number and bond length information based on fully connected neural networks\cite{timoshenko2020}. In 2020, Frenkel et al. used two fully connected neural networks simultaneously to resolve coordination number of two-element nanosystems\cite{li2021AxBy}. In addition to fully connected neural networks, other machine learning algorithms were applied to XANES analysis. For instance, Timoshenko applied convolutional neural networks in 2018 to extract radial distribution function(RDF) from two-dimensional XAS wavelet data\cite{timoshenko2018PRL};Zheng et al used ensemble machine learning algorithm\cite{zheng2018npj}. In addition, unsupervised learning algorithms are also applied to XANES analysis\cite{timoshenko2019unsupervised,tetef2021unsupervised}.Existing researches mostly focus on the use of training sets built for specific samples. Machine learning based on this is aimed at improving its structural analysis performance, but its generalization is limited while obtaining powerful structure analysis ability.
	\par
	There are few XANES analysis works which is based on database based machine learning for XANES parsing is relatively rare\cite{zheng2018npj,carbone2019}. For example, Zheng et al. used ensemble learning algorithm to match similar spectra in the database\cite{zheng2018npj}, and then predicted the architecture based on the matched spectra. However, to sum up, most of the data analysis methods based on machine learning is still to build training sets for specific systems, and the training sets are relatively large in scale. In the above work, the algorithm based on neural network algorithm, which has more advantages in large-scale data sets, is adopted, which also confirms this point from the side. However, the method based on the specific system training set is difficult to be applied to other systems with the same absorption edge. Liu, Yang et al pointed out in their work that error bar of analysis results would increase greatly when constructing neural network analysis using other systems to analyze a given sample\cite{liu2019}.In addition, machine learning XANES analysis based on training sets is more similar to XANES fitting to some extent. The training set is a set of calculated spectra obtained by the variation of structural parameters based on the initial structure. The similar XANES fitting idea is to change the initial structural parameters to find the structure whose calculated spectrum is closest to the experimental one. This is a process from "something" to "excellent", and before that there is a process from "nothing" to "something". All of these methods require an initial structure, and it is often a complex and challenging task to get the initial structure model in practice.

	\par
	The machine learning XANES analysis method based on database has greater generality to the sample to be studied than methods based on training set. The constructed model of this method can be applied to other samples with the same absorption element with high repeatability.
	This article enriches the toolkit for such kind of methods. Based on the small and medium scale theoretical spectral database, we apply the ensemble learning algorithm random forest algorithm, which is more advantageous and robust in small and medium scale data, to analyze the coordination motif of the structure. The accuracy of the analytical results is 90 percent in coordination number and more than 80 percent in stereo coordination motif, which has practical value. This method is based on small and medium scale spectral database and has reference for constructing experimental spectral database and related analysis produce of spectral beam line for spectral analysis. In addition, the method can also provide the initial structure for the users of beam line, which can be used for on-line sample judgment and as the basic structure for subsequent XANES fitting or neural network spectral analysis. At the same time, we have carried out analysis based on interpretable machine learning. We use the TreeSHAP method to explain the mechanism of our model and of a specific prediction example. The model mechanism is explained from the physical perspective as much as possible, which expands the methodological perspective of machine learning application in XAS data analysis.

	\section{Method}

	The flow chart of our method is shown in Figure\ref{flow}, and the whole processing process is briefly described below. Firstly, the theoretical XANES and the representation of the three-dimensional local structure are calculated from the material project structure database\cite{MP}. XANES is the independent variable X, and the three-dimensional local structure is represented as the dependent variable Y to constitute the data set. The input of the model we constructed is XANES and the output is three-dimensional local structure characterization. The model prediction effect is characterized by  $R^2$ or accuracy.
	\par
	In terms of three-dimensional local structure characterization, we use the algorithm developed by Zimmermann\cite{zimmermann2017,PyCDT} et al. to calculate OP. Only structures that can be accurately resolved based on OP are included in the XANES calculation. The local structure order parameters(OP) was selected as the index. On the one hand, it can process single local structure or sample with one dominant local structure; on the other hand, regression based on OP vector also provides a technical  for sample analysis of complex or mixed local structure. The space cutoff index calculated by OP is large enough to obtain more robust results. In the recognition of OP structure, the cutoff value of OP is 0.5 relatively high considering the amount of data included and the accuracy of the algorithm to identify the three-dimensional local structure. XANES is the average effect of atoms of all absorbing edge elements in the system. Let's use the Cu element as an example. In the three-dimensional local structure characterization, we firstly calculate the OP of all Cu atom sites in the system, and only the sample with successful OP identification of all Cu sites in the system is included in the analysis. Then calculate the average OP of system elements as the indicator variable.

	\begin{figure}
		\centering
		\includegraphics[width=1\linewidth]{MLXAS1.eps}
		\caption[flow]{Flow chart}
		\label{flow}
	\end{figure}

	\par
	In terms of theoretical calculation of XANES, this paper mainly deals with K-edge XANES of 3d transition metals. The calculation accuracy and calculation time are considered comprehensively. Therefore, we use FEFF\cite{FEFF} software based on multiple scattering theory for the calculation. This article focuses on XANES. Therefore, a more suitable full multiple scattering algorithm for XANES is adopted. The random-phase approximation (RPA) core-hole approximation is used in calculation. The radius of cluster for self-consistent multiple scattering calculation is large enough for convergency. Real Hedin-Lundqvist exchange-correlation potential is used in the calculation. Considering the error of muffin-tin potential approximation on XANES calculation results of a few systems, we subsequently wrote module using FDMNES\cite{FDMNES} as calculation core which is based on multiple scattering and finite difference method to carry out the XANES calculation process.Considering the amount and scale of data we deal with, we choose tree algorithm and its improved integrated learning algorithm to build the model. See the results section for a detailed description.

	\par
	The dataset consists of the important 3d transition metal Cu K-edge XANES. The local structure order parameters(OP) was calculated to characterize coordination number(CN) and coordination motif(CM), using the OP calculation method developed by Zimmermann\cite{zimmermann2017,PyCDT}. Dataset 1 contains 1088 data, which is denoted as dataset CN. The independent variable X of the dataset is XANES spectrum, which is interpolated evenly to 200 energy grid points. Index Y is the classification based on coordination number. Among them, the largest proportion was 4-coordination, accounting for 65.35\%. We use this as a baseline. That is, the worst learning model predicts that the coordination number with the largest proportion. The model results better than the baseline can reflect that the model has learned "knowledge" in the process of training. Dataset 2 contains 879 data, which we denoted as dataset OP. The dataset independent variable X is still the XANES interpolated to 200 energy points on average. Index Y is OP vector when regression is performed, and OP is used as a 21-dimensional vector here. The value of each dimension of the OP vector represents the similarity between the structure and the corresponding coordination CM of this dimension, which is a smooth value from 0 to 1. The twenty-one 3D CM names and their corresponding coordination numbers are shown in the Table.\ref{OP}. Meanwhile, based on OP, we can obtain CM dominated by sample based on OP maximum, and then classify CM classification index.
	\par
	The result part is divided into two parts according to the difference of the final analysis index. The first part is the classification of coordination number, the second part is the classification of 3D CM, furthermore the regression of OP vector. In the choice of machine learning algorithm, we choose the Tree algorithms instead of neural network. There are a lot of parameters to be fitted in the neural network model, so it is usually not used in small and medium scale data. Tree algorithm has good robustness and good performance in avoiding over-fitting. We choose Tree algorithms that perform well in small and medium scale data, including basic decision tree and ensemble learning algorithm based on decision tree including bagging random forest algorithm and boosting gradient boosted decision tree(GBDT) algorithms XGBoost\cite{xgboost} and LightGBM\cite{lightgbm}. There is no strong dependence between the individual decision trees integrated in random forest algorithm and they can be generated simultaneously. While individual decision trees integrated by XGBoost and LightGBM algorithm are strongly dependent on each other and must be generated sequentially. The important hyperparameters of the model, taking random forest as an example, include the framework hyperparameters nestimators and decision tree hyperparameters such as max-features,max-depth, min-samples-leaf, min-samples-split. The hyperparameter optimization of the model is based on references\cite{hyper1,hyper2}.

	\section{ Model results and discussion}

	\par
	The machine learning classification results based on data set CN are as follows. The index was CN classification, and the independent variable of the dataset was XANES energy spectrum. The machine learning classification results are shown in the Table\ref{CN}. We see that the accuracy of cross-validation is slightly lower than that of a single test set due to the grouping of testing sets. Specifically looking at 5 accuracy results before cross-validation, there are 1-2 results comparable to that of a single testing set. In the comparison of the results of the given machine learning algorithms, the ensemble learning algorithms are generally superior to the basic decision tree model, and the random forest model with the worst performance has a 10.6\% performance improvement compared with the original decision tree model. LightGBM model has the best effect, which can reach 91.28\% accuracy.
	\par
	The machine learning classification results based on data set OP are as follows. The index was CM classification, and the independent variable of the dataset was XANES energy spectrum. Compared with CN classification, CM classification focuses more directly on stereoscopic coordination motifs. Taking 4-coordination as an example, there are the most common tetrahedral and squ qre plan coordination motif, as well as 	see-saw like, trigonal-bipyrami coordination motifs. Here we present the relevant spectral data of tetrahedron and octahedron, the two coordination motifs with the highest proportion in the Cu OP dataset, as shown in Figure\ref{tetoct}. The machine learning classification results are shown in the Table\ref{CM}. In the process of cross-validation, the data set is divided into 5 subsets, that is, 20\% of whole data. It can be seen that even the decision tree model with the worst result is also obtained with 71.56\% accuracy in cross validation. Taking tetrahedron CM with the highest proportion of 32.49\% as the base line, the decision tree model also has a 39.07\% improvement. The optimal cross-validation accuracy of LightGBM model results reaches 81.68\%. Compared with LightGBM, the random forest model only reduced by 0.56\%.

	\par
	Further, we use OP vectors for regression. An important advantage of OP vector over 3D CM classification is that OP vector can deal with complex and mixed CM. When a variety of CM exist in the sample at the same time, OP vector can measure the similarity between the average structure of the sample and various given CMs, and the closeness to each CM can reflect the proportion of various CMs. Therefore, OP vector can represent several dominant CM components and their approximate proportion in the sample to a certain extent. OP vector regression is carried out on data set OP, and the regression results using 21-dimensional Y as the index are shown in Table\ref{CMR} DIM21. Testing $R^2$ 0.42 is the calculation result when 20\% testing sets are used. The small $R^2$ reflects that the model does not achieve the expected effect at the regression level. We compared the predicted value of $\widehat{OP}$ output from the model with the OP from testing set through post-processing, and looked at the model effect at the classification level. If the maximum value of predicted $\widehat{OP}$ and the maximum value of OP of testing set were located in the same CM, it was considered that the prediction of the first leading CM was accurate as shown in the 1st ACC column in the Table\ref{CMR}. If the seconda maximum value of $\widehat{OP}$  and OP were still located in the same CM, or there is no obvious second important CM, the prediction of the second dominant CM is accurate, see 2rd ACC column in Table\ref{CMR}. Here, the judgment that there is no obvious second CM major component is that the second largest value in the OP is less than 0.1. It can be seen that although the effect of the model is poor at the regression level, the prediction accuracy of the first important CM of the model still reaches 81.25\%.
	We speculated that one of the reasons was that samples of a few CM accounted for a large proportion in the small and medium scale data set. And OP component prediction of the CMs was more accurate, which also led to the high 1st acc. For other CM, due to the small amount of sample data, the prediction result is poor, thus lowering the overall regression $R^2$.
	In order to verify this conjecture, we reduced the regression dimension to 3 dimensions, including the three kinds of CMs with the largest number in the data set, TET, OCT and BCC. The regression results are shown as DIM3 in Table\ref{CMR}. We found that the testing $R^2$ in the testing set increased significantly to 0.71, which verified our conjecture. The quality of regression model will be improved by expanding the database to increase the sample size of other CMs.

	\par
	Finally, we discuss the importance of different energy regions to the model. We take the classified random forest model of OP data set as an example. In the Figure\ref{importance}, the abscissa is the energy corresponding to different features, and the ordinate is the normalized feature importance. It can be seen that the "main peak" feature importance, namely the feature importance of white line peak and scattering peaks near the absorption edge, is generally higher than the feature importance of scattering peaks in higher energy region. It shows the importance of "main peak" features to the model.

	\begin{table}
		\caption{\label{OP}Twenty-one 3D CM names and their corresponding coordination numbers.}
		\centering
		\begin{tabular}{lc}
			Coordination Motif    &Coordination number \\
			single neighbor      &1\\
			bent and linear           &2\\
			trigonal plane&3\\
			triangular non-coplanar &3\\
			T-shape&3\\
			square plane&4\\
			tetrahedron&4\\
			see-saw &4\\
			trigonal bipyramid&4\\
			trigonal pyramid&4\\
			pentagonal plane&5\\
			square pyramid&5\\
			trigonal bipyramid&5\\
			hex plan&6\\
			octahedron&6\\
			pentagonal pyramid&6\\
			hex pyr&7\\
			pentagonal bipyramid&7\\
			cube&8\\
			hex bipyr&8\\
			cuboctahedron&12\\

		\end{tabular}
	\end{table}

	\begin{table}
		\caption{\label{CN} Classification results of coordination number.(CN)}
		\centering
		\begin{tabular}{lccc}
			Algorithm    &testing set accuracy &cross validation accuracy  \\
			Decision Tree             &87.16\%        &81.62\%        \\
			Random Forest             &94.50\%        &90.26\%        \\
			XGBoost                   &94.50\%        &90.45\%        \\
			LightGBM                  &94.95\%        &91.28\%        \\

		\end{tabular}
	\end{table}

	\begin{table}
		\caption{\label{CM}Classification results of three-dimensional coordination motifs(CM).}
		\centering
		\begin{tabular}{lcc}
			Algorithm    &testing set accuracy &cross validation accuracy   \\
			Decision Tree             &73.30\%        &71.56\%        \\
			Random Forest             &89.20\%        &81.22\%        \\
			XGBoost                   &89.20\%        &79.29\%         \\
			LightGBM                  &90.90\%        &81.68\%         \\

		\end{tabular}
	\end{table}

	\begin{table}
		\caption{\label{CMR}Regression results of three-dimensional coordination motifs(CM).}
		\centering
		\begin{tabular}{lcccc}
			Regression target     &training$R^2$  &testing$R^2$  &1st acc   &2rd acc   \\
			dim3             &0.95   &0.71   &77.27\%   &67.61\%        \\
			dim21            &0.91   &0.42   &81.25\%   &57.95\%        \\
		\end{tabular}
	\end{table}

	\begin{figure}
		\includegraphics[width=12cm]{tet_oct.eps}
		\caption{\label{tetoct}Tet Oct database}
	\end{figure}

	\begin{figure}
		\includegraphics[width=12cm]{feature_importance.eps}
		\caption{\label{importance}feature importance}
	\end{figure}

	\section{Application of SHAP based Interpretable Machine Learning in stereo coordination motif prediction Model}
	\par
	Despite the great success of machine learning in many areas, However, the lack of interpretability of some machine learning methods severely limits its application in some tasks, especially in some fields concerned with mechanisms for spectrographers, ideally, the model should be able to explain the logic of the model to spectrographers and applied field researchers, and gain more trust from applied field researchers, i.e. beam line users.
	This paper focuses on the application of SHAP explainable method in XAS spectral analysis. SHAP is based on Shapley value theory\cite{shapley} in game theory and machine learning local interpretation. It belongs to the post-interpretation framework, which can provide Shapley value to estimate the contribution of each feature. Shapley Value is a method to describe the weight or importance of a particular feature in the prediction of a particular data point, which is the core of SHAP. Compared with the traditional feature importance method results\ref{importance} ,SHAP has better consistency and can present the positive-negative relationship of each predictor relative to the target variable, which can be used for local and global interpretation . Because SHAP has efficient algorithm implementation under the tree model, we adopted TreeSHAP\cite{TreeSHAP} here.For local interpretability, each feature has its own set of Shapley values.

	We take the CuS covellite system in the experiment to perform the tetrahedral CM regression model as an example. The force plot of the analysis results is shown in the Figure\ref{force}. You can see three features of 8992.4eV, 8992.7eV, 8993eV, that is, the covellite XANES in the 8992.4-8993eV energy region is used for prediction.
	8992.4-8993eV energy region plays an important positive role for tetrahedral CM regression results. This energy area also contributes an important positive role when we conduct model sorting and analysis, that is, considering the performance of the model on a large number of samples, as shown in the figure. In order to adapt to the habits of spectrographers, we present another form of graphs commonly used in SHAP analysis. In the graph, the ordinate is SHAP and the abscissa is energy. We also present a covellite on the graph. Cu K-edge XANES is used to visualize different energy regions. These features are all behind the absorption edge rather than the front edge peaks that we usually think of empirically. We speculate that this may be related to the accuracy of the multiple scattering calculation in the edge front. We have performed a dependency analysis on the 8992.4 and 8992.7 eV energy regions, as can be seen in the figure, these two features work under the same trend, that is, they can be combined as the same feature. 8992.4-8993eV is located in the peak energy region of scattering, and the model may predict the CM through the scattering characteristics of the structure. We conduct an interpretable machine learning analysis of the model, and this result enriches the methodological perspective of XANES data analysis, which can be used for reference.

	We take the CuS Covellite system in the experiment for the tetrahedral CM regression model as an example, and the force plot of the analysis results is shown in the figure. It can be seen that there are three features: 8992.4eV, 8992.7ev and 8993eV. That is, covellite XANES in the energy region of 8992.4-8993eV play an important positive role in predicting the tetrahedral coordination of covellite system i.e. tetrahedral CM OP value. This energy region also plays an important positive role in whole model, i.e. considering the performance of the model on a large number of samples, as shown in the Figure\ref{bswarm}. In order to adapt to the habit of spectrographers, we presented the graph commonly used in SHAP analysis in another form in Figure\ref{SHAP-XANES}. In the graph, the ordinate is SHAP and the abscissa is energy. We also presented a covellite Cu K-Edge XANES on the graph to intuitively reflect different energy regions. The 8992.4-8993eV are behind the absorption edge but not in pre-edge region. We speculate that this may be related to the accuracy of the multiple scattering calculation of pre-edge feature. We conducted a dependency analysis on 8992.4 and 8992.7eV feature, as shown in the Figure\ref{dep}. These two features work under the same trend, that is, they can be combined as the same feature. 8992.4-8993eV is located in the scattering peak energy region, and the model may predict CM based on the scattering characteristics of the structure.  In summary we perform interpretable machine learning analysis on the model, which enriches the methodological perspective of XANES data analysis and has reference significance.

	\begin{figure}
		\centering
		\includegraphics[width=0.7\linewidth]{SHAP-XANEStitle}
		\caption{SHAP value plot from a spectroscopy view of tetrahedron CM regression model.}
		\label{SHAP-XANES}
	\end{figure}

	\begin{figure}
		\centering
		\includegraphics[width=0.7\linewidth]{force}
		\caption{SHAP value force plot of CuS coverllite's prediction result.}
		\label{force}
	\end{figure}

	\begin{figure}
		\centering
		\includegraphics[width=0.7\linewidth]{dep}
		\caption{dependence diagram.}
		\label{dep}
	\end{figure}

	\begin{figure}
		\centering
		\includegraphics[width=0.7\linewidth]{bswarm}
		\caption{Summary beeswarm plot of SHAP value.}
		\label{bswarm}
	\end{figure}

	\section{Application of SHAP based Interpretable Machine Learning in XANES Reconstruction Model}
	In the previous section we demonstrated the application of interpretable machine learning to parametric prediction models. The input of this kind of model is XAS spectrum, and the output is various structural parameters, such as coordination number, bond length, bond Angle, stereo structure symmetry, etc.In contrast, there is another type of model, XANES spectrum reconstruction model in which structural parameters are input and theoretical XANES reconstructed by machine learning algorithm are output. Taking Fe complex system as an example, we also carry out explainable machine learning analysis for such models. The analysis results quantitatively and systematically demonstrate the model mechanism, that is, how parameter changes affect the theoretical XANES reconstructed by machine learning. SHAP analysis results can be seen in the Figure\ref{SHAP_FITIT}.
	For representative work in XANES Reconstruction Model, see software PyFITIT\cite{pyfitit} introduced by Martini et al. PyFITIT calls the XANES Reconstruction Model as indirect method. We take the PyFITIT IHS500 Fe complex example\cite{pyfitit} as the analysis system. The input of the model is three structural parameters, and the output is theoretical XANES reconstructed by machine learning algorithm. This example is a metal complex. The rigid body of the ligand is fixed to reduce the degree of freedom of movement. There are three ligand structural parameters central ring shift eg. the axial ring shift along Fe-N axis direction, side rings elong and side rings Shift. The three parameters are in the range of -0.3 to 0.5 angstrom.
	\par
	SHAP analysis results are shown in Figure\ref{SHAP_FITIT}. We did not adopt the traditional SHAP data presentation form similar to Figure\ref{bswarm}, but reorganized the data results according to the needs of spectral analysis. We incorporate the related SHAP values of the same parameter into the same image. Because SHAP decomposed the prediction contribution of the three structure parameters, the graph based on the given parameter can quantitatively and systematically show the influence of the given parameter on the reconstructed XANES based on machine learning algorithm. We use the two-color segmental colormap as the colorbar to display the corresponding structural parameter values of the data point.
	 It can be seen from Figure\ref{SHAP_FITIT} that the increase and decrease of "central ring shift" and "side ringselong" parameters clearly correspond to the two trends of reconstructed XANES change respectively.
	 The reduction of "central ring shift" and "side rings elong" parameters forms a new feature in 7140-7150eV energy range. The "central ring shift" decreases with the weakening of the white line peak. The decrease of "side rings elong" also causes the shift of white line peak to high energy direction. Comparatively, "side rings shift" has less effect on reconstructed XANES, and only when the parameters increase, the white line feature increases obviously. The trend of reconstructed XANES variation caused by parameters can be quantified and systematically presented by interpretable machine learning. It provides a clear direction for the subsequent XANES fitting based on optimization algorithm. The mechanism of parameters affecting reconstructed XANES also makes it possible to analyze the physical background, remove redundant and interfering set parameters, and to improve and modify the model.

	 The decrease in oxygen beam induced by oxygen impurities corresponds to two trends of oxygen dependence.

	\begin{figure}
		\centering
		\includegraphics[width=1.2\linewidth]{SHAP_FITIT}
		\caption[SHAP_FITIT]{SHAP mechanism of XANES Reconstruction Model.The above three pictures are SHAP values plots of three structural parameters, and the below three pictures are the sum of SHAP values and expected spectrum values. The black solid line is the reference XANES formed by expected values, called "XANES View", which is more convenient for spectrographers to interpret the results. Colorbar is the value of structure parameters from -0.3 to 0.5 angstrom.}
		\label{SHAP_FITIT}
	\end{figure}

	\section{Conclusion and Outlook}
	Based on the small and medium scale theoretical spectral database, we apply random forest algorithm to analyze the coordination motif of the structure. The accuracy of the analytical results is 90percent in coordination number and more than 80 percent in stereo coordination motif, which has practical value. This method can provide an initial structure for the beamline user for online judgment and as an initial guess for further detail XANES quantitative analysis. Later, we will further expand our database based on other databases than material project such as NOMAD\cite{NOMAD}, AFLOW\cite{AFLOW}, etc. A more systematic study will be also carried out on the stereo coordination motif analysis of the most common used three dimensional metal K-edge absorption spectrum.