(其实正是一批代码未有题解)710官方网站

自家要报案此次校赛出题人的消沉出题!!!

A-Softmax的计算及与L-Softmax的自己检查自纠——SphereFace

A-Softmax的下结论及与L-Softmax的对照——SphereFace

合法题解请戳:http://3.scnuacm2015.sinaapp.com/?p=89(其实正是一批代码未有题解)

\(\quad\)【引言】SphereFace在MegaFace数据集上识别率在20一7年排行第二,用的A-Softmax
Loss有着鲜明的几何定义,能在可比小的多少集上达到科学的功能。那么些是他们总计成果的舆论:SphereFace:
Deep Hypersphere Embedding for Face
Recognition
。小编对故事集做四个小的总计。

\(\quad\)【引言】SphereFace在MegaFace数据集上识别率在20壹7年排名第二,用的A-Softmax
Loss有着明显的几何定义,能在相比小的数目集上达到科学的成效。这些是他俩总括成果的诗歌:SphereFace:
Deep Hypersphere Embedding for Face
Recognition
。笔者对舆论做三个小的下结论。

 

1. A-Softmax的推导

追忆一下二分类下的Softmax后验可能率,即:

\[ \begin{split} p_1 =
\frac{\exp({W}_1^Tx+b_1)}{\exp({W}_1^Tx+b_1)+\exp({W}_2^Tx+b_2)}
\cr p_2 =
\frac{\exp({W}_2^Tx+b_2)}{\exp({W}_1^Tx+b_1)+\exp({W}_2^Tx+b_2)}
\cr \end{split} \tag{1.1} \]

\(\quad\)显明决策的交界在当\(p_1 = p_2\)时,所以决定界面是\((W_1-W_2)x+b_1-b_2=0\)。大家能够将\(W_i^Tx+b_i\)写成\(\|W_i^T\|\cdot\|x\|\cos(\theta_i)+b_i\),其中\(\theta_i\)是\(W_i\)与\(x\)的夹角,如对\(W_i\)归一化且设偏置\(b_i\)为零(\(\|W_i\|=1\),\(b_i=0\)),那么当\(p_1 = p_2\)时,我们有\(\cos(\theta_1)-\cos(\theta_2)=0\)。从此间能够看看,如里一个输入的数据特征\(x_i\)属于\(y_i\)类,那么\(\theta_{yi}\)应该比别的全体类的角度都要小,也即是说在向量空间中\(W_{yi}\)要更靠近\(x_i\)。
\(\quad\)我们用的是Softmax
Loss,对于输入\(x_i\),Softmax Loss
\(L_i\)定义以下:
\[ \begin{split} L_i &=
-\log(\frac{\exp(W_{yi}^Tx_i+b_{yi})}{\sum_j\exp(W_{j}^Tx_i+b_{j})})
\cr &=
-\log(\frac{\exp(\|W_{yi}^T\|·\|x_i\|\cos(\theta_{yi,i})+b_{yi})}{\sum_j\exp(\|W_{j}^T\|·\|x_i\|\cos(\theta_{j,i})+b_{j})})
\cr \end{split} \tag{1.2} \]
式\((1.2)\)中的\(j\in[1,K]\),其中\(K\)类其他总额。上面大家限制了部分尺度:\(\|W_i\|=1\),\(b_i=0\),由那几个条件,能够获得核查的损失函数(也便是舆论中因故说的modified
softmax loss):
\[ L_{modified} =
\frac{1}{N}\sum_i-\log(\frac{\exp(\|x_i\|\cos(\theta_{yi,i}))}{\sum_j\exp(\|x_i\|\cos(\theta_{j,i}))})
\tag{1.3} \]
\(\quad\)在二分类难点中,当\(\cos(\theta_1)>\cos(\theta_2)\)时,可以规定属于类型一,但分类一与分类二的裁定面是同壹分,表明分类1与分类二之间的距离(margin)一点都极小,直观上的感觉到便是分类不明白。若是要让分类一与分类二有八个眼看的间距,能够做七个决策面,对于项目一的决策平面为:\(\cos(m\theta_1)=\cos(\theta_2)\),对于连串贰的策平面为:\(\cos(\theta_1)=\cos(m\theta_2)\),其中\(m\geq2,m\in N\)。\(m\)是整数的目标是为着便于计算,因为可以采纳倍角公式,\(m\geq2\)表达与该分类的最大夹角要比其他类的细微夹角还要小\(m\)倍。如果\(m=1\),那么体系1与连串2的决策平面是同四个平面,要是\(m\geq2\)v,那么体系一与体系二的有多少个裁定平面,相隔多大将会在性质中验证。从上述的印证与\(L_{modified}\)能够一向获得A-Softmax
Loss:

\[ L_{ang} =
\frac{1}{N}\sum_i-\log(\frac{\exp(\|x_i\|\cos(m\theta_{yi,i}))}{\exp(\|x_i\|\cos(m\theta_{yi,i}))+\sum_{j\neq
y_i}\exp(\|x_i\|\cos(\theta_{j,i}))}) \tag{1.4} \]

其中\(\theta_{yi,i}\in[0,
\frac{\pi}{m}]\),因为\(\theta_{yi,i}\)在那些范围之外可或许会使得\(m\theta_{y_i,i}>\theta_{j,i},j\neq
y_i\)(这样就不属于分类\(y_i\)了),但\(\cos(m\theta_1)>\cos(\theta_2)\)仍恐怕建立,而我辈Loss方程用的大概\(\cos(\theta)\)。为了防止那一个题材,可以再度规划三个函数来取代\(\cos(m\theta_{y_i,i})\),定义\(\psi(\theta_{y_i,i})=(-1)^k\cos(m\theta_{y_i,i})-2k\),其中\(\theta_{y_i,i}\in[\frac{k\pi}{m},\frac{(k+1)\pi}{m}]\),\(且k\in[1,k]\)。那个函数的概念能够使得\(\psi\)随\(\theta_{y_i,i}\)单调递减,倘若\(m\theta_{y_i,i}>\theta_{j,i},j\neq
y_i\), 那么必有\(\psi(\theta_{y_i,i})<\cos(\theta_{j,i})\),反而亦然,那样可避防止上述的题材,所以有:

\[ L_{ang} =
\frac{1}{N}\sum_i-\log(\frac{\exp(\|x_i\|\psi(\theta_{yi,i}))}{\exp(\|x_i\|\psi(\theta_{yi,i}))+\sum_{j\neq
y_i}\exp(\|x_i\|\cos(\theta_{j,i}))}) \tag{1.5} \]

\(\quad\)对于以上二种二分拣难题的Loss(多分类是大抵的事态)的决策面,能够总计如下表:
\[ \begin{array}{|c|l|} \hline
\text{Loss Funtion} & \text{Decision Boundary} \\ \hline
\text{Softmax Loss} & (W_1-W_2)x+b_1-b_2=0\\ \hline
\text{Modified Softmax Loss} &
\|x\|(\cos\theta_1-\cos\theta_2)=0 \\ \hline \text{A-Softmax
Loss} & Class1: \|x\|(\cos m\theta_1-\cos\theta_2)=0 \\ &
Class2: \|x\|(\cos \theta_1-\cos m\theta_2)=0\\ \hline
\end{array} \]

\(\quad\)杂谈中还交到了那三种不一样Loss的几何意义,能够看看的是不乏先例的softmax(Euclidean
Margin
Loss)是在欧氏空间中分离的,它映射到欧氏空间中是差异的区域的长空,决策面是2个在欧氏空间中的平面,能够分隔分化的门类。Modified
Softmax Loss与A-Softmax
Loss的分歧之处在于七个区别类的裁定平面是同三个,不像A-Softmax
Loss,有四个分隔的核定平面且决策平面分隔的高低或许与\(m\)的分寸成正相关,如下图所示。

710官方网站 1

1. A-Softmax的推导

忆起一下二分拣下的Softmax后验概率,即:

\[ \begin{split} p_1 =
\frac{\exp({W}_1^Tx+b_1)}{\exp({W}_1^Tx+b_1)+\exp({W}_2^Tx+b_2)}
\cr p_2 =
\frac{\exp({W}_2^Tx+b_2)}{\exp({W}_1^Tx+b_1)+\exp({W}_2^Tx+b_2)}
\cr \end{split} \tag{1.1} \]

\(\quad\)分明决策的交界在当\(p_1 = p_2\)时,所以决定界面是\((W_1-W_2)x+b_1-b_2=0\)。大家能够将\(W_i^Tx+b_i\)写成\(\|W_i^T\|\cdot\|x\|\cos(\theta_i)+b_i\),其中\(\theta_i\)是\(W_i\)与\(x\)的夹角,如对\(W_i\)归一化且设偏置\(b_i\)为零(\(\|W_i\|=1\),\(b_i=0\)),那么当\(p_1 = p_2\)时,我们有\(\cos(\theta_1)-\cos(\theta_2)=0\)。从此间能够见到,如里2个输入的数目特征\(x_i\)属于\(y_i\)类,那么\(\theta_{yi}\)应该比另外全部类的角度都要小,也正是说在向量空间中\(W_{yi}\)要更靠近\(x_i\)。
\(\quad\)大家用的是Softmax
Loss,对于输入\(x_i\),Softmax Loss
\(L_i\)定义以下:
\[ \begin{split} L_i &=
-\log(\frac{\exp(W_{yi}^Tx_i+b_{yi})}{\sum_j\exp(W_{j}^Tx_i+b_{j})})
\cr &=
-\log(\frac{\exp(\|W_{yi}^T\|·\|x_i\|\cos(\theta_{yi,i})+b_{yi})}{\sum_j\exp(\|W_{j}^T\|·\|x_i\|\cos(\theta_{j,i})+b_{j})})
\cr \end{split} \tag{1.2} \]
式\((1.2)\)中的\(j\in[1,K]\),其中\(K\)类别的总额。下面大家限制了有的尺度:\(\|W_i\|=1\),\(b_i=0\),由这么些规则,能够收获改良的损失函数(也正是舆论中因故说的modified
softmax loss):
\[ L_{modified} =
\frac{1}{N}\sum_i-\log(\frac{\exp(\|x_i\|\cos(\theta_{yi,i}))}{\sum_j\exp(\|x_i\|\cos(\theta_{j,i}))})
\tag{1.3} \]
\(\quad\)在二分类难题中,当\(\cos(\theta_1)>\cos(\theta_2)\)时,能够规定属于类型壹,但分类1与分类2的仲裁面是同壹分,表明分类一与分类2之间的距离(margin)相当的小,直观上的觉得就是分类不显明。假若要让分类1与分类二有三个深入人心的间距,能够做四个决策面,对于项目1的裁定平面为:\(\cos(m\theta_1)=\cos(\theta_2)\),对于体系贰的策平面为:\(\cos(\theta_1)=\cos(m\theta_2)\),其中\(m\geq2,m\in N\)。\(m\)是整数的目标是为了方便总计,因为能够利用倍角公式,\(m\geq2\)表明与该分类的最大夹角要比任何类的微小夹角还要小\(m\)倍。如果\(m=1\),那么类别1与连串二的裁定平面是同二个平面,若是\(m\geq2\)v,那么连串一与连串二的有三个裁定平面,相隔多老马会在质量中验证。从上述的求证与\(L_{modified}\)能够直接获得A-Softmax
Loss:

\[ L_{ang} =
\frac{1}{N}\sum_i-\log(\frac{\exp(\|x_i\|\cos(m\theta_{yi,i}))}{\exp(\|x_i\|\cos(m\theta_{yi,i}))+\sum_{j\neq
y_i}\exp(\|x_i\|\cos(\theta_{j,i}))}) \tag{1.4} \]

其中\(\theta_{yi,i}\in[0,
\frac{\pi}{m}]\),因为\(\theta_{yi,i}\)在那一个限制之外可恐怕会使得\(m\theta_{y_i,i}>\theta_{j,i},j\neq
y_i\)(那样就不属于分类\(y_i\)了),但\(\cos(m\theta_1)>\cos(\theta_2)\)仍大概建立,而大家Loss方程用的要么\(\cos(\theta)\)。为了制止这几个难题,能够另行设计一个函数来替代\(\cos(m\theta_{y_i,i})\),定义\(\psi(\theta_{y_i,i})=(-1)^k\cos(m\theta_{y_i,i})-2k\),其中\(\theta_{y_i,i}\in[\frac{k\pi}{m},\frac{(k+1)\pi}{m}]\),\(且k\in[1,k]\)。那几个函数的定义可以使得\(\psi\)随\(\theta_{y_i,i}\)单调递减,假使\(m\theta_{y_i,i}>\theta_{j,i},j\neq
y_i\), 那么必有\(\psi(\theta_{y_i,i})<\cos(\theta_{j,i})\),反而亦然,那样能够幸免上述的题材,所以有:

\[ L_{ang} =
\frac{1}{N}\sum_i-\log(\frac{\exp(\|x_i\|\psi(\theta_{yi,i}))}{\exp(\|x_i\|\psi(\theta_{yi,i}))+\sum_{j\neq
y_i}\exp(\|x_i\|\cos(\theta_{j,i}))}) \tag{1.5} \]

\(\quad\)对于以上三种二分类难题的Loss(多分类是大抵的图景)的决策面,能够总计如下表:
\[ \begin{array}{|c|l|} \hline
\text{Loss Funtion} & \text{Decision Boundary} \\ \hline
\text{Softmax Loss} & (W_1-W_2)x+b_1-b_2=0\\ \hline
\text{Modified Softmax Loss} &
\|x\|(\cos\theta_1-\cos\theta_2)=0 \\ \hline \text{A-Softmax
Loss} & Class1: \|x\|(\cos m\theta_1-\cos\theta_2)=0 \\ &
Class2: \|x\|(\cos \theta_1-\cos m\theta_2)=0\\ \hline
\end{array} \]

\(\quad\)诗歌中还提交了那三种差别Loss的几何意义,能够观察的是常见的softmax(Euclidean
Margin
Loss)是在欧氏空间中分其余,它映射到欧氏空间中是例外的区域的空中,决策面是贰个在欧氏空间中的平面,能够分隔分化的门类。Modified
Softmax Loss与A-Softmax
Loss的分化之处在于五个区别类的仲裁平面是同二个,不像A-Softmax
Loss,有五个分隔的决策平面且决策平面分隔的分寸或然与\(m\)的高低成正相关,如下图所示。

710官方网站 2

A.
树链剖分数据结构板题

2. A-Softmax Loss的性质

性质1:A-Softmax Loss定义了三个大角度间隔的求学形式,\(m\)越大这些间隔的角度也就越大,相应区域流形的大小就越小,那就导致了锻炼的职责也越困难。
其1天性是一定简单领悟的,如图一所示:那几个区间的角度为\((m-1)\theta_1\),所以\(m\)越大,则距离的角度就越小;同时\(m\theta_1<\pi\),当所以\(m\)越大,则对应的区域流形\(\theta_1\)就越小。

710官方网站 3

图1:性质壹的示意图

定义1:\(m_{min}\)被定义为当\(m>m_{min}\)时有类内间的最大角度特征距离小于类间的细小角度特征距离。
性质2:在二分类难题中:\(m_{min}>2+\sqrt{3}\),有多分类难题中:\(m_{min}\geq 3\)。
表达:一.对此二分拣难点,设\(W_1\)、\(W_2\)分别是项目一与种类贰的权重,\(W_1\)与\(W_2\)之间的夹角是\(\theta_{12}\),输入的特点为\(x\),那么权重与输入特征之间的夹角就控制了输入的表征属于格外体系,不失一般性地能够认为输入的特征性于连串1,则有\(m\theta_1<\theta_2\)。当\(x\)在\(\theta_{12}\)之间时,如图2所示,可以由\(m\theta_1=\theta_2\)求出那时\(\theta_1\)的最大值为\(\theta_{max1}^{in}=\frac{\theta_{12}}{m+1}\)。

710官方网站 4

图2:$x$在$\theta_{12}$之间时的示意图

当\(x\)在\(\theta_{12}\)之外时,第三种情况是当\(\theta_{12} \leq
\frac{m-1}{m}\pi\),如图3所示,可以由\(m\theta_1=\theta_2\)求出那时\(\theta_1\)的最大值为\(\theta_{max1}^{out}=\frac{\theta_{12}}{m-1}\),还有1种情况就是当\(\theta_1\)与\(\theta_2\)不是同1侧时,\(\theta_{12} <
\frac{m-1}{m}\pi\),如图四所示,能够得到:\(\theta_{max1}^{out}=\frac{2\pi-\theta_{12}}{m+1}\)。

710官方网站 5

图3:$x$在$\theta_{1二}$之外时的示意图

710官方网站 6

图4:$x$在$\theta_{1二}$之外时的示意图

无论是上述中的第二种状态依然其次种情景,类间的矮小角度特征距离如图5所示情况中的\(\theta_{inter}\),所以有:\(\theta_{inter}=(m-1)\theta_1=\frac{m-1}{m+1}\theta_{12}\)。

710官方网站 7

图5:最小的类间距离示意图

上述的分析能够总计为以下方程:
\[ \begin{split}
\frac{\theta_{12}}{m-1} + \frac{\theta_{12}}{m+1} \leq
\frac{m-1}{m+1}\theta_{12}, \theta_{12} \leq \frac{m-1}{m}\pi
\cr \frac{2\pi – \theta_{12}}{m-1} + \frac{\theta_{12}}{m+1}
\leq \frac{m-1}{m+1}\theta_{12}, \theta_{12} >
\frac{m-1}{m}\pi \cr \end{split} \tag{2.1} \]
解上述不等式能够行到\(m_{min} \geq
2+\sqrt{3}\)。
2.对于\(K\)类(\(K\geq 3\))问题,设\(\theta_i^{i+1}\)是权重\(W_i\)与\(W_{i+1}\)的夹角,鲜明最佳的情状是\(W_i\)是均匀分布的,所以有\(\theta_i^{i+1}=\frac{2\pi}{K}\)。对于类内的最大距离与类间的小距离有以下方程:
\[ \frac{\theta_{i}^{i+1}}{m+1}
+ \frac{\theta_{i-1}^{i}}{m+1} <
min\{\frac{(m-1)\theta_{i}^{i+1}}{m+1},
\frac{(m-1)\theta_{i-1}^{i}}{m+1}\} \tag{2.2} \]
能够解得\(m_{min} \geq
3\)。综合上边对\(m_{min}\)的议论,散文中取了\(m=4\)。

2. A-Softmax Loss的性质

性质1:A-Softmax Loss定义了三个大角度间隔的就学格局,\(m\)越大那么些间隔的角度也就越大,相应区域流形的大大小小就越小,那就造成了教练的职分也越困难。
本条天性是格外简单驾驭的,如图一所示:那么些间隔的角度为\((m-1)\theta_1\),所以\(m\)越大,则距离的角度就越小;同时\(m\theta_1<\pi\),当所以\(m\)越大,则附和的区域流形\(\theta_1\)就越小。

710官方网站 8

图一:性质一的示意图

定义1:\(m_{min}\)被定义为当\(m>m_{min}\)时有类内间的最大角度特征距离小于类间的微小角度特征距离。
性质2:在二分类难点中:\(m_{min}>2+\sqrt{3}\),有多分类难题中:\(m_{min}\geq 3\)。
证实:1.对此二分拣难题,设\(W_1\)、\(W_2\)分别是项目一与连串2的权重,\(W_1\)与\(W_2\)之间的夹角是\(\theta_{12}\),输入的特征为\(x\),那么权重与输入特征之间的夹角就决定了输入的风味属于至极连串,不失壹般性地可以认为输入的特征性于类别1,则有\(m\theta_1<\theta_2\)。当\(x\)在\(\theta_{12}\)之间时,如图2所示,可以由\(m\theta_1=\theta_2\)求出那时\(\theta_1\)的最大值为\(\theta_{max1}^{in}=\frac{\theta_{12}}{m+1}\)。

710官方网站 9

图2:$x$在$\theta_{1二}$之间时的示意图

当\(x\)在\(\theta_{12}\)之外时,第3种景况是当\(\theta_{12} \leq
\frac{m-1}{m}\pi\),如图3所示,可以由\(m\theta_1=\theta_2\)求出那时\(\theta_1\)的最大值为\(\theta_{max1}^{out}=\frac{\theta_{12}}{m-1}\),还有1种意况正是当\(\theta_1\)与\(\theta_2\)不是同一侧时,\(\theta_{12} <
\frac{m-1}{m}\pi\),如图四所示,能够赢得:\(\theta_{max1}^{out}=\frac{2\pi-\theta_{12}}{m+1}\)。

710官方网站 10

图3:$x$在$\theta_{1二}$之外时的示意图

710官方网站 11

图4:$x$在$\theta_{1二}$之外时的示意图

不论是上述中的第二种状态照旧其次种状态,类间的矮小角度特征距离如图5所示情形中的\(\theta_{inter}\),所以有:\(\theta_{inter}=(m-1)\theta_1=\frac{m-1}{m+1}\theta_{12}\)。

710官方网站 12

图5:最小的类间距离示意图

上述的辨析能够总计为以下方程:
\[ \begin{split}
\frac{\theta_{12}}{m-1} + \frac{\theta_{12}}{m+1} \leq
\frac{m-1}{m+1}\theta_{12}, \theta_{12} \leq \frac{m-1}{m}\pi
\cr \frac{2\pi – \theta_{12}}{m-1} + \frac{\theta_{12}}{m+1}
\leq \frac{m-1}{m+1}\theta_{12}, \theta_{12} >
\frac{m-1}{m}\pi \cr \end{split} \tag{2.1} \]
解上述不等式能够行到\(m_{min} \geq
2+\sqrt{3}\)。
2.对于\(K\)类(\(K\geq 3\))问题,设\(\theta_i^{i+1}\)是权重\(W_i\)与\(W_{i+1}\)的夹角,显著最佳的状态是\(W_i\)是均匀分布的,所以有\(\theta_i^{i+1}=\frac{2\pi}{K}\)。对于类内的最大距离与类间的小距离有以下方程:
\[ \frac{\theta_{i}^{i+1}}{m+1}
+ \frac{\theta_{i-1}^{i}}{m+1} <
min\{\frac{(m-1)\theta_{i}^{i+1}}{m+1},
\frac{(m-1)\theta_{i-1}^{i}}{m+1}\} \tag{2.2} \]
能够解得\(m_{min} \geq
3\)。综合上边对\(m_{min}\)的议论,诗歌中取了\(m=4\)。

标题马虎:我没看,看不懂。

3. A-Softmax的几何意义

私家认为A-Softmax是依照1个假若:不一致的类位于一个单位超球表面包车型客车分歧区域。从下面也足以了然它的几何意义是权重所代表的在单位超球表面包车型客车点,在练习的历程中,同一类的输入映射到表面上会稳步地向骨干点(这里的宗旨点超过八分之四时候和权重的意义分外)聚集,而到不一致类的权重(恐怕主旨点)稳步地分散开来。\(m\)的分寸是决定同一类点聚集的档次,从而控制了不一致类之间的距离。从图陆能够观察,区别的\(m\)对映射分布的熏陶(作者画的图真美观,也不精通作者是怎么画出来的)。

710官方网站 13

图6:区别的$m$对映射分布的震慑

三. A-Softmax的几何意义

个人觉得A-Softmax是根据一个假使:不一样的类位于2个单位超球表面包车型地铁两样区域。从地点也能够领略它的几何意义是权重所表示的在单位超球表面的点,在教练的长河中,同壹类的输入映射到表面上会稳步地向主导点(那里的中坚点大多数时候和权重的含义分外)聚集,而到分裂类的权重(或然中央点)稳步地分散开来。\(m\)的大小是决定同1类点聚集的档次,从而决定了区别类之间的偏离。从图六能够见到,分歧的\(m\)对映射分布的熏陶(笔者画的图真美观,也不晓得作者是怎么画出来的)。

710官方网站 14

图陆:差别的$m$对映射分布的影响

基本思路:我不会。

4. 源码解读

\(\quad\)小编用Caffe达成了A-Softmax,能够参考那几个wy1iu/SphereFace,来解读当中的部分细节。在实际上的编程中,不供给一贯达成式\((1.4)\)中的\(L_{ang}\),可以在SoftmaxOut层后边加1层\(MarginInnerProduct\),那个文件sphereface_model.prototxt的末尾如上边引用所示,能够看看笔者是加多了1层。具体的C++代码在margin_inner_product_layer.cpp

############### A-Softmax Loss ##############
layer {
  name: "fc6"
  type: "MarginInnerProduct"
  bottom: "fc5"
  bottom: "label"
  top: "fc6"
  top: "lambda"
  param {
    lr_mult: 1
    decay_mult: 1
  }
  margin_inner_product_param {
    num_output: 10572
    type: QUADRUPLE
    weight_filler {
      type: "xavier"
    }
    base: 1000
    gamma: 0.12
    power: 1
    lambda_min: 5
    iteration: 0
  }
}
layer {
  name: "softmax_loss"
  type: "SoftmaxWithLoss"
  bottom: "fc6"
  bottom: "label"
  top: "softmax_loss"
}

\(\quad\)驾驭这几个达成的笔触后,关键看前向和后向传播,今后多数的吃水学习框架都扶助电动求导了(如tensorflow,mxnet的gluon),但小编要么建议我们写后向传来,因为机关求导会消耗显存只怕内部存款和储蓄器(看运营的装置)而且一定不比本身写的成效高。在Forword的历程中,有如下细节:
\[ \begin{split} \cos \theta_{i,j} &=
\frac{\vec{x_i}\cdot\vec{W_j}}{\|\vec{x_i}\|\cdot\|\vec{W_j}\|}
\frac{\vec{x_i}\cdot\vec{W_{norm_j}}}{\|\vec{x_i}\|} \cr
\cos 2\theta &= 2\cos^2 \theta -1 \cr \cos 3\theta &= 4\cos^2
\theta -3 \cos \theta \cr \cos 4\theta &= 8\cos^4 \theta
-8\cos^2 \theta – 1 \cr \end{split} \tag{4.1} \]

\[ M_{i,j} = \begin{cases}
\|\vec{x_i}\|\cos \theta_{i,j} =
\vec{x_i}\cdot\vec{W_{norm_j}}, & \text {if $j \neq y_i$ } \\
\|\vec{x_i}\|\psi(\theta_{i,j}), & \text{if $j = y_i$ }
\end{cases} \tag{4.2} \]
\(M\)是出口,代码中的\(sign\_3\_=(-1)^k,
sign\_4\_=-2k\),Caffe的代码如下:

template <typename Dtype>
void MarginInnerProductLayer<Dtype>::Forward_cpu(const vector<Blob<Dtype>*>& bottom, const vector<Blob<Dtype>*>& top) 
{
  iter_ += (Dtype)1.;
  Dtype base_ = this->layer_param_.margin_inner_product_param().base();
  Dtype gamma_ = this->layer_param_.margin_inner_product_param().gamma();
  Dtype power_ = this->layer_param_.margin_inner_product_param().power();
  Dtype lambda_min_ = this->layer_param_.margin_inner_product_param().lambda_min();
  lambda_ = base_ * pow(((Dtype)1. + gamma_ * iter_), -power_);
  lambda_ = std::max(lambda_, lambda_min_);
  top[1]->mutable_cpu_data()[0] = lambda_;

  /************************* normalize weight *************************/
  Dtype* norm_weight = this->blobs_[0]->mutable_cpu_data();
  Dtype temp_norm = (Dtype)0.;
  for (int i = 0; i < N_; i++) {
    temp_norm = caffe_cpu_dot(K_, norm_weight + i * K_, norm_weight + i * K_);
    temp_norm = (Dtype)1./sqrt(temp_norm);
    caffe_scal(K_, temp_norm, norm_weight + i * K_);
  }

  /************************* common variables *************************/
  // x_norm_ = |x|
  const Dtype* bottom_data = bottom[0]->cpu_data();
  const Dtype* weight = this->blobs_[0]->cpu_data();
  Dtype* mutable_x_norm_data = x_norm_.mutable_cpu_data();
  for (int i = 0; i < M_; i++) {
    mutable_x_norm_data[i] = sqrt(caffe_cpu_dot(K_, bottom_data + i * K_, bottom_data + i * K_));
  }
  Dtype* mutable_cos_theta_data = cos_theta_.mutable_cpu_data();
  caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasTrans, M_, N_, K_, (Dtype)1.,
      bottom_data, weight, (Dtype)0., mutable_cos_theta_data);
  for (int i = 0; i < M_; i++) {
    caffe_scal(N_, (Dtype)1./mutable_x_norm_data[i], mutable_cos_theta_data + i * N_);
  }
  // sign_0 = sign(cos_theta)
  caffe_cpu_sign(M_ * N_, cos_theta_.cpu_data(), sign_0_.mutable_cpu_data());

  /************************* optional variables *************************/
  switch (type_) {
  case MarginInnerProductParameter_MarginType_SINGLE:
    break;
  case MarginInnerProductParameter_MarginType_DOUBLE:
    // cos_theta_quadratic
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)2., cos_theta_quadratic_.mutable_cpu_data());
    break;
  case MarginInnerProductParameter_MarginType_TRIPLE:
    // cos_theta_quadratic && cos_theta_cubic
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)2., cos_theta_quadratic_.mutable_cpu_data());
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)3., cos_theta_cubic_.mutable_cpu_data());
    // sign_1 = sign(abs(cos_theta) - 0.5)
    caffe_abs(M_ * N_, cos_theta_.cpu_data(), sign_1_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, -(Dtype)0.5, sign_1_.mutable_cpu_data());
    caffe_cpu_sign(M_ * N_, sign_1_.cpu_data(), sign_1_.mutable_cpu_data());
    // sign_2 = sign_0 * (1 + sign_1) - 2
    caffe_copy(M_ * N_, sign_1_.cpu_data(), sign_2_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, (Dtype)1., sign_2_.mutable_cpu_data());
    caffe_mul(M_ * N_, sign_0_.cpu_data(), sign_2_.cpu_data(), sign_2_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, - (Dtype)2., sign_2_.mutable_cpu_data());
    break;
  case MarginInnerProductParameter_MarginType_QUADRUPLE:
    // cos_theta_quadratic && cos_theta_cubic && cos_theta_quartic
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)2., cos_theta_quadratic_.mutable_cpu_data());
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)3., cos_theta_cubic_.mutable_cpu_data());
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)4., cos_theta_quartic_.mutable_cpu_data());
    // sign_3 = sign_0 * sign(2 * cos_theta_quadratic_ - 1)
    caffe_copy(M_ * N_, cos_theta_quadratic_.cpu_data(), sign_3_.mutable_cpu_data());
    caffe_scal(M_ * N_, (Dtype)2., sign_3_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, (Dtype)-1., sign_3_.mutable_cpu_data());
    caffe_cpu_sign(M_ * N_, sign_3_.cpu_data(), sign_3_.mutable_cpu_data());
    caffe_mul(M_ * N_, sign_0_.cpu_data(), sign_3_.cpu_data(), sign_3_.mutable_cpu_data());
    // sign_4 = 2 * sign_0 + sign_3 - 3
    caffe_copy(M_ * N_, sign_0_.cpu_data(), sign_4_.mutable_cpu_data());
    caffe_scal(M_ * N_, (Dtype)2., sign_4_.mutable_cpu_data());
    caffe_add(M_ * N_, sign_4_.cpu_data(), sign_3_.cpu_data(), sign_4_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, - (Dtype)3., sign_4_.mutable_cpu_data());
    break;
  default:
    LOG(FATAL) << "Unknown margin type.";
  }

对于背后传出,求推比较费心,而且在小编的源码中练习用了不少的trick,并不能够透过梯度测试,小编写出推导进度,方便大家在看代码的时候能够明白效果用了哪些trick,笔者对那一个trick的表达是有助于模型的地西泮团结收敛,并不曾付诸原理上的解释。

当\(y_i \neq
j\)时,有(留意我源码中对\(W\)求导有鲜明的多少个错误,1个是作者只对\(W_norm\)求导,对不是对\(W\),一个是未曾思索到\(y_i\neq j\)的情况):
\[ \begin{split} \frac{\partial
M_{i,j}}{\partial x_{i,k}}&= \frac{\partial
(\vec{x_i}\cdot\vec{W_{norm_j}})}{\partial x_{i,k}} =
W_{norm_{k,j}} \cr \frac{\partial M_{i,j}}{\partial W_{k,j}}&=
\frac{\partial
(\vec{x_i}\cdot\vec{W_{j}}/\|\vec{W_j}\|)}{\partial W_{k,j}}
= \frac{1}{\|\vec{W_j}\|}\frac{\partial
(\vec{x_i}\cdot\vec{W_{j}})}{\partial
W_{k,j}}+(\vec{x_i}\cdot\vec{W_{j}})\frac{\partial
(1/\|\vec{W_j}\|)}{\partial W_{k,j}} \cr &=
\frac{x_{i,k}}{\|\vec{W_j}\|} – \frac{W_{norm_{k,j}}\cos
\theta_{i,j} \|\vec{x_i}\|}{\|\vec{W_j}\|} \end{split}
\tag{4.3} \]

在那边自身仅于\(m=4\)为例子,当\(y_i=j,m=4\),有:
\[ \begin{split} if \quad
M_{1,i,j}&=\|\vec{x_i}\|\cos(\theta_{i,j})\cr
M_{i,j}&=\|\vec{x_i}\|\psi(\theta_{i,j}) =
(-1)^k[8\|\vec{x_i}\|^{-3}M_{1,i,j}^4-8\|\vec{x_i}\|^{-1}M_{1,i,j}^2

  • \|\vec{x_i}\|] – 2k\|\vec{x_i}\| \cr \frac{\partial
    M_{i,j}}{\partial x_{i,k}}&=
    ((-1)^k(-24\|\vec{x_i}\|^{-4}M_{1,i,j}^4 + 8
    \|\vec{x_i}\|^{-2}M_{1,i,j}^2 + 1)
    -2k)\frac{\partial\|\vec{x}\|}{\partial x_{i,k}}\cr & +
    (-1)^k(32\|\vec{x_i}\|^{-3}M_{1,i,j}^3 –
    16\|\vec{x_i}\|^{-1}M_{1,i,j})\frac{\partial
    M_{1,i,j}}{\partial x_{i,k}} \cr &= ((-1)^k(-24\cos^4
    \theta_{i,j} + 8 \cos^2 \theta_{i,j} + 1) -2k)x_{i,k}\cr & +
    (-1)^k(32\cos^3 \theta_{i,j} – 16\cos \theta_{i,j})W_{k,j}\cr
    \frac{\partial M_{i,j}}{\partial W_{k,j}}&= (-1)^k(32\cos^3
    \theta_{i,j} – 16\cos
    \theta_{i,j})(\frac{x_{i,k}}{\|\vec{W_j}\|} –
    \frac{W_{norm_{k,j}}\cos \theta_{i,j}
    \|\vec{x_i}\|}{\|\vec{W_j}\|})\cr \end{split} \tag{4.4}
    \]
    要留心的是上述的\(i,j,k\)分别第i个样本、第j个出口特征和第k个输入特征。上边的仅是演绎偏导数的进度,并不曾涉及到梯度残差的反向传播,假如上层传过来的梯度残差为\(\Delta\),本层的向下层传播的残差为\(\delta\)(二个样书中的2个特点要对拥有的输出累加),权重的更新值为\(\zeta\)(2个权根本对富有的样本量累加),则能够收获:

\[ \begin{split} \delta_{i,k} = \sum_j
\frac{\partial M_{i,j}}{\partial x_{i,k}}\Delta_{i,j} \cr
\zeta_{k,j} = \sum_i \frac{\partial M_{i,j}}{\partial
W_{k,j}}\Delta_{i,j} \end{split} \tag{4.5} \]

Caffe代码如下:

template <typename Dtype>
void MarginInnerProductLayer<Dtype>::Backward_cpu(const vector<Blob<Dtype>*>& top,
    const vector<bool>& propagate_down,
    const vector<Blob<Dtype>*>& bottom) {

  const Dtype* top_diff = top[0]->cpu_diff();
  const Dtype* bottom_data = bottom[0]->cpu_data();
  const Dtype* label = bottom[1]->cpu_data();
  const Dtype* weight = this->blobs_[0]->cpu_data();

  // Gradient with respect to weight
  if (this->param_propagate_down_[0]) {
    caffe_cpu_gemm<Dtype>(CblasTrans, CblasNoTrans, N_, K_, M_, (Dtype)1.,
        top_diff, bottom_data, (Dtype)1., this->blobs_[0]->mutable_cpu_diff());
  }

  // Gradient with respect to bottom data
  if (propagate_down[0]) {
    Dtype* bottom_diff = bottom[0]->mutable_cpu_diff();
    const Dtype* x_norm_data = x_norm_.cpu_data();
    caffe_set(M_ * K_, Dtype(0), bottom_diff);
    switch (type_) {
    case MarginInnerProductParameter_MarginType_SINGLE: {
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, (Dtype)1.,
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)0.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    case MarginInnerProductParameter_MarginType_DOUBLE: {
      const Dtype* sign_0_data = sign_0_.cpu_data();
      const Dtype* cos_theta_data = cos_theta_.cpu_data();
      const Dtype* cos_theta_quadratic_data = cos_theta_quadratic_.cpu_data();
      for (int i = 0; i < M_; i++) {
        const int label_value = static_cast<int>(label[i]);
        for (int j = 0; j < N_; j++) {
          if (label_value != j) {
            // 1 / (1 + lambda) * w
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j], 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
          } else {
            // 4 * sign_0 * cos_theta * w
            Dtype coeff_w = (Dtype)4. * sign_0_data[i * N_ + j] * cos_theta_data[i * N_ + j];
            // 1 / (-|x|) * (2 * sign_0 * cos_theta_quadratic + 1) * x
            Dtype coeff_x = (Dtype)1. / (-x_norm_data[i]) * ((Dtype)2. * 
                            sign_0_data[i * N_ + j] * cos_theta_quadratic_data[i * N_ + j] + (Dtype)1.);
            Dtype coeff_norm = sqrt(coeff_w * coeff_w + coeff_x * coeff_x);
            coeff_w = coeff_w / coeff_norm;
            coeff_x = coeff_x / coeff_norm;
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_w, 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_x, 
                            bottom_data + i * K_, (Dtype)1., bottom_diff + i * K_);
          }
        }
      }
      // + lambda/(1 + lambda) * w
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, lambda_/((Dtype)1. + lambda_),
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)1.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    case MarginInnerProductParameter_MarginType_TRIPLE: {
      const Dtype* sign_1_data = sign_1_.cpu_data();
      const Dtype* sign_2_data = sign_2_.cpu_data();
      const Dtype* cos_theta_quadratic_data = cos_theta_quadratic_.cpu_data();
      const Dtype* cos_theta_cubic_data = cos_theta_cubic_.cpu_data();
      for (int i = 0; i < M_; i++) {
        const int label_value = static_cast<int>(label[i]);
        for (int j = 0; j < N_; j++) {
          if (label_value != j) {
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j], 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
          } else {
            // sign_1 * (12 * cos_theta_quadratic - 3) * w
            Dtype coeff_w = sign_1_data[i * N_ + j] * ((Dtype)12. * 
                            cos_theta_quadratic_data[i * N_ + j] - (Dtype)3.);
            // 1 / (-|x|) * (8 * sign_1 * cos_theta_cubic - sign_2) * x
            Dtype coeff_x = (Dtype)1. / (-x_norm_data[i]) * ((Dtype)8. * sign_1_data[i * N_ + j] * 
                              cos_theta_cubic_data[i * N_ + j] - sign_2_data[i * N_ +j]);
            Dtype coeff_norm = sqrt(coeff_w * coeff_w + coeff_x * coeff_x);
            coeff_w = coeff_w / coeff_norm;
            coeff_x = coeff_x / coeff_norm;
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_w, 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_x, 
                            bottom_data + i * K_, (Dtype)1., bottom_diff + i * K_);
          }
        }
      }
      // + lambda/(1 + lambda) * w
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, lambda_/((Dtype)1. + lambda_),
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)1.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    case MarginInnerProductParameter_MarginType_QUADRUPLE: {
      const Dtype* sign_3_data = sign_3_.cpu_data();
      const Dtype* sign_4_data = sign_4_.cpu_data();
      const Dtype* cos_theta_data = cos_theta_.cpu_data();
      const Dtype* cos_theta_quadratic_data = cos_theta_quadratic_.cpu_data();
      const Dtype* cos_theta_cubic_data = cos_theta_cubic_.cpu_data();
      const Dtype* cos_theta_quartic_data = cos_theta_quartic_.cpu_data();
      for (int i = 0; i < M_; i++) {
        const int label_value = static_cast<int>(label[i]);
        for (int j = 0; j < N_; j++) {
          if (label_value != j) {
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j], 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
          } else {
            // 1 / (1 + lambda) * sign_3 * (32 * cos_theta_cubic - 16 * cos_theta) * w
            Dtype coeff_w = sign_3_data[i * N_ + j] * ((Dtype)32. * cos_theta_cubic_data[i * N_ + j] -
                                (Dtype)16. * cos_theta_data[i * N_ + j]);
            // 1 / (-|x|) * (sign_3 * (24 * cos_theta_quartic - 8 * cos_theta_quadratic - 1) + 
            //                        sign_4) * x
            Dtype coeff_x = (Dtype)1. / (-x_norm_data[i]) * (sign_3_data[i * N_ + j] * 
                            ((Dtype)24. * cos_theta_quartic_data[i * N_ + j] - 
                            (Dtype)8. * cos_theta_quadratic_data[i * N_ + j] - (Dtype)1.) - 
                             sign_4_data[i * N_ + j]);
            Dtype coeff_norm = sqrt(coeff_w * coeff_w + coeff_x * coeff_x);
            coeff_w = coeff_w / coeff_norm;
            coeff_x = coeff_x / coeff_norm;
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_w, 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_x, 
                            bottom_data + i * K_, (Dtype)1., bottom_diff + i * K_);
          }
        }
      }
      // + lambda/(1 + lambda) * w
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, lambda_/((Dtype)1. + lambda_),
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)1.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    default: {
      LOG(FATAL) << "Unknown margin type.";
    }
    }
  }
}

4. 源码解读

\(\quad\)作者用Caffe达成了A-Softmax,能够参见那些wy1iu/SphereFace,来解读个中的一对细节。在实质上的编制程序中,不须要向来完成式\((1.4)\)中的\(L_{ang}\),能够在SoftmaxOut层前边加一层\(MarginInnerProduct\),这几个文件sphereface_model.prototxt的终极如下边引用所示,能够观察小编是加多了1层。具体的C++代码在margin_inner_product_layer.cpp

############### A-Softmax Loss ##############
layer {
  name: "fc6"
  type: "MarginInnerProduct"
  bottom: "fc5"
  bottom: "label"
  top: "fc6"
  top: "lambda"
  param {
    lr_mult: 1
    decay_mult: 1
  }
  margin_inner_product_param {
    num_output: 10572
    type: QUADRUPLE
    weight_filler {
      type: "xavier"
    }
    base: 1000
    gamma: 0.12
    power: 1
    lambda_min: 5
    iteration: 0
  }
}
layer {
  name: "softmax_loss"
  type: "SoftmaxWithLoss"
  bottom: "fc6"
  bottom: "label"
  top: "softmax_loss"
}

\(\quad\)精通这一个达成的笔触后,关键看前向和后向传播,以后大多数的纵深学习框架都支持电动求导了(如tensorflow,mxnet的gluon),但自身要么提出我们写后向传来,因为机关求导会消耗显存也许内部存储器(看运营的设施)而且一定比不上自身写的功用高。在Forword的进度中,有如下细节:
\[ \begin{split} \cos \theta_{i,j} &=
\frac{\vec{x_i}\cdot\vec{W_j}}{\|\vec{x_i}\|\cdot\|\vec{W_j}\|}
\frac{\vec{x_i}\cdot\vec{W_{norm_j}}}{\|\vec{x_i}\|} \cr
\cos 2\theta &= 2\cos^2 \theta -1 \cr \cos 3\theta &= 4\cos^2
\theta -3 \cos \theta \cr \cos 4\theta &= 8\cos^4 \theta
-8\cos^2 \theta – 1 \cr \end{split} \tag{4.1} \]

\[ M_{i,j} = \begin{cases}
\|\vec{x_i}\|\cos \theta_{i,j} =
\vec{x_i}\cdot\vec{W_{norm_j}}, & \text {if $j \neq y_i$ } \\
\|\vec{x_i}\|\psi(\theta_{i,j}), & \text{if $j = y_i$ }
\end{cases} \tag{4.2} \]
\(M\)是出口,代码中的\(sign\_3\_=(-1)^k,
sign\_4\_=-2k\),Caffe的代码如下:

template <typename Dtype>
void MarginInnerProductLayer<Dtype>::Forward_cpu(const vector<Blob<Dtype>*>& bottom, const vector<Blob<Dtype>*>& top) 
{
  iter_ += (Dtype)1.;
  Dtype base_ = this->layer_param_.margin_inner_product_param().base();
  Dtype gamma_ = this->layer_param_.margin_inner_product_param().gamma();
  Dtype power_ = this->layer_param_.margin_inner_product_param().power();
  Dtype lambda_min_ = this->layer_param_.margin_inner_product_param().lambda_min();
  lambda_ = base_ * pow(((Dtype)1. + gamma_ * iter_), -power_);
  lambda_ = std::max(lambda_, lambda_min_);
  top[1]->mutable_cpu_data()[0] = lambda_;

  /************************* normalize weight *************************/
  Dtype* norm_weight = this->blobs_[0]->mutable_cpu_data();
  Dtype temp_norm = (Dtype)0.;
  for (int i = 0; i < N_; i++) {
    temp_norm = caffe_cpu_dot(K_, norm_weight + i * K_, norm_weight + i * K_);
    temp_norm = (Dtype)1./sqrt(temp_norm);
    caffe_scal(K_, temp_norm, norm_weight + i * K_);
  }

  /************************* common variables *************************/
  // x_norm_ = |x|
  const Dtype* bottom_data = bottom[0]->cpu_data();
  const Dtype* weight = this->blobs_[0]->cpu_data();
  Dtype* mutable_x_norm_data = x_norm_.mutable_cpu_data();
  for (int i = 0; i < M_; i++) {
    mutable_x_norm_data[i] = sqrt(caffe_cpu_dot(K_, bottom_data + i * K_, bottom_data + i * K_));
  }
  Dtype* mutable_cos_theta_data = cos_theta_.mutable_cpu_data();
  caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasTrans, M_, N_, K_, (Dtype)1.,
      bottom_data, weight, (Dtype)0., mutable_cos_theta_data);
  for (int i = 0; i < M_; i++) {
    caffe_scal(N_, (Dtype)1./mutable_x_norm_data[i], mutable_cos_theta_data + i * N_);
  }
  // sign_0 = sign(cos_theta)
  caffe_cpu_sign(M_ * N_, cos_theta_.cpu_data(), sign_0_.mutable_cpu_data());

  /************************* optional variables *************************/
  switch (type_) {
  case MarginInnerProductParameter_MarginType_SINGLE:
    break;
  case MarginInnerProductParameter_MarginType_DOUBLE:
    // cos_theta_quadratic
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)2., cos_theta_quadratic_.mutable_cpu_data());
    break;
  case MarginInnerProductParameter_MarginType_TRIPLE:
    // cos_theta_quadratic && cos_theta_cubic
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)2., cos_theta_quadratic_.mutable_cpu_data());
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)3., cos_theta_cubic_.mutable_cpu_data());
    // sign_1 = sign(abs(cos_theta) - 0.5)
    caffe_abs(M_ * N_, cos_theta_.cpu_data(), sign_1_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, -(Dtype)0.5, sign_1_.mutable_cpu_data());
    caffe_cpu_sign(M_ * N_, sign_1_.cpu_data(), sign_1_.mutable_cpu_data());
    // sign_2 = sign_0 * (1 + sign_1) - 2
    caffe_copy(M_ * N_, sign_1_.cpu_data(), sign_2_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, (Dtype)1., sign_2_.mutable_cpu_data());
    caffe_mul(M_ * N_, sign_0_.cpu_data(), sign_2_.cpu_data(), sign_2_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, - (Dtype)2., sign_2_.mutable_cpu_data());
    break;
  case MarginInnerProductParameter_MarginType_QUADRUPLE:
    // cos_theta_quadratic && cos_theta_cubic && cos_theta_quartic
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)2., cos_theta_quadratic_.mutable_cpu_data());
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)3., cos_theta_cubic_.mutable_cpu_data());
    caffe_powx(M_ * N_, cos_theta_.cpu_data(), (Dtype)4., cos_theta_quartic_.mutable_cpu_data());
    // sign_3 = sign_0 * sign(2 * cos_theta_quadratic_ - 1)
    caffe_copy(M_ * N_, cos_theta_quadratic_.cpu_data(), sign_3_.mutable_cpu_data());
    caffe_scal(M_ * N_, (Dtype)2., sign_3_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, (Dtype)-1., sign_3_.mutable_cpu_data());
    caffe_cpu_sign(M_ * N_, sign_3_.cpu_data(), sign_3_.mutable_cpu_data());
    caffe_mul(M_ * N_, sign_0_.cpu_data(), sign_3_.cpu_data(), sign_3_.mutable_cpu_data());
    // sign_4 = 2 * sign_0 + sign_3 - 3
    caffe_copy(M_ * N_, sign_0_.cpu_data(), sign_4_.mutable_cpu_data());
    caffe_scal(M_ * N_, (Dtype)2., sign_4_.mutable_cpu_data());
    caffe_add(M_ * N_, sign_4_.cpu_data(), sign_3_.cpu_data(), sign_4_.mutable_cpu_data());
    caffe_add_scalar(M_ * N_, - (Dtype)3., sign_4_.mutable_cpu_data());
    break;
  default:
    LOG(FATAL) << "Unknown margin type.";
  }

对于背后传出,求推比较费心,而且在作者的源码中练习用了不少的trick,并不可能通过梯度测试,作者写出推导进程,方便大家在看代码的时候可以知晓效果用了怎样trick,小编对这一个trick的解说是推进模型的平稳收敛,并不曾提交原理上的表明。

当\(y_i \neq
j\)时,有(只顾小编源码中对\(W\)求导有肯定的三个错误,贰个是作者只对\(W_norm\)求导,对不是对\(W\),三个是绝非考虑到\(y_i\neq j\)的情况):
\[ \begin{split} \frac{\partial
M_{i,j}}{\partial x_{i,k}}&= \frac{\partial
(\vec{x_i}\cdot\vec{W_{norm_j}})}{\partial x_{i,k}} =
W_{norm_{k,j}} \cr \frac{\partial M_{i,j}}{\partial W_{k,j}}&=
\frac{\partial
(\vec{x_i}\cdot\vec{W_{j}}/\|\vec{W_j}\|)}{\partial W_{k,j}}
= \frac{1}{\|\vec{W_j}\|}\frac{\partial
(\vec{x_i}\cdot\vec{W_{j}})}{\partial
W_{k,j}}+(\vec{x_i}\cdot\vec{W_{j}})\frac{\partial
(1/\|\vec{W_j}\|)}{\partial W_{k,j}} \cr &=
\frac{x_{i,k}}{\|\vec{W_j}\|} – \frac{W_{norm_{k,j}}\cos
\theta_{i,j} \|\vec{x_i}\|}{\|\vec{W_j}\|} \end{split}
\tag{4.3} \]

在那里作者仅于\(m=4\)为例子,当\(y_i=j,m=4\),有:
\[ \begin{split} if \quad
M_{1,i,j}&=\|\vec{x_i}\|\cos(\theta_{i,j})\cr
M_{i,j}&=\|\vec{x_i}\|\psi(\theta_{i,j}) =
(-1)^k[8\|\vec{x_i}\|^{-3}M_{1,i,j}^4-8\|\vec{x_i}\|^{-1}M_{1,i,j}^2

  • \|\vec{x_i}\|] – 2k\|\vec{x_i}\| \cr \frac{\partial
    M_{i,j}}{\partial x_{i,k}}&=
    ((-1)^k(-24\|\vec{x_i}\|^{-4}M_{1,i,j}^4 + 8
    \|\vec{x_i}\|^{-2}M_{1,i,j}^2 + 1)
    -2k)\frac{\partial\|\vec{x}\|}{\partial x_{i,k}}\cr & +
    (-1)^k(32\|\vec{x_i}\|^{-3}M_{1,i,j}^3 –
    16\|\vec{x_i}\|^{-1}M_{1,i,j})\frac{\partial
    M_{1,i,j}}{\partial x_{i,k}} \cr &= ((-1)^k(-24\cos^4
    \theta_{i,j} + 8 \cos^2 \theta_{i,j} + 1) -2k)x_{i,k}\cr & +
    (-1)^k(32\cos^3 \theta_{i,j} – 16\cos \theta_{i,j})W_{k,j}\cr
    \frac{\partial M_{i,j}}{\partial W_{k,j}}&= (-1)^k(32\cos^3
    \theta_{i,j} – 16\cos
    \theta_{i,j})(\frac{x_{i,k}}{\|\vec{W_j}\|} –
    \frac{W_{norm_{k,j}}\cos \theta_{i,j}
    \|\vec{x_i}\|}{\|\vec{W_j}\|})\cr \end{split} \tag{4.4}
    \]
    要小心的是上述的\(i,j,k\)分别第i个样本、第j个出口特征和第k个输入特征。下边包车型地铁仅是演绎偏导数的历程,并不曾涉嫌到梯度残差的反向传播,尽管上层传过来的梯度残差为\(\Delta\),本层的向下层传播的残差为\(\delta\)(3个样书中的1个天性要对全数的输出累加),权重的更新值为\(\zeta\)(三个权根本对具备的样本量累加),则能够赢得:

\[ \begin{split} \delta_{i,k} = \sum_j
\frac{\partial M_{i,j}}{\partial x_{i,k}}\Delta_{i,j} \cr
\zeta_{k,j} = \sum_i \frac{\partial M_{i,j}}{\partial
W_{k,j}}\Delta_{i,j} \end{split} \tag{4.5} \]

Caffe代码如下:

template <typename Dtype>
void MarginInnerProductLayer<Dtype>::Backward_cpu(const vector<Blob<Dtype>*>& top,
    const vector<bool>& propagate_down,
    const vector<Blob<Dtype>*>& bottom) {

  const Dtype* top_diff = top[0]->cpu_diff();
  const Dtype* bottom_data = bottom[0]->cpu_data();
  const Dtype* label = bottom[1]->cpu_data();
  const Dtype* weight = this->blobs_[0]->cpu_data();

  // Gradient with respect to weight
  if (this->param_propagate_down_[0]) {
    caffe_cpu_gemm<Dtype>(CblasTrans, CblasNoTrans, N_, K_, M_, (Dtype)1.,
        top_diff, bottom_data, (Dtype)1., this->blobs_[0]->mutable_cpu_diff());
  }

  // Gradient with respect to bottom data
  if (propagate_down[0]) {
    Dtype* bottom_diff = bottom[0]->mutable_cpu_diff();
    const Dtype* x_norm_data = x_norm_.cpu_data();
    caffe_set(M_ * K_, Dtype(0), bottom_diff);
    switch (type_) {
    case MarginInnerProductParameter_MarginType_SINGLE: {
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, (Dtype)1.,
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)0.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    case MarginInnerProductParameter_MarginType_DOUBLE: {
      const Dtype* sign_0_data = sign_0_.cpu_data();
      const Dtype* cos_theta_data = cos_theta_.cpu_data();
      const Dtype* cos_theta_quadratic_data = cos_theta_quadratic_.cpu_data();
      for (int i = 0; i < M_; i++) {
        const int label_value = static_cast<int>(label[i]);
        for (int j = 0; j < N_; j++) {
          if (label_value != j) {
            // 1 / (1 + lambda) * w
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j], 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
          } else {
            // 4 * sign_0 * cos_theta * w
            Dtype coeff_w = (Dtype)4. * sign_0_data[i * N_ + j] * cos_theta_data[i * N_ + j];
            // 1 / (-|x|) * (2 * sign_0 * cos_theta_quadratic + 1) * x
            Dtype coeff_x = (Dtype)1. / (-x_norm_data[i]) * ((Dtype)2. * 
                            sign_0_data[i * N_ + j] * cos_theta_quadratic_data[i * N_ + j] + (Dtype)1.);
            Dtype coeff_norm = sqrt(coeff_w * coeff_w + coeff_x * coeff_x);
            coeff_w = coeff_w / coeff_norm;
            coeff_x = coeff_x / coeff_norm;
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_w, 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_x, 
                            bottom_data + i * K_, (Dtype)1., bottom_diff + i * K_);
          }
        }
      }
      // + lambda/(1 + lambda) * w
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, lambda_/((Dtype)1. + lambda_),
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)1.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    case MarginInnerProductParameter_MarginType_TRIPLE: {
      const Dtype* sign_1_data = sign_1_.cpu_data();
      const Dtype* sign_2_data = sign_2_.cpu_data();
      const Dtype* cos_theta_quadratic_data = cos_theta_quadratic_.cpu_data();
      const Dtype* cos_theta_cubic_data = cos_theta_cubic_.cpu_data();
      for (int i = 0; i < M_; i++) {
        const int label_value = static_cast<int>(label[i]);
        for (int j = 0; j < N_; j++) {
          if (label_value != j) {
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j], 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
          } else {
            // sign_1 * (12 * cos_theta_quadratic - 3) * w
            Dtype coeff_w = sign_1_data[i * N_ + j] * ((Dtype)12. * 
                            cos_theta_quadratic_data[i * N_ + j] - (Dtype)3.);
            // 1 / (-|x|) * (8 * sign_1 * cos_theta_cubic - sign_2) * x
            Dtype coeff_x = (Dtype)1. / (-x_norm_data[i]) * ((Dtype)8. * sign_1_data[i * N_ + j] * 
                              cos_theta_cubic_data[i * N_ + j] - sign_2_data[i * N_ +j]);
            Dtype coeff_norm = sqrt(coeff_w * coeff_w + coeff_x * coeff_x);
            coeff_w = coeff_w / coeff_norm;
            coeff_x = coeff_x / coeff_norm;
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_w, 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_x, 
                            bottom_data + i * K_, (Dtype)1., bottom_diff + i * K_);
          }
        }
      }
      // + lambda/(1 + lambda) * w
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, lambda_/((Dtype)1. + lambda_),
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)1.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    case MarginInnerProductParameter_MarginType_QUADRUPLE: {
      const Dtype* sign_3_data = sign_3_.cpu_data();
      const Dtype* sign_4_data = sign_4_.cpu_data();
      const Dtype* cos_theta_data = cos_theta_.cpu_data();
      const Dtype* cos_theta_quadratic_data = cos_theta_quadratic_.cpu_data();
      const Dtype* cos_theta_cubic_data = cos_theta_cubic_.cpu_data();
      const Dtype* cos_theta_quartic_data = cos_theta_quartic_.cpu_data();
      for (int i = 0; i < M_; i++) {
        const int label_value = static_cast<int>(label[i]);
        for (int j = 0; j < N_; j++) {
          if (label_value != j) {
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j], 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
          } else {
            // 1 / (1 + lambda) * sign_3 * (32 * cos_theta_cubic - 16 * cos_theta) * w
            Dtype coeff_w = sign_3_data[i * N_ + j] * ((Dtype)32. * cos_theta_cubic_data[i * N_ + j] -
                                (Dtype)16. * cos_theta_data[i * N_ + j]);
            // 1 / (-|x|) * (sign_3 * (24 * cos_theta_quartic - 8 * cos_theta_quadratic - 1) + 
            //                        sign_4) * x
            Dtype coeff_x = (Dtype)1. / (-x_norm_data[i]) * (sign_3_data[i * N_ + j] * 
                            ((Dtype)24. * cos_theta_quartic_data[i * N_ + j] - 
                            (Dtype)8. * cos_theta_quadratic_data[i * N_ + j] - (Dtype)1.) - 
                             sign_4_data[i * N_ + j]);
            Dtype coeff_norm = sqrt(coeff_w * coeff_w + coeff_x * coeff_x);
            coeff_w = coeff_w / coeff_norm;
            coeff_x = coeff_x / coeff_norm;
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_w, 
                            weight + j * K_, (Dtype)1., bottom_diff + i * K_);
            caffe_cpu_axpby(K_, (Dtype)1. / ((Dtype)1. + lambda_) * top_diff[i * N_ + j] * coeff_x, 
                            bottom_data + i * K_, (Dtype)1., bottom_diff + i * K_);
          }
        }
      }
      // + lambda/(1 + lambda) * w
      caffe_cpu_gemm<Dtype>(CblasNoTrans, CblasNoTrans, M_, K_, N_, lambda_/((Dtype)1. + lambda_),
        top_diff, this->blobs_[0]->cpu_data(), (Dtype)1.,
        bottom[0]->mutable_cpu_diff());
      break;
    }
    default: {
      LOG(FATAL) << "Unknown margin type.";
    }
    }
  }
}

参考代码:找Oyk老师和Czj老师去。

A-Softmax的效果

在磨炼模型(training)用的是A-Softmax函数,但在辨明分类结果(vilidation)用的是余弦相似原理,如下图七所示:

710官方网站 15

图7

所用的模子如图8所示:

710官方网站 16

图8

效率如下所示(详细的对待,请看原稿):

710官方网站 17

图9

A-Softmax在较小的数额集合上有着美妙的机能且理论具有正确的可解释性,它的缺陷也领悟即是总括量相对相比大,可能这正是作者在诗歌中绝非测试大数据集的来头。

A-Softmax的效果

在练习模型(training)用的是A-Softmax函数,但在辨明分类结果(vilidation)用的是余弦相似原理,如下图七所示:

710官方网站 18

图7

所用的模型如图八所示:

710官方网站 19

图8

功能如下所示(详细的比较,请看原稿):

710官方网站 20

图9

A-Softmax在较小的数量集合上有着精美的功能且理论具有正确的可解释性,它的弱点也赫赫有名就是总结量相对相比大,或然这便是作者在随想中尚无测试大数据集的因由。

 

与L-Softmax的区别

A-Softmax与L-Softmax的最大区别在于A-Softmax的权重归1化了,而L-Softmax则没的。A-Softmax权重的归一化导致特征上的点映射到单位超球面上,而L-Softmax则不未有这么些限制,那个脾气使得两方在几何的分解上是不平等的。如图10所示,假如在教练时七个体系的天性输入在同2个区域时,如下图十所示。A-Softmax只好从角度上分度那五个品类,也正是说它仅从可行性上区分类,分类的结果如图11所示;而L-Softmax,不仅能够从角度上分别八个类,还可以从权重的模(长度)上有别那多个类,分类的结果如图1二所示。在数量集合大小固定的规格下,L-Softmax能有多少个法子分类,练习大概未有使得它在角度与长度方向都分别,导致它的标准只怕不比A-Softmax。

710官方网站 21

图10:系列一与品种二映射到特征空间发出了区域的重合

710官方网站 22

图1一:A-Softmax分类大概的结果

710官方网站 23

图1二:L-Softmax分类可能的结果

【幸免爬虫转发而造成的格式难题——链接】:http://www.cnblogs.com/heguanyou/p/7503025.html

与L-Softmax的区别

A-Softmax与L-Softmax的最大分化在于A-Softmax的权重归1化了,而L-Softmax则没的。A-Softmax权重的归1化导致特征上的点映射到单位超球面上,而L-Softmax则不未有这么些限制,那本性格使得两岸在几何的解说上是不平等的。如图拾所示,借使在教练时五个档次的性状输入在同二个区域时,如下图10所示。A-Softmax只可以从角度上分度那五个体系,约等于说它仅从可行性上区分类,分类的结果如图1壹所示;而L-Softmax,不仅可以从角度上分别八个类,还是能够从权重的模(长度)上有别那三个类,分类的结果如图1贰所示。在数量集合大小固定的规格下,L-Softmax能有多个章程分类,训练恐怕未有使得它在角度与长度方向都分别,导致它的可相信只怕比不上A-Softmax。

710官方网站 24

图十:体系一与项目二映射到特征空间发出了区域的重合

710官方网站 25

图1一:A-Softmax分类恐怕的结果

710官方网站 26

图1二:L-Softmax分类恐怕的结果

【幸免爬虫转发而致使的格式难点——链接】:http://www.cnblogs.com/heguanyou/p/7503025.html

B. The
background of water problem

标题大意(大写加粗的水题):给定$N$个学生和她们$K$个科指标成就$S_i$,再付出各科目$K_i$的权重顺序$Q_i$,求排行之后,拥有id为$X$的是哪些学生。

基本思路:纵然$K$唯有$10$,$S$唯有$十0$,但有M组查询,所以自然不可能开个long
long去hash每一种学员。我们大致点,开个结构体,排个序,就好了。

参照代码

官方代码(将培育和id分开放,制止在排序时复制构造大结构体):

710官方网站 27710官方网站 28

 1 #include <cstdio>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 
 7 int N,K,M,X;
 8 int people[1005][11];
 9 int cmpOrder[11];
10 
11 struct CmpNode{
12     CmpNode(int x):id(x){}
13     int id;
14     bool operator < (const CmpNode &other) const
15     {
16         for(int i=0; i<K; i++)
17         {
18             if(people[this->id][cmpOrder[i]] > people[other.id][cmpOrder[i]])
19                 return true;
20             else if(people[this->id][cmpOrder[i]] < people[other.id][cmpOrder[i]])
21                 return false;
22         }
23         return this->id<other.id;
24     }
25 };
26 
27 void solve(FILE *fin=stdin, FILE *fout=stdout)
28 {
29     int t;
30     fscanf(fin,"%d",&t);
31     while(t--)
32     {
33         fscanf(fin,"%d%d",&N,&K);
34         vector<CmpNode> nodes;
35         for(int i=0;i<N;i++)
36         {
37             nodes.push_back(CmpNode(i));
38             for(int j=1;j<=K;j++)
39                 fscanf(fin,"%d",&people[i][j]);
40         }
41         fscanf(fin,"%d",&M);
42         while(M--)
43         {
44             for(int i=0;i<K;i++)
45                 fscanf(fin,"%d",cmpOrder+i);
46             fscanf(fin,"%d", &X);
47             sort(nodes.begin(),nodes.end());
48             fprintf(fout,"%d\n",nodes[X-1].id+1);
49         }
50     }
51 }
52 
53 int main()
54 {
55     solve(stdin,stdout);
56     return 0;
57 }

B. The background of water
problem

非官方代码(那是清一色放在结构体的事例,无论算法竞技照旧工程都不建议那样排序):

710官方网站 29710官方网站 30

 1 #include <stdio.h>
 2 #include <algorithm>
 3 
 4 int N, K, M, X;
 5 int order[11];
 6 
 7 struct stu {
 8     int id, score[11];
 9     bool operator <(const stu&x) const {
10         for(int i=1; i<=K; i++)
11             if(score[order[i]] != x.score[order[i]])
12                 return score[order[i]] > x.score[order[i]];
13         return id < x.id;
14     }
15 }student[1001];
16 
17 int main() {
18     int T;
19     scanf("%d", &T);
20     while(T--) {
21         scanf("%d%d", &N, &K);
22         for(int i=1; i<=N; i++) {
23             student[i].id = i;
24             for(int j=1; j<=K; j++)
25                 scanf("%d", &student[i].score[j]);
26         }
27         scanf("%d", &M);
28         while(M--) {
29             for(int i=1; i<=K; i++)
30                 scanf("%d", order+i);
31             std::sort(student+1, student+1+N);
32             scanf("%d", &X);
33             printf("%d\n", student[X].id);
34         }
35     }
36     return 0;
37 }

B. The background of water
problem 

 

C. Oyk
cut paper forever

标题马虎

  永远的Oyk剪纸(灰霾)。Oyk给面子Z大师,玩$C$轮剪纸,每轮给定一条长为$k$个单位的纸带,Z大师先手能够剪去(任意)$N_1$个单位,但无法不剪或任何拿走。此后每轮都不得不剪$一$到$2\times
N_一$个单位,能拿走最后壹段纸带的人制伏,问Oyk第三回制伏是第几轮。

基本思路

  斐波那契博弈,声明参见:

  原题参见
hdoj 2516.
取石子游戏
 等。

  首先知道了那是个斐波那契博弈,接下去我们要做的正是判断$K_i$是或不是为Fibonacci数。简单想到的是用递推打一个表,将Fibonacci数存起来或标志一下。不过大家清楚斐波那契数列通项公式为$F_n=\frac1{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right]$(比内公式),还知道判断一个数$x$是还是不是为Fibonacci数只需判断$五x^2+四$或$伍x^贰-4$是还是不是为完全平方数(参考:Wiki示例)(即判断开根号后是还是不是为整数),于是Over。

参考代码

合法代码(丧sha病bi出题人改了少数波代码,大家依旧伪装下边包车型大巴是对的呢):

710官方网站 31710官方网站 32

 1 #include <cstdlib>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int T;
 9     scanf("%d",&T);
10     while(T--){
11         int n,i;
12         int ans=0;
13         scanf("%d",&n);
14         for(i = 1;i<=n;i++){
15             int a;
16             scanf("%d",&a);
17             if(!ans&&(sqrt(5*a*a+4)-(int)sqrt(5*a*a+4)<1e-6||sqrt(5*a*a-4)-(int)sqrt(5*a*a-4)<1e-6)){
18                 ans=i;
19             }
20         }
21         if(ans)printf("%d\n",ans);
22         else puts("Oyk forever!");
23     }
24     return 0;
25 }

C. OykOyk!

非官方代码(打表出奇迹):

710官方网站 33710官方网站 34

 1 #include <stdio.h>
 2 using namespace std;
 3 
 4 int flag[100100];
 5 void init() {
 6     int a = 1, b = 2;
 7     while(b<=100000) {
 8         ++flag[b];
 9         b += a;
10         a = b-a;
11     }
12 }
13 int main() {
14     int T; init();
15     scanf("%d", &T);
16     while(T--) {
17         int C, k, res=0;
18         scanf("%d", &C);
19         for(int i=1; i<=C; i++) {
20             scanf("%d", &k);
21             if(!res&&flag[k])
22                 res = i;
23         }
24         res?printf("%d\n", res):puts("Oyk forever!");
25     }
26     return 0;
27 }

C. Oyk forever!

 

D.
最小开销流

标题马虎

  挖$n$天的财富,每一日要求$RAV4_i$只铲子,当天用完会坏掉。有$三$种艺术准备铲子:从集团买,$p$元1只;找铁匠$A$修理,每只$f$元同时修$m$天;找铁匠$B$修理,每只$s$元同时修$t$天。问最小费用。

基本思路

  最小开支流,参见网络流二四题之餐巾难点。

参考代码

710官方网站 35710官方网站 36

  1 #include <iostream>
  2 #include<stdio.h>
  3 #include<string.h>
  4 #define INF 99999999
  5 #define min(x,y) (x)>(y)?(y):(x)
  6 #define abs(x) ((x)>0?(x):-(x))
  7 #define E 50000
  8 struct p
  9 {
 10     int v,next,k,t,cost;
 11 }edge[200000];
 12 int n,m,ans,tot,S,T,head[1001],pre[1001],pid[1001],pop[100001];
 13 int mark[1001],dis[1001],now[1001];
 14 void addedge(int a,int b,int k,int cost)
 15 {
 16     edge[tot].v=b;
 17     edge[tot].k=k;
 18     edge[tot].cost=cost;
 19     edge[tot].t=tot+1;
 20     edge[tot].next=head[a];
 21     head[a]=tot++;
 22 
 23     edge[tot].v=a;
 24     edge[tot].k=0;
 25     edge[tot].cost=-cost;
 26     edge[tot].t=tot-1;
 27     edge[tot].next=head[b];
 28     head[b]=tot++;
 29 }
 30 int spfa()
 31 {
 32     int i,top,tail,cur;
 33     for(i=0;i<=T;i++)
 34         dis[i]=INF,mark[i]=0;
 35     top=tail=0;
 36     pop[top++]=S;
 37     dis[S]=0;
 38     mark[S]=1;
 39     while(tail!=top)
 40     {
 41         cur=pop[tail++];
 42         tail%=50000;
 43         mark[cur]=0;
 44         for(i=head[cur];i!=-1;i=edge[i].next)
 45             if(edge[i].k>0&&dis[edge[i].v]>dis[cur]+edge[i].cost)
 46             {
 47                 dis[edge[i].v]=dis[cur]+edge[i].cost;
 48                 pre[edge[i].v]=cur;
 49                 pid[edge[i].v]=i;
 50                 if(mark[edge[i].v]==0)
 51                 {
 52                     mark[edge[i].v]=1;
 53                     pop[top++]=edge[i].v;
 54                     top%=50000;
 55                 }
 56             }
 57     }
 58     return dis[T];
 59 }
 60 int mincost()
 61 {
 62     int i,flow,tmp,ans,maxflow=0;
 63     ans=0;
 64     while(1)
 65     {
 66         tmp=spfa();
 67         if(tmp==INF) break;
 68         flow=INF;
 69         for(i=T;i!=S;i=pre[i])
 70             if(edge[pid[i]].k<flow)
 71                 flow=edge[pid[i]].k;
 72         for(i=T;i!=S;i=pre[i])
 73         {
 74             edge[pid[i]].k-=flow;
 75             edge[edge[pid[i]].t].k+=flow;
 76         }
 77         maxflow+=flow;
 78         ans+=tmp*flow;
 79     }
 80     return ans;
 81 }
 82 int main()
 83 {
 84     freopen("in.txt","r",stdin);
 85     freopen("out.txt","w",stdout);
 86     int i,j,p,m1,f,m2,s,tmp;
 87     while(scanf("%d%d%d%d%d%d",&n,&p,&m1,&f,&m2,&s)!=EOF)
 88     {
 89         memset(edge,0xff,sizeof(edge));
 90         tot=n*2+3;
 91         S=0;
 92         T=n*2+1;
 93         for(i=1;i<=n;i++)
 94         {
 95             scanf("%d",&tmp);
 96             tmp++;
 97             addedge(S,i+n,INF,p);
 98             addedge(S,i,tmp,0);
 99             addedge(i+n,T,tmp,0);
100             if(i<n) addedge(i,i+1,INF,0);
101             if(i+m1<=n) addedge(i,n+i+m1,INF,f);
102             if(i+m2<=n) addedge(i,n+i+m2,INF,s);
103         }
104         printf("%d\n",mincost());
105     }
106     return 0;
107 }

D. Dig the treasure

 

E.
Wwj’s work

标题大意:这题是HDOJ
4622. Reincarnation
原题,有且仅有数量是团结造的。。

基本思路:求3个字符串的子串数目,标准的后缀自动机。当然就像也足现在缀数组、后缀xxx什么的乱搞。

参照代码:(参考kuangbin的模板,和代码

710官方网站 37710官方网站 38

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int CHAR = 26;
 7 const int MAXN = 2020;
 8 struct SAM_Node {
 9     SAM_Node *fa, *next[CHAR];
10     int len;
11     int id,pos;
12     SAM_Node() {}
13     SAM_Node(int _len) {
14         fa = 0;
15         len = _len;
16         memset(next,0,sizeof(next));
17     }
18 };
19 SAM_Node SAM_node[MAXN*2], *SAM_root, *SAM_last;
20 int SAM_size;
21 SAM_Node *newSAM_Node(int len) {
22     SAM_node[SAM_size] = SAM_Node(len);
23     SAM_node[SAM_size].id = SAM_size;
24     return &SAM_node[SAM_size++];
25 }
26 SAM_Node *newSAM_Node(SAM_Node *p) {
27     SAM_node[SAM_size] = *p;
28     SAM_node[SAM_size].id = SAM_size;
29     return &SAM_node[SAM_size++];
30 }
31 void SAM_init() {
32     SAM_size = 0;
33     SAM_root = SAM_last = newSAM_Node(0);
34     SAM_node[0].pos = 0;
35 }
36 void SAM_add(int x,int len) {
37     SAM_Node *p = SAM_last, *np = newSAM_Node(p->len+1);
38     np->pos = len;
39     SAM_last = np;
40     for(; p && !p->next[x]; p = p->fa)
41         p->next[x] = np;
42     if(!p) {
43         np->fa = SAM_root;
44         return;
45     }
46     SAM_Node *q = p->next[x];
47     if(q->len == p->len + 1) {
48         np->fa = q;
49         return;
50     }
51     SAM_Node *nq = newSAM_Node(q);
52     nq->len = p->len + 1;
53     q->fa = nq;
54     np->fa = nq;
55     for(; p && p->next[x] == q; p = p->fa)
56         p->next[x] = nq;
57 }
58 
59 int sub[MAXN][MAXN];
60 char S[MAXN];
61 void read() {
62     memset(sub, 0, sizeof(sub));
63     scanf("%s", S);
64     int len = strlen(S);
65     for(int i=0; i<len; i++) {
66         SAM_init();
67         for(int j=i; j<len; j++)
68             SAM_add(S[j]-'a', j-i+1);
69         for(int j=1; j<SAM_size; j++)
70             sub[i][ SAM_node[j].pos+i-1 ]
71                 += SAM_node[j].len - SAM_node[j].fa->len;
72         for(int j=i+1; j<len; j++)
73             sub[i][j] += sub[i][j-1];
74     }
75 }
76 void work() {
77     int Q, l, r;
78     scanf("%d", &Q);
79     while(Q--) {
80         scanf("%d%d", &l, &r);
81         printf("%d\n", sub[l-1][r-1]);
82     }
83 }
84 int main() {
85     int T;
86     scanf("%d", &T);
87     while(T--) {
88         read();
89         work();
90     }
91     return 0;
92 }

E. Wwj’s work

 

F.
防AK题,dfs+高斯消元

标题马虎:我没看,看不懂。

基本思路:我不会。

参照代码:找Czj去。

 

G. Not
Easy Math Problem

难题马虎:$F(m,n)=\left\{\begin{matrix}\begin{aligned}&B*2^{m-1},&n=0\\&\sum_{i=1}^m
F(i,
n-1),&n>0\end{aligned}\end{matrix}\right.$,其中$m<10^6$,$n<10^3$,$B<10$,求$F(m,n)\%(1E8+7)$。

基本思路

  递推法

    先调查前方若干行若干列,发现各种系数构成杨辉三角。代多少个数进去发现 $\displaystyle
F(m,n)=B*\sum_{i=0}^{m-1}C_{m-i+n-2}^{n-1}*2^i$。

    $O(M)$肯定会TLE啊,算算算 $\displaystyle
\frac{2F(m,n)-F(m,n)}{B}=C_{n-1}^{n-1}*2^m-C_{m+n-2}^{n-1}*2^0+\sum_{i=1}^{m-1}\left(C_{m-i+n-1}^{n-1}-C_{m-i+n-2}^{n-1}\right)*2^i$

    发现能够应用组合数个性,令$\displaystyle
T(n-1)=\sum_{i=0}^{m-1}C_{m-i+n-2}^{n-1}*2^i$,$\displaystyle
T(n-2)=\sum_{i=0}^{m-1}C_{m-i+n-2}^{n-2}*2^i$

    则$\displaystyle
T(n-1)=C_{n-1}^{n-1}*2^m-C_{m+n-2}^{n-1}+T(n-2)-C_{m+n-2}^{n-2}$

    递推下去得$\displaystyle
T(n-1)=2^{n-1}*2^m-2*\sum_{i=0}^{n-2}C_{m+n-2}^i-C_{m+n-2}^{n-1}$

    来个飞跃幂,再预处理下逆元和组合数,$O(log(M+N)+N)$跑得飞快($log$里面包车型客车$N$能够在后面预处理组合数的轮回去掉,丑就是了)。

  数学归咎法

    参见
hdoj. 5490 题解。归结公式为$\displaystyle
F(m,n)=\frac{q*F(m,n-1)-B*C_{m+n-二}^{n-一}}{q-一}$,然后递推,时间复杂度$O(log(M)+N)$(假如用便捷幂算$二^{m-一}$的话)。

参考代码(笔者的终将比标算美观):

710官方网站 39710官方网站 40

 1 #include <stdio.h>
 2 const int MOD = 100000007;
 3 inline int add(int a, int b) { return (a%MOD+b%MOD)%MOD; }
 4 inline int sub(int a, int b) { return ((a-b)%MOD+MOD)%MOD; }
 5 inline int mul(int a, int b) { return int((long long)a%MOD*(b%MOD)%MOD); }
 6 inline int pow(int x, int n) {
 7     int res = 1;
 8     while(n) {
 9         if(n&1) res = mul(res, x);
10         x = mul(x, x);
11         n >>= 1;
12     }
13     return res;
14 }
15 int inv[1001]={1,1};
16 void init() {
17     for(int i=2; i<=1000; i++)
18         inv[i] = mul(inv[MOD%i], MOD-MOD/i);
19 }
20 int B, M, N;
21 void read() {
22     scanf("%d%d%d", &B, &M, &N);
23 }
24 int Binomial[1001]={1};
25 void work() {
26     for(int i=1; i<N; i++)
27         Binomial[i] = mul(mul(Binomial[i-1], M+N-i-1), inv[i]);
28     int res = pow(2, M+N-1);
29     for(int i=0; i<N; i++)
30         res = sub(res, mul(Binomial[i], 2));
31     res = mul(add(res, Binomial[N-1]), B);
32     printf("%d\n", res);
33 }
34 int main() {
35     int T; init();
36     scanf("%d", &T);
37     while(T--) {
38         read();
39         work();
40     }
41     return 0;
42 }

比标算美观一丝丝的 G.

 

H.
Party!

难点马虎

  Wwj和她的女对象们壹起$N$个人去开趴体。各类人一旦还没把温馨的赠品送出去的话,就足以从外人手中接收礼物。第$i$个人得到第$j$人礼物的同时,也会博得四个高兴指数$H_{i,\
j}$。求全体人的高兴指数的总数的最大值。

基本思路

  诶?有人用贪心做?有人用搜索做?据悉还有人用最小生成树做?诶等等那个用无向图MST的怎样心态?这不是有向图?(小编的天呐.jpg)

  那题能够跑1个互连网流,当然也足以DP。何人告诉您给一个矩阵就势必是图论题了?mdzz。

  能DP我当然不写互联网流,考虑收红包状态矩阵$M$,$M_{i,\
j}$代表第$i$个人收没收第$j$人的礼金($i\neq
j$),收了为$1$,没收为$0$。鉴于各样人惟有1份礼品,他只好送给1位,所以在同等列内最七唯有$1$个$一$,所以状态矩阵$M$能够直接拍扁。好的,$N\leq
10$,我们能够愉悦地气象压缩了,状态数$2^N-一$,dp时间复杂度$O(二^N
N^二)$。

  思考任意状态state,假如第$i\geq
0$位为$1$(即$state\&(1<<i)!=0$),则申明该意况下第$i$个人已经把他的红包给出去了(当然也不容许发生给自身的情况)。对每三个情景求最大欢愉指数,再取全数景况的最大值。

参照代码

710官方网站 41710官方网站 42

 1 #include <stdio.h>
 2 
 3 int N, H[11][11];
 4 inline void getMax(int&n, int x) { if(n<x) n=x; }
 5 void read() {
 6     scanf("%d", &N);
 7     for(int i=0; i<N; i++)
 8         for(int j=0; j<N; j++)
 9             scanf("%d", H[i]+j);
10 }
11 void work() {
12     int maxState = 1<<N, dp[maxState]={0};
13     for(int state=0; state<maxState; state++)
14         for(int i=0; i<N; i++) if(!(state&(1<<i)))
15             for(int j=0; j<N; j++) if(i!=j&&!(state&(1<<j)))
16                 getMax(dp[state+(1<<j)], dp[state]+H[i][j]);
17     int res = 0;
18     for(int state=0; state<maxState; state++)
19         getMax(res, dp[state]);
20     printf("%d\n", res);
21 }
22 int main() {
23     int T;
24     scanf("%d",&T);
25     while(T--) {
26         read();
27         work();
28     }
29     return 0;
30 }

H. Party!

 

I.
Square

题材大意:$N\times
N$的矩阵,每种格子要填$0$或$一$,须求每行每列中$一$的个数就算奇数个。

基本思路:不考虑范围条件,有$2^{N^2}$种方案对吧?能乱填对啊?那什么样确认保障每行每列中$一$的个数是奇数个?在两旁加多一行加多1列(即$(N+一)\times(N+一)$),对于每一行每1列,借使$1$的个数是偶数个,再填个$一$,不然填$0$进去。啥?剩下那些格子如何是好?会1边奇数一边偶数?嗯,由于是$N\times
N$,所以是不容许的。由此$S_N=二^{(N-壹)^贰}$,连忙幂或然意想不到的优化即可。

参考代码

官方代码(分块处理,把47改成一伍,不用long
long用int也是足以的,当然时间就差个2.5倍咯):

710官方网站 43710官方网站 44

 1 #include <stdio.h>
 2 #define ULL unsigned long long
 3 int main() {
 4     ULL res;
 5     int n;
 6     int T;
 7     scanf("%d",&T);
 8     while(T--) {
 9         scanf("%d",&n);
10         res=1;
11         for(ULL i = 0; i<(ULL)(n-1)*(n-1)/47; i++)
12             res=(res<<47)%100007;
13         for(ULL i = 0; i<(ULL)(n-1)*(n-1)%47; i++)
14             res=(res*2)%100007;
15         printf("%d\n",res);
16     }
17     return 0;
18 }

I. Square

非官方代码(连忙幂,怎么说也是log的复杂度,比上面竟然的优化要快便是了):

710官方网站 45710官方网站 46

 1 #include <stdio.h>
 2 const int MOD = 100007;
 3 long long pow(long long x, int n) {
 4     long long res = 1LL;
 5     while(n) {
 6         if(n&1) res = res*x%MOD;
 7         x = x*x%MOD;
 8         n >>= 1;
 9     }
10     return res;
11 }
12 int main() {
13     int T, N;
14     scanf("%d",&T);
15     while(T--) {
16         scanf("%d",&N);
17         --N; N *= N;
18         printf("%d\n", pow(2, N));
19     }
20     return 0;
21 }

I. Square

 

J.
Rotate and skew

题目马虎

  windows系统里面有个“画图”工具,相信我们一定不会目生。但个中没有转动任意$x$角度的作用,只有“扭曲”的功用。如逆时针旋转$28^\circ$,我们发现能够先对$x$轴扭曲$-1四^\circ$,再对$y$轴扭曲$25^\circ$,再对$x$轴扭曲$-14^\circ$,就马到成功辣!问给定角度$x$,输出三次扭曲的角度。

基本思路

  好多同桌可能1早先先取个基向量,比如$\vec
b=(0,1)$,然后想$x$轴扭曲$-14^\circ$应该是$\vec{b’}=(tan14^\circ,1)$,$y$轴再反过来$二伍^\circ$应该是$\vec{b”}=(tan14^\circ,
1-tan25^\circ)$,再反过来一下……再$arc
tan$一下……咦?怎么出来的不是$2捌^\circ$了?

  Naive。如若是那般那还叫扭曲吗?那叫拉伸!你倒是把$x$乘进去啊!把$y$乘进去啊!

  • 先是考虑基向量$\vec
    a=(1,0)$。设旋转角度$\theta$。先水平扭曲任意角度,不变。垂直扭曲$\varphi$,$\vec{a’}=(1,
    tan\varphi)$,再水平扭曲3次得$\vec{a”}=(1-tan(x),
    tan\varphi)$,和$tan\theta$解一下发觉$x=\frac\theta2$,于是知道了档次扭曲角度。
  • 正解(1):思考向量$\vec
    x=\begin{bmatrix}x\\y\end{bmatrix}$,水平扭曲矩阵$A=\begin{bmatrix}1&tan(-\frac\theta2)\\0&1\end{bmatrix}$, ($A\vec
    x=\begin{bmatrix}x+ytan(-\frac\theta2)\\y\end{bmatrix}$,看不懂的学线代去)

    • 五个扭曲矩阵相乘应该是$M=ABA$,当中大家渴求的是此中的垂直扭曲矩阵$B$。
    • 已知旋转矩阵$M=\begin{bmatrix}cos\theta&-sin\theta\\sin\theta&cos\theta\end{bmatrix}$,解得$B=\begin{bmatrix}1&0\\sin\theta&1\end{bmatrix}$。
    • 唯独我们的垂直扭曲矩阵应该要长大$B=\begin{bmatrix}1&0\\tan\varphi&1\end{bmatrix}$的样子。
    • 据此大家须求用$tan$正切值去模拟$sin$正弦值(本来就是供给用扭曲模拟旋转)。
  • 正解(2):再考虑基向量$\vec
    b=(0,1)$。

    • 联立化简
      $\left\{\begin{matrix}\begin{aligned}&x_1=x_0+y_0*tan(-\frac\theta2)\\&y_1=y_0+x_1*tan(\varphi)\\&x_2=x_1+y_1*tan(-\frac\theta2)\end{aligned}\end{matrix}\right.$,$\left\{\begin{matrix}\begin{aligned}&x_0=0,\
      y_0=1\\&tan(-\theta)=\frac{x_2}{y_1}\end{aligned}\end{matrix}\right.$
       得
       $\displaystyle\frac{tan(\frac\theta2)[sec(\theta)tan(\varphi)-tan(\theta)]}{tan(\frac\theta2)tan(\varphi)-1}=0$

    • $sec(\theta)tan(\varphi)=tan(\theta)$ 得笔直扭曲角度
      $\varphi=tan^{-1}sin(\theta)$
    • 啥?你还要$+k\pi$?你还要分母不为$0$?$\theta$不为$0$?那都要作者解,你咋不上天呢。
  • 察觉标题对精度必要不高,反正切取个整即可。也能够一贯打个垂直扭曲角度的表。
  • 更加多请参见
     Matrix陆七—线性代数的妙用:怎么着在Windows画图软件中落实28度旋转?

参考代码

对基向量$\vec
b=(0,1)$的模拟:

 1 #include <stdio.h>
 2 #include <math.h>
 3 const double PI = acos(-1.L);
 4 int main() {
 5     double x = 0.0, y = 1.0;
 6     x = x + tan(-14.*PI/180.) * y;
 7     y = y + tan(25.*PI/180.) * x;///注意这里是tan25模拟sin28,若这里直接用sin28则最后atan回来的结果是28.0整
 8     x = x + tan(-14.*PI/180.) * y;
 9     printf("%f\n", atan(x/y)*180./PI);
10     return 0;
11 }

法定代码:

1 // http://scarky.com/widget/getiframe/PLNRB5QG/
2 #include <stdio.h>
3 int y[]={0,2,4,6,8,10,12,14,15,17,19,21,22,24,25,27,28,29,30,32,33,34,35};
4 int main(int i) {
5   while(~scanf("%d", &i))
6     i/=2, printf("%d %d %d\n", -i, i>0?y[i]:-y[-i], -i);
7   return 0;
8 }

非官方代码:

1 #include <stdio.h>
2 #include <math.h>
3 const double PI = acos(-1.L);
4 int main() {
5     int x;
6     while(~scanf("%d", &x))
7         printf("%d %.f %d\n", -x/2, round(atan(sin(x*PI/180.))*180./PI), -x/2);
8     return 0;
9 }

 

 

——原创by
BlackStorm,转发请申明出处。

正文地址:http://www.cnblogs.com/BlackStorm/p/5380872.html

相关文章