魔鬼训练1

魔鬼训练1

作业

day1

1. 描述你在学习、使用数学表达式时的困难, 可举例说明.
   答案：主要遇到的问题:a.数学表达式比较多，如果不是经常使用的话很容易就会忘记，例如数学中的希腊字母，不仅难写，还经常读错；b.很多的数学的表达有相似之处容易搞混，例如集合 A → B mathbf{A} to mathbf{B} A→B 和 函数 A ↦ B mathbf{A} mapsto mathbf{B} A↦B 这两个的箭头符号就容易搞混.
2. 令 A = { 3 , 5 } mathbf{A} = {3, 5} A={3,5}, 写出 2 A 2^{mathbf{A}} 2A.
   答案： { ∅ , { 3 } , { 5 } , { 3 , 5 } } {emptyset,{3},{5},{3,5}} {∅,{3},{5},{3,5}}.
3. 展开 2 ∅ 2^{emptyset} 2∅.
   答案： { ∅ } {emptyset} {∅}.
4. 令 A = { 5 , 6 , 7 , 8 , 9 } mathbf{A} = {5, 6, 7, 8, 9} A={5,6,7,8,9}, 写出 A mathbf{A} A 的其它两种表示法. 答案：枚举法 [ 5..9 ] [5..9] [5..9] ,谓词法 { x ∣ x ∈ N , 5 ≤ x ≤ 9 } {x|xin N,5leq x leq9} {x∣x∈N,5≤x≤9}.
5. 自己出数据, 做一个 3 × 2 3 × 2 3×2与 2 × 4 2 × 4 2×4 的矩阵乘法.
   答案： [ 1 1 2 2 3 3 ] × [ 1 1 1 1 2 2 2 2 ] = [ 3 3 3 3 6 6 6 6 9 9 9 9 ] left[begin{array}{ll} 1 & 1 \ 2 & 2 \ 3 & 3 end{array}right] timesleft[begin{array}{lll} 1 & 1 & 1 & 1 \ 2 & 2 & 2 & 2 end{array}right]=left[begin{array}{ccc} 3 & 3 & 3 & 3 \ 6 & 6 & 6 & 6 \ 9 & 9 & 9& 9 end{array}right] ⎣⎡​123​123​⎦⎤​×[12​12​12​12​]=⎣⎡​369​369​369​369​⎦⎤​

day2

1. 令 A = { 1 , 2 , 5 , 8 , 9 } mathbf{A} = {1, 2, 5, 8, 9} A={1,2,5,8,9}, 写出 A mathbf{A} A 上的 “模 2 同余”关系及相应的划分.
   答案： R = { ( 1 , 1 ) , ( 1 , 5 ) , ( 1 , 9 ) , ( 2 , 8 ) , ( 2 , 2 ) , ( 8 , 2 ) , ( 5 , 5 ) , ( 5 , 9 ) , ( 8 , 8 ) , ( 9 , 1 ) , ( 9 , 5 ) , ( 9 , 9 ) } mathbf{R}={(1,1),(1,5),(1,9),(2,8),(2,2),(8,2),(5,5),(5,9),(8,8),(9,1),(9,5),(9,9)} R={(1,1),(1,5),(1,9),(2,8),(2,2),(8,2),(5,5),(5,9),(8,8),(9,1),(9,5),(9,9)}; P = { { 1 , 5 , 9 } , { 2 , 8 } } mathcal{P}={{1,5,9},{2,8}} P={{1,5,9},{2,8}}

2. A = { 1 , 2 , 5 , 8 , 9 } mathbf{A} = {1, 2, 5, 8,9} A={1,2,5,8,9},自己给定两个关系 R 1 mathbf{R}_1 R1​和 R 2 mathbf{R}_2 R2​,并计算 R 1 R 2 mathbf{R}_1mathbf{R}_2 R1​R2​, R 1 + mathbf{R}_1^+ R1+​, R 1 ∗ mathbf{R}_1^* R1∗​

   答案：定义 R 1 = { ( x , y ) ∈ A 2 ∣ x + y < 8 } mathbf{R}_1={(x,y)in mathbf{A}^2|x+y<8} R1​={(x,y)∈A2∣x+y<8}; R 2 = { ( x , y ) ∈ A 2 ∣ x 2 < y } mathbf{R}_2={(x,y)in mathbf{A}^2|x^2<y} R2​={(x,y)∈A2∣x2<y}
   R 1 = { ( 1 , 1 ) , ( 2 , 2 ) , ( 1 , 2 ) , ( 2 , 1 ) , ( 1 , 5 ) , ( 5 , 1 ) , ( 2 , 5 ) , ( 5 , 2 ) } mathbf{R}_1={(1,1),(2,2),(1,2),(2,1),(1,5),(5,1),(2,5),(5,2)} R1​={(1,1),(2,2),(1,2),(2,1),(1,5),(5,1),(2,5),(5,2)}
   R 2 = { ( 1 , 2 ) , ( 1 , 5 ) , ( 1 , 8 ) , ( 1 , 9 ) , ( 2 , 5 ) , ( 2 , 8 ) , ( 2 , 9 ) } mathbf{R}_2={(1,2),(1,5),(1,8),(1,9),(2,5),(2,8),(2,9)} R2​={(1,2),(1,5),(1,8),(1,9),(2,5),(2,8),(2,9)}
   R 2 ∘ R 1 = { ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 1 ) , ( 2 , 2 ) } mathbf{R}_2circmathbf{R}_1={(1,1),(1,2),(1,5),(2,1),(2,2)} R2​∘R1​={(1,1),(1,2),(1,5),(2,1),(2,2)}
   R 1 2 = { ( 1 , 1 ) , ( 1 , 5 ) , ( 2 , 2 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 2 ) , ( 5 , 5 ) , ( 2 , 1 ) , ( 5 , 1 ) } mathbf{R}_1^2={(1,1),(1,5),(2,2),(2,5),(1,2),(5,2),(5,5),(2,1),(5,1)} R12​={(1,1),(1,5),(2,2),(2,5),(1,2),(5,2),(5,5),(2,1),(5,1)}
   R 1 3 = R 1 2 R 1 = { ( 1 , 2 ) , ( 1 , 1 ) , ( 1 , 5 ) , ( 2 , 2 ) , ( 2 , 1 ) , ( 2 , 5 ) , ( 5 , 1 ) , ( 5 , 5 ) , ( 5 , 2 ) } mathbf{R}_1^3=mathbf{R}_1^2mathbf{R}_1={(1,2),(1,1),(1,5),(2,2),(2,1),(2,5),(5,1),(5,5),(5,2)} R13​=R12​R1​={(1,2),(1,1),(1,5),(2,2),(2,1),(2,5),(5,1),(5,5),(5,2)}
   R 1 4 = R 1 3 R 1 = { ( 1 , 1 ) , ( 1 , 5 ) , ( 1 , 2 ) , ( 2 , 1 ) , ( 2 , 5 ) , ( 2 , 2 ) , ( 5 , 2 ) , ( 5 , 5 ) , ( 5 , 1 ) ) } mathbf{R}_1^4=mathbf{R}_1^3mathbf{R}_1={(1,1),(1,5),(1,2),(2,1),(2,5),(2,2),(5,2),(5,5),(5,1))} R14​=R13​R1​={(1,1),(1,5),(1,2),(2,1),(2,5),(2,2),(5,2),(5,5),(5,1))}
   R 1 5 = R 1 4 R 1 = { ( 1 , 2 ) , ( 1 , 5 ) , ( 1 , 1 ) , ( 2 , 2 ) , ( 2 , 5 ) , ( 2 , 1 ) , ( 5 , 1 ) , ( 5 , 5 ) , ( 5 , 2 ) } mathbf{R}_1^5=mathbf{R}_1^4mathbf{R}_1={(1,2),(1,5),(1,1),(2,2),(2,5),(2,1),(5,1),(5,5),(5,2)} R15​=R14​R1​={(1,2),(1,5),(1,1),(2,2),(2,5),(2,1),(5,1),(5,5),(5,2)}
   R + = R 1 ∪ R 1 2 ∪ R 1 3 ∪ R 1 4 ∪ R 1 5 = { ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 5 ) , ( 5 , 1 ) , ( 5 , 2 ) , ( 5 , 5 ) } mathbf{R}^+=mathbf{R}_1cupmathbf{R}_1^2cupmathbf{R}_1^3cupmathbf{R}_1^4cupmathbf{R}_1^5={(1,1),(1,2),(1,5),(2,1),(2,2),(2,5),(5,1),(5,2),(5,5)} R+=R1​∪R12​∪R13​∪R14​∪R15​={(1,1),(1,2),(1,5),(2,1),(2,2),(2,5),(5,1),(5,2),(5,5)}
   R ∗ = R 1 + ∪ R 0 = { ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 5 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 2 , 5 ) , ( 5 , 1 ) , ( 5 , 2 ) , ( 5 , 5 ) , ( 8 , 8 ) , ( 9 , 9 ) } mathbf{R}^*=mathbf{R}_1^+cup mathbf{R}^0={(1,1),(1,2),(1,5),(2,1),(2,2),(2,5),(5,1),(5,2),(5,5),(8,8),(9,9)} R∗=R1+​∪R0={(1,1),(1,2),(1,5),(2,1),(2,2),(2,5),(5,1),(5,2),(5,5),(8,8),(9,9)}

3. 查阅粗糙集上下近似的定义并大致描述.

   答案： 粗糙集的下近似就是由相识关系确定的属于粗糙集的所有元素的最大集合
   粗糙集的上近似就是由所有可能属于粗糙集的所有元素的最小集合

4. 举例说明你对函数的认识.

   答案：函数 有定义域与值域, 且对于定义域的每个值, 在值域中有且仅有一个值与其对应. 函数就是在定义域和值域上定义了某种关系，而这种关系也称之为映射，例如函数 y = x y=x y=x,定义了两个数相等的关系，每一个 x x x都对应有且仅有一个 y y y,其值域为 { y ∣ y ∈ R } {y|yin mathbb{R}} {y∣y∈R},定义域为 { x ∣ x ∈ R } {x|xin mathbb{R}} {x∣x∈R}

5. 自己给定一个矩阵并计算其各种范数.
   答案：定义矩阵
   X = [ 0 4 3 0 ] mathbf{X}=left[begin{array}{ll} 0 & 4\ 3 & 0 end{array}right] X=[03​40​]
   l 0 l_0 l0​范数 ∥ m a t h b f X ∥ 0 = 2 |mathbf{X}|_0=2 ∥mathbfX∥0​=2; l 1 l_1 l1​范数 ∥ X ∥ 1 = 7 |mathbf{X}|_1=7 ∥X∥1​=7; l 2 l_2 l2​范数 ∥ X ∥ 2 = 5 |mathbf{X}|_2=5 ∥X∥2​=5; l ∞ l_infty l∞​范数 ∥ X ∥ ∞ = 4 |mathbf{X}|_infty=4 ∥X∥∞​=4

6. 解释 推荐系统: 问题、算法与研究思路2.1中的优化目标
   min ⁡ ∑ ( i , j ) ∈ Ω ( f ( x i , t j ) − r i j ) 2 minsum_{(i, j) in Omega} (f(mathbf{x}_i, mathbf{t}_j) - r_{ij})^2 min(i,j)∈Ω∑​(f(xi​,tj​)−rij​)2 各符号及其含义
   答案： min ⁡ min min是表示优化目标是取最小值， ∑ sum ∑符号是求和， Ω Omega Ω表示集合， ( i , j ) ∈ Ω (i,j)in Omega (i,j)∈Ω表示求和的每一项的 i , j i,j i,j都是集合 Ω Omega Ω里的元素， f ( x i , t j ) f(mathbf{x}_i,mathbf{t}_j) f(xi​,tj​)是需要求得的预测函数，输入 x i mathbf{x}_i xi​是一个用户的属性向量， t j mathbf{t}_j tj​表示的是一个商品的属性向量， r i j r_{ij} rij​是用户对商品的满意程度。通过不断优化求得 f f f与 r i j r_{ij} rij​差的平方和最小值来确定预测函数 f f f的参数。

day3

1. 将向量下标为偶数的分量 ( x 2 , x 4 , … ) (x_2, x_4, …) (x2​,x4​,…) 累加, 写出相应表达式.
   答案： ∑ i m o d 2 = 0 x i sum_{imod2=0}x_i imod2=0∑​xi​

for(int i=1;i<=count;i++){if(i%2==0)sum += i;}

1. 各出一道累加、累乘、积分表达式的习题, 并给出标准答案.
   答案：累加 表示 1 + 2 + ⋯ + 10 数学表达式 ∑ i = 1 10 i = 55 sum_{i=1}^{10}i=55 ∑i=110​i=55
   累乘 表示 1 × 2 × ⋯ × 5 1times 2 times dots times5 1×2×⋯×5 数学表达式 ∏ i = 1 5 i = 120 prod_{i=1}^{5}i=120 ∏i=15​i=120
   积分 ∫ 0 1 x d x = 0.5 int_{0}^1xmathrm{d}x=0.5 ∫01​xdx=0.5
   你使用过三重累加吗? 描述一下其应用.
   三重累加在一定条件下可以转化为三重积分，三重积分可以看作是几何体的测量
2. 给一个常用的定积分, 将手算结果与程序结果对比.
   答案： ∫ 0 1 x 2 d x int_0^1x^2mathrm{d}x ∫01​x2dx
   手算结果 1 3 frac{1}{3} 31​
   程序运算结果

 public static void main(String[] args) {// write your code hereint count=1;double delta =0.01;double result=0;for(double i=0;i<=count;i+=delta){result += i*i*delta;}System.out.println(result);}

0.3293410000000002

3. 自己写一个小例子 ( n = 3 , m = 1 ) (n = 3, m = 1) (n=3,m=1) 来验证最小二乘法.

设一元线性回归方程 y ^ = a x + b hat{y}=ax+b y^​=ax+b,数据点样本为 ( x i , y i ) (x_i,y_i) (xi​,yi​),用最小二乘法求解方程
arg min ⁡ a , b ∑ i = 1 n ( y i − y ^ i ) 2 = arg min ⁡ a , b ∑ i = 1 n ( y i − a x i − b ) 2 argmin_{a,b}sum_{i=1}^{n}(y_i-hat{y}_i)^2=argmin_{a,b}sum_{i=1}^{n}(y_i-ax_i-b)^2 a,bargmin​∑i=1n​(yi​−y^​i​)2=a,bargmin​∑i=1n​(yi​−axi​−b)2
令 J ( a , b ) = arg min ⁡ a , b ∑ i = 1 n ( y i − a x i − b ) 2 J(a,b)=argmin_{a,b}sum_{i=1}^{n}(y_i-ax_i-b)^2 J(a,b)=a,bargmin​∑i=1n​(yi​−axi​−b)2，分别对 a , b a,b a,b求导
∇ a J ( a , b ) = − 2 arg min ⁡ a , b ∑ i = 1 n ( y i − a x i − b ) x i = − 2 ∑ i = 1 n x i y i + 2 a ∑ i = 1 n x i 2 + 2 b ∑ i = 1 n x i nabla_aJ(a,b)=-2argmin_{a,b}sum_{i=1}^{n}(y_i-ax_i-b)x_i \ qquad qquad ,,=-2sum_{i=1}^nx_iy_i+2asum_{i=1}^nx_i^2+2bsum_{i=1}^nx_i ∇a​J(a,b)=−2a,bargmin​∑i=1n​(yi​−axi​−b)xi​=−2∑i=1n​xi​yi​+2a∑i=1n​xi2​+2b∑i=1n​xi​
∇ a J ( a , b ) = − 2 arg min ⁡ a , b ∑ i = 1 n ( y i − a x i − b ) = − 2 ∑ i = 1 n y i + 2 a ∑ i = 1 n x i + 2 n b nabla_aJ(a,b)=-2argmin_{a,b}sum_{i=1}^{n}(y_i-ax_i-b)\ qquad qquad ,,=-2sum_{i=1}^ny_i+2asum_{i=1}^nx_i+2nb ∇a​J(a,b)=−2a,bargmin​∑i=1n​(yi​−axi​−b)=−2∑i=1n​yi​+2a∑i=1n​xi​+2nb
令 ∇ a J ( a , b ) = 0 , ∇ b J ( a , b ) = 0 nabla_aJ(a,b)=0,nabla_bJ(a,b)=0 ∇a​J(a,b)=0,∇b​J(a,b)=0,并带入数据求解得到 a = 5 , b = − 5 3 a=5,b=-frac{5}{3} a=5,b=−35​,所以 y ^ = 5 x − 5 3 hat{y}=5x-frac{5}{3} y^​=5x−35​

4. 自己推导一遍数学表达式: 从恐惧到单挑 (10. Logistic 回归), 并描述这个方法的特点 (不少于 5 条).

log ⁡ L ( w ) = ∑ i = 1 n log ⁡ P ( y i ∣ x i ; w ) = ∑ i = 1 n y i log ⁡ P ( y i = 1 ∣ x i ; w ) + ( 1 − y i ) log ⁡ ( 1 − P ( y i = 1 ∣ x i ; w ) ) = ∑ i = 1 n y i log ⁡ P ( y i = 1 ∣ x i ; w ) 1 − P ( y i = 1 ∣ x i ; w ) + log ⁡ ( 1 − P ( y i = 1 ∣ x i ; w ) ) = ∑ i = 1 n y i x i w − log ⁡ ( 1 + e x i w ) begin{array}{l}log L(mathbf{w}) = sum_{i = 1}^n log P(y_i vert mathbf{x}_i; mathbf{w}) \ = sum_{i = 1}^n y_i log P(y_i = 1 vert mathbf{x}_i; mathbf{w}) + (1 - y_i) log(1 - P(y_i = 1 vert mathbf{x}_i; mathbf{w})) \ = sum_{i = 1}^n y_i log frac{P(y_i = 1 vert mathbf{x}_i; mathbf{w})}{1 - P(y_i = 1 vert mathbf{x}_i; mathbf{w})} + log (1 - P(y_i = 1 vert mathbf{x}_i; mathbf{w}))\ = sum_{i = 1}^n y_i mathbf{x}_i mathbf{w} -log(1+e^{mathbf{x}_imathbf{w}})end{array} logL(w)=∑i=1n​logP(yi​∣xi​;w)=∑i=1n​yi​logP(yi​=1∣xi​;w)+(1−yi​)log(1−P(yi​=1∣xi​;w))=∑i=1n​yi​log1−P(yi​=1∣xi​;w)P(yi​=1∣xi​;w)​+log(1−P(yi​=1∣xi​;w))=∑i=1n​yi​xi​w−log(1+exi​w)​
对 w 求 偏 导 mathbf{w}求偏导 w求偏导
∂ log ⁡ L ( w ) ∂ w = ∑ i = 1 n y i x i − e x i w 1 + e x i w x i = ∑ i = 1 n ( y i − e x i w 1 + e x i w ) x i begin{array}{l} 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= sum_{i = 1}^n left(y_i - frac{e^{mathbf{x}_i mathbf{w}}}{1 + e^{mathbf{x}_i mathbf{w}}}right) mathbf{x}_iend{array} ∂w∂logL(w)​=∑i=1n​yi​xi​−1+exi​wexi​w​xi​=∑i=1n​(yi​−1+exi​wexi​w​)xi​​
令该偏导为 0, 无法获得解析式, 因此用梯度下降.
w t + 1 = w − α ∂ log ⁡ L ( w ) ∂ w mathbf{w}^{t+1}=mathbf{w}-alphafrac{partiallogmathbf{L}(mathbf{w})}{partialmathbf{w}} wt+1=w−α∂w∂logL(w)​
方法的特点
1.线性向量相乘计算所有点到超平面的距离
2.使用sigmoid函数将距离映射为0到1的概率，降低了计算的难度
3. w mathbf{w} w是所求的未知量，将其作为参数带入 P P P，用 P P P反求参数
4.用 l o g log log把概率相乘转化为相加，降低了计算的难度
5.利用求导和梯度下降来无限逼近 w mathbf{w} w