本文主要介绍用于解决SVM对偶模型的算法，它于1998年由John Platt在论文“Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines”中提出的。这篇笔记还参考了某篇博客，但由于是一年前的事了，暂时没找到这篇博客，所以没有引用出来，希望该篇博客的主人见谅。
（1）解决的问题。
SMO 算法解决的是 soft SVM 对偶问题。其模型为：
egin{align}mathop{max}_{alpha}&quad W(alpha)=sum_{i=1}^nalpha_i-frac{1}{2}sum_{i,j=1}^ny_iy_jalpha_ialpha_jlangle x_i,x_j angle onumber\mathop{s.t.}&quad 0leqalpha_ileq C onumber\&quadsum_{i=1}^nalpha_iy_i=0label{model:SoftSVMDual}end{align}
不失一般性，可以将$langle x_i,y_j angle$替换为核函数，记为$K_{ij}$。对应的KKT条件为：
- $alpha_i=0Longrightarrow y_i[x_i^prime w+b]geq 1$.
- $alpha_i=CLongrightarrow y_i[x_i^prime w+b]leq 1$.
- $0<alpha_i<CLongrightarrow y_i[x_i^prime w+b]=1$.
（2）思路。
对模型 ef{model:SoftSVMDual}（二次规划问题，QP），如果采用 interior point methods (比如 the projected conjugate gradient algorithm)的话，当训练集的数据量很大时，将产生一个非常大的矩阵，这对内存的要求以及效率影响非常大。SMO的思路就是把大的QP问题分解成一系列小的QP问题。具体点就是将向量$alpha=(alpha_1,alpha_2,cdots,alpha_n)$中的大部分均固定住，只取其中的两个分量为变量，然后求解模型 ef{model:SoftSVMDual}。 其主要步骤如下：
repeat till convergence{
- 采用启发式的方法选取一对$alpha_i,alpha_j$，然后固定其他分量；
- 在$alpha_i,alpha_j$为变量的情况下求解模型 ef{model:SoftSVMDual}，更新$alpha_i,alpha_j$。
}
（3）SMO分析。
不失一般性，我们假设选取的点为$alpha_1,alpha_2$，由限制条件$sum_{i=1}^nalpha_iy_i=0$可知$y_1alpha_1+y_2alpha_2=-sum_{i=3}^nalpha_iy_i riangleq k$，其中$k$为常数。又由限制条件$0leqalpha_ileq C$可知，可行解被限制在如下的两个盒子里。
对第二个限制条件$y_1alpha_1+y_2alpha_2=k$进行讨论。
1）当$y_1 eq y_2$时，$alpha_1-alpha_2=k$。设$alpha_2$的上下界为$L,H$。
若$kgeq 0$，则$alpha_1,alpha_2$只能在图1中直线一的实线部分，则此时$L=0,H=C-k$;
若$k< 0$，则$alpha_1,alpha_2$只能在图1中直线二的实线部分，则此时$L=-k,H=C$;
2) 当$y_1=y_2$时，$alpha_1+alpha_2=k$。
若$0leq kleq C$，则$alpha_1,alpha_2$只能在图2中直线一的实线部分，则此时$L=0,H=k$;
若$k>C$，则$alpha_1,alpha_2$只能在图2中直线二的实线部分，则此时$L=k-C,H=C$。
综上，$alpha_2$的取值范围为: $Lleqalpha_2leq H$。
对目标函数进行转化：
egin{align*}W(alpha_2)&=sum_{i=1}^nalpha_i-frac{1}{2}sum_{i=1}^nsum_{j=1}^ny_iy_jK_{ij}alpha_ialpha_j\&=alpha_1+alpha_2+sum_{i=3}^nalpha_i-frac{1}{2}sum_{i=1}^n(sum_{j=1}^2y_iy_jK_{ij}alpha_ialpha_j+sum_{j=3}^ny_iy_jK_{ij}alpha_ialpha_j)\&=alpha_1+alpha_2+sum_{i=3}^nalpha_i-frac{1}{2}sum_{i=1}^2(sum_{j=1}^2y_iy_jK_{ij}alpha_ialpha_j+sum_{j=3}^ny_iy_jK_{ij}alpha_ialpha_j)\&quad-frac{1}{2}sum_{i=3}^n(sum_{j=1}^2y_iy_jK_{ij}alpha_ialpha_j+sum_{j=3}^ny_iy_jK_{ij}alpha_ialpha_j)\&=alpha_1+alpha_2+sum_{i=3}^nalpha_i-frac{1}{2}sum_{i=1}^2sum_{j=1}^2y_iy_jalpha_ialpha_jK_{ij}-sum_{i=1}^2sum_{j=3}^ny_iy_jalpha_ialpha_jK_{ij}-frac{1}{2}sum_{i=3}^nsum_{j=3}^ny_iy_jalpha_ialpha_jK_{ij}\&=alpha_1+alpha_2-frac{1}{2}alpha_1^2K_{11}-frac{1}{2}alpha_2^2K_{22}-y_1y_2alpha_1alpha_2K_{12}-y_1alpha_1sum_{j=3}^ny_jalpha_jK_{1j}-y_2alpha_2sum_{j=3}^ny_jalpha_jK_{2j}\&quad +sum_{i=3}^nalpha_i-frac{1}{2}sum_{i=3}^nsum_{j=3}^ny_iy_jalpha_ialpha_jK_{ij}\&=alpha_1+alpha_2-frac{1}{2}K_{11}alpha_1^2-frac{1}{2}K_{22}alpha_2-y_1y_2K_{12}alpha_1alpha_2-y_1alpha_1v_1-y_2alpha_2v_2+ ext{Constant}end{align*}
其中$v_1=sum_{j=3}^ny_jalpha_jK_{1j},v_2=sum_{j=3}^ny_jalpha_jK_{2j}$。
由$sum_{i=1}^ny_ialpha_i=0Longrightarrow alpha_1y_1+alpha_2y_2=kLongrightarrow alpha_1=r-salpha_2$，其中$r=ky_1$为常数，$s=y_1y_2$。 将$alpha_1=r-salpha_2$代入上式得到：
egin{align*}W(alpha_2)=&r-salpha_2+alpha_2-frac{1}{2}K_{11}(r-salpha_2)^2-frac{1}{2}K_{22}alpha_2^2-sK_{12}alpha_2(r-salpha_2)\&quad-y_1(r-salpha_2)v_1-y_2alpha_2v_2+ ext{Constant}end{align*}
对$W(alpha)$求导并令导数为0得：
egin{align*}frac{dW(alpha_2)}{dalpha_2}=-s+1+sK_{11}(r-salpha_2)-K_{22}alpha_2-srK_{12}+2K_{12}alpha_2+y_1v_1s-y_2v_2=0end{align*}
$$Longrightarrow(K_{11}+K_{22}-2K_{12})alpha_2=1-y_1y_2+y_1y_2r(K_{11}-K_{12})+y_2(v_1-v_2)$$
egin{equation}Longrightarrowalpha_2=frac{y_2[y_2-y_1+y_1r(K_{11}-K_{12})+v_1-v_2]}{K_{11}+K_{22}-2K_{12}}label{equ:solutionOfAlpha2}end{equation}
将$v_1=sum_{j=3}^ny_jalpha_jK_{1j}, v_2=sum_{j=3}^ny_jalpha_jK_{2j}, r=alpha_1+salpha_2=alpha_1^{old}+salpha_2^{old}$ 代入式子 ef{equ:solutionOfAlpha2}得：
egin{equation}alpha_2^{new}=frac{y_2[y_2-y_1+y_1(alpha_1^{old}+salpha_2^{old})(K_{11}-K_{12})+sum_{j=3}^ny_jalpha_jK_{1j}-sum_{i=3}^ny_ialpha_iK_{2i}]}{K_{11}+K_{22}-2K_{12}}label{equ:updateAlpha2}end{equation}
记$f(x_i)=sum_{j=1}^ny_jalpha_jK_{ij}+b$，即$f(x_i)=w^prime x_i+b$，故可得$v_1,v_2$:
egin{equation}v_1=sum_{j=3}^ny_jalpha_jK_{1j}=f(x_1)-b-y_1alpha_1K_{11}-y_2alpha_2K_{12}=f(x_1)-b-y_1alpha_1^{old}K_{11}-y_2alpha_2^{old}K_{12}label{equ:v1}end{equation}
egin{equation}v_2=sum_{j=3}^ny_jalpha_jK_{2j}=f(x_2)-b-y_1alpha_1K_{21}-y_2alpha_2K_{22}=f(x_2)-b-y_1alpha_1^{old}K_{21}-y_2alpha_2^{old}K_{22}label{equ:v2}end{equation}
将式子 ef{equ:v1}和 ef{equ:v2}代入式子 ef{equ:updateAlpha2}得：
egin{align}alpha_2^{new}&=frac{y_2[y_2-y_1+y_1(alpha_1^{old}+salpha_2^{old})(K_{11}-K_{12})+f(x_1)-f(x_2)\-y_1alpha_1^{old}K_{11}-y_2alpha_2^{old}K_{12}+y_1alpha_1^{old}+y_2alpha_2^{old}K_{22}]}{K_{11}+K_{22}-2K_{12}} onumber\&=frac{y_2[y_2-y_1+y_1alpha_1^{old}(K_{11}-K_{12})+y_2alpha_2^{old}(K_{11}-K_{12})\+y_1alpha_1^{old}(K_{21}-K_{11})+y_2alpha_2^{old}(K_{22}-K_{21})+f(x_1)-f(x_2)]}{K_{11}+K_{22}-2K_{12}} onumber\&=frac{y_2[y_2-y_1+y_2alpha_2^{old}(K_{11}-K_{12}+K_{22}-K_{21})+f(x_1)-f(x_2)]}{K_{11}+K_{22}-K_{12}} onumber\&=alpha_2^{old}+frac{y_2[(f(x_1)-y_1)-(f(x_2)-y_2)]}{K_{11}+K_{22}-2K_{12}} onumber\& riangleqalpha_2^{old}+frac{y_2(E_1-E_2)}{eta}label{equ:newUpdateAlpha2}end{align}
其中$E_i=f(x_i)-y_i$表示误差项，$eta=K_{11}+K_{22}-2K_{12}=|Phi(x_1)-Phi(x_2)|^2$.（$Phi$是原始空间向特征空间的映射，其中$sqrt{eta}$可以看成是一个度量两个样本的相似性距离）
得到$alpha_2^{old}$的更新式子后，由于$alpha_2^{old}$也必须落入限制盒子里，故必须对$alpha_2^{new}$进行限制，即：
egin{equation}alpha_2^{new.clipped}=left{egin{array}&Lquadquadquadalpha_2^{new}leq L\alpha_2^{new}quadquadquad L<alpha_2^{new}<H\Hquadquadquadalpha_2^{new}geq Hend{array} ight.label{equ:clippedAlpha2}end{equation}
又因为$alpha_1^{old}=r-salpha_2^{old},alpha_1^{new}=r-salpha_2^{new.clipped}$，消去$r$得到：
egin{equation}alpha_1^{new}=alpha_1^{old}+salpha_2^{old}-salpha_2^{new.clipped}=alpha_1^{old}+y_1y_2(alpha_2^{old}-alpha_2^{new.clipped})label{equ:updateAlpha1}end{equation}
得到更新$alpha_1$与$alpha_2$的两个迭代式：
$alpha_2^{new}=alpha_2^{old}+frac{y_2(E_1-E_2)}{eta}$，进一步求得$alpha_2^{new.clipped}$
$alpha_1^{new}=alpha_1^{old}+y_1y_2(alpha_2^{old}-alpha_2^{new.clipped})$.
（4）停止条件。
一般对于凸优化问题，有如下三种停止条件：
- 监视目标函数的增长率，即$W(alpha)$的增长低于某一tolerance时停止，这种效果一般都不好。
- 监视原问题的KKT条件，由于最优解必定满足KKT条件，但KKT条件本身较为苛刻，故只需在一定的tolerance范围内所有样本满足KKT条件即可停止。
- 监视可行间隙，即原问题与对偶问题的目标函数值之差，对于凸优化来说这个间隙为0.
设原问题的目标函数值为$O(w,b)$，对偶问题的目标函数为$W(alpha)$，则Gap为:
egin{align} ext{Gap}&=frac{1}{2}w^prime w+Csum_{i=1}^nxi_i-(sum_{i=1}^nalpha_i-frac{1}{2}sum_{i,j=1}^ny_iy_jalpha_ialpha_jK_{ij}) onumber\&frac{1}{2}sum_{i,j=1}^ny_iy_jalpha_ialpha_jK_{ij}+Csum_{i=1}^nxi_i-(sum_{i=1}^nalpha_i-frac{1}{2}sum_{i,j=1}^ny_iy_jalpha_ialpha_jK_{ij}) onumber\&=sum_{i,j=1}^ny_iy_jalpha_ialpha_jK_{ij}+Csum_{i=1}^nxi_i-sum_{i=1}^nalpha_i onumber\&=2sum_{i=1}^nalpha_i-2W(alpha)+Csum_{i=1}^nxi_i-sum_{i=1}^nalpha_i onumber\&=sum_{i=1}^nalpha_i-2W(alpha)+Csum_{i=1}^nxi_ilabel{equ:Gap}end{align}
所以当上诉的Gap达到某一tolerance时即可停止。
（5）启发式（Heuristics）的方法选择$alpha_i,alpha_j$。
从上述停止条件可知，最优点满足KKT条件，因此我们可以选择“最违反KKT条件”的点进行优化。违反KKT条件的点指的是：
egin{equation}alpha_i=0 && y_i(x_i^prime w+b) < 1label{equ:violateKKT1}end{equation}
egin{equation}0<alpha_i<C && y_i(x_i^prime w+b) eq 1label{equ:violateKKT2}end{equation}
egin{equation}alpha_i=C&& y_i(x_i^prime w+b)>1label{equ:violateKKT3}end{equation}
从式子 ef{equ:Gap}可知，第$i$个点对Gap的贡献为：
egin{align*} ext{Gap}_i&=alpha_i[y_i(sum_{j=1}^nalpha_jy_jK_{ij})-1]+Cxi_i\&=alpha_i(y_iu_i-1y_ib)+Cxi_iend{align*}
其中$u_i=w^prime x_i+b=sum_{j=1}^nalpha_jy_jK_{ij}+b$。
1）若满足第一个KKT条件，即$alpha_i=0&& y_iu_igeq 1Longrightarrow xi_i=0$（参考Soft Margin SVM笔记），则
egin{equation*} ext{Gap}_i=alpha_i(y_iu_i-1-y_ib)+Cxi_i=0end{equation*}
若违反第一个KKT条件，即$alpha_i=0&&y_iu_i<1Longrightarrow xi_i>0$，于是$ ext{Gap}_i=Cxi_i>0$，故违反第一个KKT条件使可行间隙变大。
2）若满足第二个KKT条件，即$0<alpha_i<C && y_i(x_i^prime w+b) = 1Longrightarrow xi_i=0$，则
egin{equation*} ext{Gap}_i=-alpha_iy_ib+Cxi_i=-alpha_iy_ibend{equation*}
若违反，即$0<alpha_i<C && y_i(x_i^prime w+b) eq 1$。当$y_iu_i>1Longrightarrowxi_i=0$时，$ ext{Gap}_i=alpha_i(y_iu_i-1)-alpha_iy_ib>-alpha_iy_ib$；当$y_iu_i<1Longrightarrowxi_1-y_iu_i$时，故$ ext{Gap}_i=alpha_i(y_iu_i-1-y_ib)+C(1-y_iu_i)=(C-alpha_i)(1-y_iu_i)-alpha_iy_ib>-alpha_iy_ib$。故违反第二个KKT条件使可行间隙变大。
3）若满足第三个KKT条件，即$alpha_i=C&&y_iu_ileq 1Longrightarrow xi_i=1-y_iu_i$，则
egin{equation*} ext{Gap}_i=alpha_i(y_iu_i-1-y_ib)+Cxi_i=Cy_ibend{equation*}
若违反第三个KKT条件，即$alpha_i=C&&y_iu_i>1$时，$xi_i=0$:
egin{equation*} ext{Gap}_i=alpha_i(y_iu_i-1-y_ib)+Cxi_i=C(y_iu_i-1)-Cy_ib>-Cy_ibend{equation*}
故违反第三个KKT条件使可行间隙变大。
从上述分析可知，采用该策略是可行的，严格的收敛证明可以根据Osuna E Personal Communication 中提到的Osuna's theorem。
该启发式选择分为两个部分，第一部分用于选择第一个乘子$alpha_i$，第二部分用于选择第二个乘子$alpha_j$，其第一部分过程可描述如下：
while(存在违反KKT条件的样本点)
for(i ：遍历所有违反KKT条件的样本点)
j = 采用第二个启发式方法选择乘子；
以$alpha_i,alpha_j$为变量进行优化；
end for
while(存在违反KKT条件的边界点，其中边界点指的是$alpha$等于$0$或者$C$)
for(i：遍历所有违反KKT条件的边界点)
j = 采用第二个启发式方法选择乘子；
以$alpha_i,alpha_j$为变量进行优化；
end for
end while
end while
第二部分过程描述如下：
由于$alpha_2^{new}=alpha_2^{old}+frac{y_2(E_1-E_2)}{eta}$，故为了加快收敛速度，可选择$|E_1-E_2|$的最大值为优化的另一个乘子。
- 在非边界样本点中找值$|E_1-E_2|$最大的点，若不存在或则该最大值点不会是目标函数增加的话，则转2；
- 在非边界样本点中随机选一个样本点，从该样本点开始遍历所有非边界点，直到找到可行的点，否则转3；
- 在所有边界样本点中随机选一个样本点，从该样本点开始遍历所有边界点，直到找到可行的点，否则返回0，表示没找到可行点。
整个SMO的伪代码可在原论文中找到。
（6）关于两个乘子优化的说明。
对目标函数求一阶和二阶导数如下：
egin{equation}frac{partial W(alpha_2)}{partialalpha_2}=-s+1sK_{11}r-K_{11}alpha_2-K_{22}alpha_2-srK_{12}+2K_{12}alpha_2+y_1v_1-y_2v_2end{equation}
egin{equation}frac{partial^2W(alpha_2)}{partialalpha_2^2}=-K_{11}-K_{22}+2K_{12}=-etaend{equation}
由于之前的更新是由导数等于0而得到的，而当二阶导数大于零的时候，这种更新不会使目标函数值保持增长，现在我们对更新方法进行改进，使其对所有的情况都可使目标函数保持增长。
1）当$-eta<0$时，目标函数(关于$alpha_2$的二次函数)开口向下，则有如下三种情况：
- 令$frac{partial W}{partialalpha_2}=0Longrightarrow alpha_2=alpha_2^primein[L,H]$，目标函数取得最大值；
- 令$frac{partial W}{partialalpha_2}=0Longrightarrow alpha_2=alpha_2^prime>H$，$alpha_2$经过clipped，$alpha_2^{new.clipped}=H$，目标函数取得最大值；
- 令$frac{partial W}{partialalpha_2}=0Longrightarrow alpha_2=alpha_2^prime<L$，$alpha_2$经过clipped，$alpha_2^{new.clipped}=L$，目标函数取得最大值。
2）当$-eta>0$时，目标函数开口向上，此时目标函数的最大值必定在边界处取得，因此只要验证边界值的大小即可。将a) $left{egin{array}&alpha_2^{new.clipped}=L\alpha_1^{new}=alpha_1^{old}+s(alpha_1^{old}-L)end{array} ight.$ 和 b) $left{egin{array}&alpha_2^{new.clipped}=H\alpha_1^{new}=alpha_1^{old}+s(alpha_1^{old}-H)end{array} ight.$ 分别代入目标函数中，若a)使目标函数值更大则采用更新a)；若b)使目标函数值更大则采用更新b)。
（7）更新阈值(Threshold)。
为了使每一次更新后的$alpha_1,alpha_2$都满足KKT条件，我们还必须更新阈值$b$。
1）设$alpha_1^{new}$在界内，即$0<alpha_1^{new}<C$，由KKT条件可知：
egin{equation}y_1u_1^{new}=1Longrightarrow y_1(alpha_1^{new}y_1K_{11}+alpha_2^{new.clipped}y_2K_{21}+sum_{i=3}^n(alpha_iy_iK_{i1})+b^{new})=1label{equ:updateThre1}end{equation}
又因：
egin{align}E_1&=f(x_1)-y_1 onumber\&=sum_{j=1}^ny_jalpha_j^{old}K_{1j}+b^{old}-y_1 onumber\&=y_1alpha_1^{old}K_{11}+y_2alpha_2^{old}K_{12}+sum_{j=3}^nalpha_jy_jK_{1j}+b^{old}-y_1 onumber\Longrightarrow& onumber\sum_{i=3}^nalpha_iy_iK_{1i}&=E_1-alpha_1^{old}y_1K_{11}-alpha_2^{old}y_2K_{12}-b^{old}+y_1label{equ:updateThre2}end{align}
将式子 ef{equ:updateThre2}代入式子 ef{equ:updateThre1}得：
$$y_1(alpha_1^{new}y_1K_{11}+alpha_2^{new.clipped}y_2K_{21}+E_1-alpha_1^{old}y_1K_{11}-alpha_2^{old}y_2K_{12}-b^{old}+y_1+b^{new})=1$$
即：
egin{align*}b^{new}&=-alpha_1^{new}y_1K_{11}-alpha_2^{new.clipped}y_2K_{21}-E_1+alpha_1^{old}y_1K_{11}+alpha_2^{old}y_2K_{12}+b^{old}\&=(alpha_1^{old}-alpha_1^{new})y_1K_{11}+(alpha_2^{old}-alpha_2^{new.clipped})y_2K_{21}-E_1+b^{old}end{align*}
2）设$alpha_2^{new.clipped}$在界内，即$0<alpha_2^{new.clipped}<C$，由KKT条件知：
egin{equation}y_2u_2^{new}=1Longrightarrow y_2(w^prime x_2+b^{new})=y_2(alpha_1^{new}y_1K_{21}+alpha_2^{new}y_2K_{22}+sum_{i=3}^nalpha_iy_iK_{2j}+b^{new})=1label{equ:updateThre3}end{equation}
又因：
egin{align}E_2&=f(x_2)-y_2 onumber\&=sum_{j=1}^ny_jalpha_j^{old}K_{2j}+b^{old}-y_2 onumber\&=y_1alpha_1^{old}K_{21}+y_2alpha_2^{old}K_{22}+sum_{j=3}^nalpha_jy_jK_{2j}+b^{old}-y_2 onumber\Longrightarrow& onumber\sum_{i=3}^nalpha_iy_iK_{2i}&=E_2-alpha_1^{old}y_1K_{21}-alpha_2^{old}y_2K_{22}-b^{old}+y_2label{equ:updateThre4}end{align}
将式子 ef{equ:updateThre4}代入式子 ef{equ:updateThre3}得：
$$y_2(alpha_1^{new}y_1K_{21}+alpha_2^{new}y_2K_{22}+E_2-alpha_1^{old}y_1K_{21}-alpha_2^{old}y_2K_{22}-b^{old}+y_2+b^{new})=1$$
即：
egin{align*}b^{new}&=-alpha_1^{new}y_1K_{21}-alpha_2^{new}y_2K_{22}-E_2+alpha_1^{old}y_1K_{21}+alpha_2^{old}y_2K_{22}+b^{old}\&=(alpha_1^{old}-alpha_1^{new})y_1K_{21}+(alpha_2^{old}-alpha_2^{new})y_2K_{22}-E_2+b^{old}end{align*}
3）若$alpha_1^{new},alpha_2^{new.clipped}$都在界内，则情况1）和情况2）的$b$值相等，任取一个即可。
4）若$alpha_1^{new},alpha_2^{new.clipped}$都不再界内，则$b^{new}$取情况1）和情况2）之间的任一值即可。在SMO里，我们去二者的平均值。
（8）提高SMO速度。
有两种技巧可用于提高SMO算法的速度。
1）将核矩阵放在缓存中，减少重复计算。
2）若核函数为线性时，可直接更新$w$，即：
egin{align*}w^{new}&=y_1alpha_1^{new}x_1+y_2alpha_2^{new}x_2+sum_{i=1}^ny_ialpha_ix_i\&=y_1alpha_1^{old}x_1+y_1alpha_1^{new}x_1-y_1alpha_1^{old}x_1+y_2alpha_2^{old}x_2+y_2alpha_2^{new}x_2-y_2alpha_2^{old}x_2+sum_{i=3}^ny_ialpha_ix_i\&=sum_{i=1}^ny_ialpha_i^{old}x_i+(alpha_1^{new}-alpha_1^{old})y_1x_1+(alpha_2^{new}-alpha_2^{old})y_2alpha_2\&=w^{old}+(alpha_1^{new}-alpha_1^{old})y_1x_1+(alpha_2^{new}-alpha_2^{old})y_2alpha_2end{align*}