SMALE训练营作业

第一天

上午

题1.6

问题描述：描述你在学习、使用数学表达式时的困难, 可举例说明.
答：1.数学表达式有很多细节不知道，导致表达式错误或者不专业。比如集合之间的映射要用“$\mapsto$”，而函数的映射关系用“$\to$”.
2.如何把自己心里的算法思路表达成数学式？数学表达式又该如何用语言简单明了解释它，不知道从何处下手.
3.定义数学表达式不够严谨，经不起推敲.

下午

题2.6

1.令 A = { 3 , 5 } \mathbf{A}=\{3, 5\} A={3,5}，写出$2^{\mathbf{A}}$.
答： 2 A = { ∅ , { 3 } , { 5 } , { 3 , 5 } } 2^{\mathbf{A}}=\{\emptyset, \{3\}, \{5\}, \{3, 5\}\} 2A={∅,{3},{5},{3,5}}.
2.展开$2^{\varnothing }$.
答：$|2^{\varnothing }|=2^{|\varnothing |}=2^0=1$,故 2 ∅ = { ∅ } 2^{\empty}=\{\empty\} 2∅={∅}.
3.令 A = { 5 , 6 , 7 , 8 , 9 } \mathbf{A}=\{5, 6, 7, 8, 9\} A={5,6,7,8,9},写出$\mathbf{A}$的其他两种表达式.
答：①$\mathbf{A}=[5..9]$；② A = { x ∈ N ∣ x ∈ [ 5 , 9 ] } \mathbf{A}=\{x \in \mathbf{N} \vert x\in[5,9]\} A={x∈N∣x∈[5,9]}；③ A = { 5 , 6 , … , 9 } \mathbf{A}=\{5, 6, \dots, 9\} A={5,6,…,9}.

晚上

题3.3

问题描述：自己出一个数据，做一个$3\times 2$与$2\times 4$的矩阵乘法.
答：设$\mathbf{A}=\left[\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right]$,$\mathbf{B}=\left[\begin{array}{cccc}1& 2& 3& 4\\ 5& 6& 7& 8\end{array}\right]$,则$$\mathbf{A}\times \mathbf{B}=\left[\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right]\times \left[\begin{array}{cccc}1& 2& 3& 4\\ 5& 6& 7& 8\end{array}\right]=\left[\begin{array}{cccc}11& 14& 7& 20\\ 23& 30& 17& 44\\ 35& 46& 27& 68\end{array}\right]$$

补充题

问题描述：找出Deep Multi-View 符号系统的矛盾
答：
如上标注：
①：${\mathbf{o}}_{\mathbf{i}}$为一个对象，应该是一个向量，此处应该为黑体.
②：此处“m”应该为斜体.
③：$\mathbf{B}$为一个集合，不应该使用$\in$,而是$\subseteq$.
④：1D代表一维，应该表达为：$1-D$.
⑥：前文的正1未加“+”号，前后不一致.

第二天

上午

题4.6

1.令 A = { 1 , 2 , 5 , 8 , 9 } \mathbf{A}=\{1, 2, 5, 8, 9\} A={1,2,5,8,9},写出$\mathbf{A}$上的“模2同余”关系及相应的划分.
答： R = { ( a , b ) ∈ A × A ∣ a m o d 2 = b m o d 2 } \mathbf{R}=\{(a,b)\in\mathbf{A}\times\mathbf{A} \vert a\mod2=b\mod2\} R={(a,b)∈A×A∣amod2=bmod2}.
模2余0：$(2,2),(2,8),(8,2),(8,8)$
模2余1：$(1,1),(1,5),(1,9),(5,1),(5,5),(5,9),(9,1),(9,5),(9,9)$
故： R = { ( 2 , 2 ) , ( 2 , 8 ) , ( 8 , 2 ) , ( 8 , 8 ) , ( 1 , 1 ) , ( 1 , 5 ) , ( 1 , 9 ) , ( 5 , 1 ) , ( 5 , 5 ) , ( 5 , 9 ) , ( 9 , 1 ) , ( 9 , 5 ) , ( 9 , 9 ) } \mathbf{R}=\{(2, 2),(2, 8),(8, 2),(8, 8),(1,1),(1,5),(1,9),(5,1),(5,5),(5,9),(9,1),(9,5),(9,9)\} R={(2,2),(2,8),(8,2),(8,8),(1,1),(1,5),(1,9),(5,1),(5,5),(5,9),(9,1),(9,5),(9,9)}.
P = { { 2 , 8 } , { 1 , 5 , 9 } } \mathcal{P}=\{\{2,8\}, \{1, 5, 9\}\} P={{2,8},{1,5,9}}
2. A = { 1 , 2 , 5 , 8 , 9 } \mathbf{A}=\{1, 2, 5, 8, 9\} A={1,2,5,8,9},自己给定两个关系${\mathbf{R}}_1$和${\mathbf{R}}_2$，并计算${\mathbf{R}}_1{\mathbf{R}}_2,{\mathbf{R}}_1^{+},{\mathbf{R}}_1^{\ast }$.
答：设 R 1 = { ( 1 , 2 ) , ( 1 , 5 ) } , R 2 = { ( 2 , 1 ) , ( 5 , 8 ) } \mathbf{R}_1=\{(1, 2), (1, 5)\},\mathbf{R}_2=\{(2,1), (5,8)\} R1​={(1,2),(1,5)},R2​={(2,1),(5,8)}
R 2 ∘ R 1 = { ( 1 , 1 ) , ( 1 , 8 ) } \mathbf{R}_2 \circ\mathbf{R}_1=\{(1,1), (1,8)\} R2​∘R1​={(1,1),(1,8)}
${\mathbf{R}}_1^{+}={\bigcup }_{i=1}^{|\mathbf{A}|}{\mathbf{R}}_1^i={\mathbf{R}}_1^1\cup {\mathbf{R}}_1^2\cup {\mathbf{R}}_1^3\cup {\mathbf{R}}_1^4\cup {\mathbf{R}}_1^5,{\mathbf{R}}_1^1={\mathbf{R}}_1,{\mathbf{R}}_1{\mathbf{R}}_1={\mathbf{R}}_1^3={\mathbf{R}}_1^4={\mathbf{R}}_1^5=\varnothing .$
故 R 1 + = R 1 = { ( 1 , 2 ) , ( 1 , 5 ) } \mathbf{R}_1^+=\mathbf{R}_1=\{(1, 2), (1,5)\} R1+​=R1​={(1,2),(1,5)}.
R 1 ∗ = R 1 + ∪ R 0 , R 0 = { ( 1 , 1 ) , ( 2 , 2 ) , ( 5 , 5 ) , ( 8 , 8 ) , ( 9 , 9 ) } \mathbf{R}_1^*=\mathbf{R}_1^+\cup\mathbf{R}^0,\mathbf{R}^0=\{(1,1), (2,2), (5,5), (8,8), (9,9)\} R1∗​=R1+​∪R0,R0={(1,1),(2,2),(5,5),(8,8),(9,9)}
故 R 1 ∗ = { ( 1 , 2 ) , ( 1 , 5 ) , ( 1 , 1 ) , ( 2 , 2 ) , ( 5 , 5 ) , ( 8 , 8 ) , ( 9 , 9 ) } \mathbf{R}_1^*=\{(1,2), (1,5), (1,1), (2,2), (5,5), (8,8), (9,9)\} R1∗​={(1,2),(1,5),(1,1),(2,2),(5,5),(8,8),(9,9)}
3.查阅粗糙集上下近似的定义并大致描述.
答：设$\mathbf{X}\subseteq \mathbf{U}$是任一子集，$\mathbf{R}$是$\mathbf{U}$上的等价关系，下近似集： R ‾ ( X ) = U { Y ∈ U / R , Y ⊆ X } \underline{R}(\mathbf{X})=\mathbf{U}\{\mathbf{Y}\in\mathbf{U}/\mathbf{R},\mathbf{Y} \subseteq \mathbf{X}\} R​(X)=U{Y∈U/R,Y⊆X}.上近似集： R ‾ ( X ) = U { Y ∈ U / R , Y ∩ X ≠ ∅ } \overline{R}(\mathbf{X})=\mathbf{U}\{\mathbf{Y} \in \mathbf{U}/ \mathbf{R},\mathbf{Y}\cap \mathbf{X}\ne \empty\} R(X)=U{Y∈U/R,Y∩X​=∅}.

下午

题5.5

问题描述：举例说明你对函数的认识.
答:函数是一个集合到另一个集合的一对一或者多对一的映射,也可以看作空间的一个点。比如：$z=f(x,y)=x^2+y^2$，二维平面确定的点$(x,y)$有唯一对应的$z$，也可以看作确定的三维空间中的一个唯一确定的点$(x,y,z)$.

晚上

题6.5

问题描述：自己给定一个矩阵并计算其各种范数.
答：设$\mathbf{A}=\left[\begin{array}{cc}1& 2\\ -3& 4\\ 0& 6\end{array}\right]$，则：
∥ A ∥ 0 = ∣ { ( i , j ) ∣ a i j ≠ 0 } ∣ = 5 \|\mathbf{A}\|_0=\lvert \{(i,j)\vert a_{ij} \ne 0\}\rvert=5 ∥A∥0​=∣{(i,j)∣aij​​=0}∣=5.
$\Vert \mathbf{A}{\Vert }_1={\sum }_{i,j}|a_{ij}|=16$.
$\Vert \mathbf{A}{\Vert }_2=\sqrt{{\sum }_{i,j}{a}_{ij}^2}=2\sqrt{11},\Vert {\mathbf{A}\Vert }_2^2={\sum }_{i,j}{a}_{ij}^2=44$.
$\Vert \mathbf{A}{\Vert }_{\infty }={\max }_{i,j}|a_{ij}|=6$.

题7.3

问题描述：解释推荐系统: 问题、算法与研究思路 2.1中的优化目标$$\min \sum _{(i,j)\in \Omega }(f({\mathbf{x}}_i,{\mathbf{t}}_j)-r_{ij}{)}^2$$各符号及含义.
答：对$\forall (i,j)\in \Omega$，即将评分表的每一个数据作为输入，将模型产生的输出与相应的评分表的值求差距的平方的最小值。

第三天

上午

题8.4

1.将向量下标为偶数的分量$(x2,x4,\dots )$累加，写出相应表达式.
答：$$\sum _{i\mathrm{m}\mathrm{o}\mathrm{d}2=0}{x}_i$$

int sum=0;
for(int i=1;i<=n;i++)
{if(i%2==0)sum+=x[i];
}

2 各出一道累加、累乘、积分表达式的习题，并给出标准答案.
累加：$$\sum _{i=1}^{10}i=1+2+3+\cdots +10=55$$

int sum=0;
for(int i=1;i<=10;i++)
{
sum+=i;
}

累乘：$$\prod _{i=1}^3{i}^2=1^2\times 2^2\times 3^2=36$$

int product=1;
for(int i=1;i<=3;i++)product*=i*i;

积分：$${\int }_1^4(2x+1)\mathrm{d}x=(x^2+x){|}_1^4=18$$

double integration=0;
double deltax=0.01;
for(double x=1;x<=4;x+=deltax)
{integration+=(2*x+1)*deltax;
}

3 你使用过三重累加吗？描述一下其应用.
答:三重累加在一定条件下可以转化为三重积分，在数学上，三重积分可以看作是几何体的测度，在物理应用上，可以看作是不均匀物体的质量。
4 给一个常用的积分，将手算结果与程序结果相比对.
答：$${\int }_0^5(2x)\mathrm{d}x=x^2{|}_0^5=25$$
程序：

结果：

下午

题9.3

问题描述：自己写一个小例子$(n=3,m=1)$来验证最小二乘法.
答：给定数据集$\mathbf{X}=[x_{ij}{]}_{3\times 2}=\left[\begin{array}{cc}1& 2\\ 1& 3\\ 1& 4\end{array}\right]$与其标签$\mathbf{Y}=[y_1,\dots ,y_n{]}^{\mathrm{T}}=[5,7,9{]}^{\mathrm{T}}$.
计算$${\mathbf{w}}^{\ast }=\underset{\mathbf{w}}{\mathrm{argmin}}||\mathbf{X}\mathbf{w}-\mathbf{Y}|{|}_2^2,$$其中$$||\mathbf{X}\mathbf{w}-\mathbf{Y}|{|}_2^2=(\mathbf{X}\mathbf{w}-\mathbf{Y}{)}^{\mathrm{T}}(\mathbf{X}\mathbf{w}-\mathbf{Y})=({\mathbf{w}}^{\mathrm{T}}{\mathbf{X}}^{\mathrm{T}}-{\mathbf{Y}}^{\mathrm{T}})(\mathbf{X}\mathbf{w}-\mathbf{Y})={\mathbf{w}}^{\mathrm{T}}{\mathbf{X}}^{\mathrm{T}}\mathbf{X}\mathbf{w}-{\mathbf{w}}^{\mathrm{T}}{\mathbf{X}}^{\mathrm{T}}\mathbf{Y}-{\mathbf{Y}}^{\mathrm{T}}\mathbf{X}\mathbf{w}+{\mathbf{Y}}^{\mathrm{T}}\mathbf{Y}$$
对$\mathbf{w}$求导并令其为0得：$$\mathbf{w}=({\mathbf{X}}^{\mathrm{T}}\mathbf{X}{)}^{-1}{\mathbf{X}}^{\mathrm{T}}\mathbf{Y}=(\left[\begin{array}{ccc}1& 1& 1\\ 2& 3& 4\end{array}\right]\times \left[\begin{array}{cc}1& 2\\ 1& 3\\ 1& 4\end{array}\right]{)}^{-1}\times \left[\begin{array}{ccc}1& 1& 1\\ 2& 3& 4\end{array}\right]\times \left[\begin{array}{c}5\\ 7\\ 9\end{array}\right]$$
$\mathbf{w}=({\mathbf{X}}^{\mathrm{T}}\mathbf{X}{)}^{-1}{\mathbf{X}}^{\mathrm{T}}\mathbf{Y}={\left[\begin{array}{cc}3& 9\\ 9& 29\end{array}\right]}^{-1}\times \left[\begin{array}{c}21\\ 67\end{array}\right]=\left[\begin{array}{cc}\frac{29}{6}& -\frac{3}{2}\\ -\frac{3}{2}& \frac{1}{2}\end{array}\right]\times \left[\begin{array}{c}21\\ 67\end{array}\right]=\left[\begin{array}{c}1\\ 2\end{array}\right]$
得$\mathbf{w}=\left[\begin{array}{c}1\\ 2\end{array}\right]$.故模型为：$y=2x+1$.
验证：$(x_1,y_1)=(2,5):5=2\times 2+1；$
$(x_2,y_2)=(3,7):7=2\times 3+1；$
$(x_3,y_3)=(4,9):9=2\times 4+1；$
故使用最小二乘法得到的结果完全符合数据集的数据.

晚上

题10.6

问题描述：自己推导一遍，并描述这个方法的特点(不少于5条).
答：在二维平面分类，需要一条直线将它们分开，当是多维空间时，需要超平面将两类事物进行分类，分类成正例和负例。如何判断这个超平面将它们的效果是好是坏？可以根据分错的个数来判断，但是存在多个超平面都可以完全分开正例与负例呢，可以根据对象到超平面的距离来衡量（距离越大越好）：分类正确，那么对象离超平面越远越好，分类不正确，离超平面越近越接近0.
1)计算点到超平面的距离=$\mathbf{x}\mathbf{w}$
2)使用sigmoid函数将距离转换为概率$P(y=1|\mathbf{x};\mathbf{w})=\frac{1}{1+e^{-\mathbf{x}\mathbf{w}}}$；
含义为：距离越大，那么它是正例的概率接近1；如果距离很小$(-\infty )$时，它是正例的概率几乎为0，它为负例的概率接近1.
3)统一$y_i=0$或$y_i=1$：$P(y_i|{\mathbf{x}}_i;\mathbf{w})=P(y_i=1|{\mathbf{x}}_i;\mathbf{w}{)}^{y_i}(1-P(y_i=1|{\mathbf{x}}_i;\mathbf{w}){)}^{1-y_i}$
当$y_i=1$时：$P(y_i|{\mathbf{x}}_i;\mathbf{w})=P(y_i=1|{\mathbf{x}}_i;\mathbf{w})$
当$y_i=0$时：$P(y_i|{\mathbf{x}}_i;\mathbf{w})=1-P(y_i=1|{\mathbf{x}}_i;\mathbf{w})$
4）因为是概率，故用最大似然估计来定义优化目标：$$\mathbf{w}=\underset{\mathbf{w}}{\mathrm{argmax}}\prod _{i=1}^{n}P(y_i|{\mathbf{x}}_i;\mathbf{w})$$
5)计算最大似然估计,由于是连乘，不方便计算，求其对数化简，不改变取得最大值的$\mathbf{w}$的值：$$\log L(\mathbf{w})=\sum _{i=1}^n\log P(y_i|{\mathbf{x}}_i;\mathbf{w})$$
$$\log L(\mathbf{w})=\sum _{i=1}^n{y}_i\log P(y_i=1|{\mathbf{x}}_i;\mathbf{w})+(1-y_i)\log (1-P(y_i=1|{\mathbf{x}}_i;\mathbf{w}))$$
$$\log L(\mathbf{w})=\sum _{i=1}^n{y}_i\log \frac{P(y_i=1|{\mathbf{x}}_i;\mathbf{w})}{1-P(y_i=1|{\mathbf{x}}_i;\mathbf{w})}+\log (1-P(y_i=1|{\mathbf{x}}_i;\mathbf{w}))$$
$$\log L(\mathbf{w})=\sum _{i=1}^n{y}_i{\mathbf{x}}_i\mathbf{w}-\log (1+e^{{\mathbf{x}}_i\mathbf{w}})$$
6)对$\mathbf{w}$求偏导为：
$$\frac{\partial \log L(\mathbf{w})}{\partial \mathbf{w}}=\sum _{i=1}^n{y}_i{\mathbf{x}}_i-\frac{e^{{\mathbf{x}}_i\mathbf{w}}}{1+e^{{\mathbf{x}}_i\mathbf{w}}}{\mathbf{x}}_i$$
$$\frac{\partial \log L(\mathbf{w})}{\partial \mathbf{w}}=\sum _{i=1}^n(y_i-\frac{e^{{\mathbf{x}}_i\mathbf{w}}}{1+e^{{\mathbf{x}}_i\mathbf{w}}}){\mathbf{x}}_i$$
7)由于无法通过导数为0来得到极值，故使用梯度下降法：
$${\mathbf{w}}^{t+1}={\mathbf{w}}^t-\alpha \frac{\partial \log L(\mathbf{w})}{\partial \mathbf{w}}$$不断更新，直到导数为0或接近0.
特点：
1）使用点到超平面的距离：$\mathbf{x}\mathbf{w}$；
2）使用了sigmoid函数，将距离映射成概率；
3）将$\mathbf{w}$写成参数；
4）将$y_i=1$和$y_i=0$统一成一个表达式；
5）每个对象都考虑，使用连乘；
6）取$\log$简化优化目标；
7）使用最大似然估计试图直接求出$\mathbf{w}$；
8）求导为0计算最小值失败时，采用了梯度下降法.

第四天

第五天