ICESat-2 ATL07 数据说明

2023-08-03

1 数据描述

1.1 参数

沿轨道的海冰和海面高度。其中海冰高度是相对于时变海面（包括海洋潮汐、逆气压计效应和其他因素）而言的。

1.2 文件信息

1.2.1 格式

HDF格式。

1.2.2 ICESat-2描述

每个地面轨道根据产生它的激光点号进行编号，最左边为地面轨道1L（GT1L），最右边为地面轨道3R（GT3R）。每对位点中的左右位点在跨轨道方向相距约90米，在沿轨道方向相距约2.5公里。

Matlab Cody——CUP Challenge 题解

2023-07-29

1. Problem 1974. Length of a short side

1
2
3

function a = calculate_short_side(b, c)
  a = sqrt(c.^2-b.^2)
end

2. Problem 2024. Triangle sequence

function area = triangle_sequence(n)
  a = [0 1;1 1]^n;
  x = [9;16];
  res = a*x;
  area = res(2);
end

3. Problem 2022. Find a Pythagorean triple

function flag = isTherePythagoreanTriple(a, b, c, d)
tol = 1e-5;
  if abs(a^2+b^2 - c^2) <= tol
      flag = true;
  elseif abs(a^2+b^2 - d^2) <= tol
      flag = true;
  elseif abs(a^2+c^2 - d^2) <= tol
      flag = true;
  elseif abs(b^2+c^2 - d^2) <= tol
      flag = true;
  else
      flag = false;
  end
end

4. Problem 2023. Is this triangle right-angled?

function flag = isRightAngled(a,b,c)
  temp = [a,b,c];
  temp = sort(temp,2,'ascend');
  tol = 1e-5;
  if abs(temp(1)^2+temp(2)^2-temp(3)^2)<=tol
    flag = true;
  else
    flag = false;
end

5. Problem 2021. Is this triangle right-angled?

function flag = isRightAngled(a, b, c)
  tol = 1e-5;
  if abs(a^2+b^2-c^2)<tol
      flag = true;
  else
      flag = false;
  end
end

6. Problem 2020. Area of an Isoceles Triangle

function A = isocelesArea(x,y)
  w = y/2;
  h = sqrt(x^2-w^2);
  A = w*h;
end

7. Problem 2018. Side of a rhombus

1
2
3

function y = rhombus_side(x)
  y = sqrt(x.^2 + (x+1).^2)/2;
end

Matlab Cody——Basics Rounding 题解

2023-07-22

1. Problem 42641. MATLAB Basic: rounding

错误写法：

1
2
3

function y = round_zero(x)
  y = round(x,TieBreaker="tozero");
end

正确写法：

1
2
3

function y = round_zero(x)
  y = fix(x);
end

2. Problem 42642. MATLAB Basic: rounding II

1
2
3

function y = round_x(x)
  y = round(x);
end

3. Problem 42643. MATLAB Basic: rounding III

1
2
3

function y = round_x(x)
  y = floor(x);
end

4. Problem 42644. MATLAB Basic: rounding IV

1
2
3

function y = round_x(x)
  y = ceil(x);
end

5. Problem 2559. Check that number is whole number

1
2
3

function y = your_fcn_name(x)
  y = (x==round(x));
end

6. Problem 2866. Matlab Basics - Rounding II

1
2
3

function y = round_3_d_p(x)
  y = round(x,3);
end

7. Problem 2867. Matlab Basics - Rounding III

1
2
3

function y = round_ten_thou(x)
  y = round(x,-4);
end

8. Problem 2120. Rounding off numbers to n decimals

1
2
3

function y = myround(x,n)
  y = round(x,n);
end

9. Problem 43278. Make roundn function

1
2
3

function y = myroundn(x,n)
   y = round(x,n-1);
end

10. Problem 713. Find the maximum number of decimal places in a set of numbers

题目意思：给定一个向量或值矩阵，计算输入中的最大小数位数。尾随零不算有效。没有有效数字将导致答案为 0。
题解：没有找到一个优雅的写法，所有先放空。

Matlab Cody——Basics on Vectors题解

2023-07-22

0. Matlab Cody 简介

Matlab Cody是一个类似Leetcode的oj网站，网址：https://ww2.mathworks.cn/matlabcentral/cody

1. Problem 3. Find the sum of all the numbers of the input vector

1
2
3

function y = vecsum(x)
   y = sum(x,'all')
end

2. Problem 6. Select every other element of a vector

1
2
3

function y = everyOther(x)
  y = x(1:2:end);
end

3. Problem 247. Arrange Vector in descending order

1
2
3

function y = desSort(x)
  y = sort(x,'descend');
end

4. Problem 135. Inner product of two vectors

1
2
3

function z = your_fcn_name(x,y)
  z = dot(x,y);
end

5. Problem 624. Get the length of a given vector

1
2
3

function y = VectorLength(x)
  y = length(x);
end

6. Problem 1107. Find max

1
2
3

function y = your_fcn_name(x)
  y = max(x,[],'all');
end

7. Problem 605. Whether the input is vector?

function y = checkvector(x)
  if isvector(x)
      y = 1;
  else
      y = 0;
  end
end

8. Problem 2631. Flip the vector from right to left

题目要求不能直接使用函数，所以自己写

1
2
3

function y = flip_vector(x)
  y = x(end:-1:1);
end

9. Problem 3076. Create a vector

1
2
3

function y = zeroToNby2(n)
  y = 0:2:n;
end

10. Problem 1024. Doubling elements in a vector

function B = your_fcn_name(A)
  B = zeros(1,2*length(A));
  B(1:2:end-1) = A;
  B(2:2:end) = A;
end

11. Problem 42651. Vector creation

1
2
3

function y = vector(x)
  y = 1:x;
end

辐射基础1

2023-05-21

林轩田机器学习每章要点

2023-05-14

0. 符号假设

1. When Can Machine Learn?

1.1 1.2 Learning to Answer Yes-No

本节主要介绍了感知机算法，它在一定条件下可以使得 $\textbf{E}_{in} \approx 0$ (在数据集上的误差近似为0)。

感知机学习算法 $\mathcal{A}$ 通过线性可分的数据 $\mathcal{D}$ 以及感知机 $\mathcal{H}$ 获得假设 $g$

感知机的假设空间：定义在 $\mathbb{R}^d$ 上的一条直线或超平面
感知机算法可以不断纠正错误并改进
感知机的分类正确性保证：数据是线性可分的
无法分类的数据：存储效果最好的直线

1.3 Types of Learning

本节主要介绍机器学习的分类

按输出空间 $\mathcal{Y}$ 分类：分类、回归、结构化学习
按数据标签 $y_n$ 分类：监督学习、半监督学习、无监督学习、强化学习
按不同的学习方式分类：批量学习、在线学习、主动学习
按输入空间 $\mathcal{X}$ 分类：具体意义的数据、原始数据、抽象数据

1.4 Feasibility of Learning

本节主要介绍机器学习的可能性

NFL定理：面对所有的问题，没有一种算法能说比另一种算法更好
验证一个固定假设 $h$ 的 $E_{in}$ 和 $E_{out}$ 是否PAC
- 机器能够学习的必要条件：样本满足独立同分布假设 (每次抽样之间相互独立，样本服从同一分布)
- $E_{in}$ 为抽样样本（数据集）内所有数据中 $h(\vec{x}) = f(\vec{x})$ 的概率，
  $E_{out}$ 为抽样样本外所有数据中 $h(\vec{x}) = f(\vec{x})$ 的概率
  
  ($E_{in}(h) = \frac{1}{N} \sum\limits_{n=1}^{N} \mathbb{I}[h(\vec{x}) \neq y_n]$、
  $E_{out} = \mathop{\varepsilon}\limits_{\vec{x} \sim{P}} \mathbb{I}[h(\vec{x}) \neq f(\vec{x})]$)
- Hoeffding 不等式：$P[\lvert E_{in} - E_{out} \rvert > \epsilon] \leq 2exp(-2 \epsilon^2 N)$
  
  (说明了只要样本数 $N$ 够大，$E_{in}$ 和 $E_{out}$ 相差的很大概率会很小，也就可以用 $E_{in}$ 来估计 $E_{out}$)
- 上述 Hoeffding 不等式说明了 $E_{in}$ 和 $E_{out}$ 是 PAC(概率近似相等) 的
在 $E_{in}(h)$ 足够小且 $\lvert \mathcal{H} \rvert$ 有限的情况下，学习有可能能实现了
- 坏数据集 (BAD $\mathcal{D}$)：使得假设 $h$ 的 $E_{in}$ 和 $E_{out}$ 相差很大的数据集
- $P_{\mathcal{D}}(BAD \; \mathcal{D}) \leq P(BAD \; \mathcal{D} \; for \; h_1) + … + P(BAD \; \mathcal{D} \; for \; h_M)$
  
  $P_{\mathcal{D}}(BAD \; \mathcal{D}) \leq 2exp(-2 \epsilon^2 N) + … + 2exp(-2 \epsilon^2 N)$
  
  $P_{\mathcal{D}}(BAD \; \mathcal{D}) \leq 2Mexp(-2 \epsilon^2 N)$
  
  也就是说只要 $N$ 足够大，$\lvert \mathcal{H} \rvert$ 有限的情况下。
  不管使用什么算法 $\mathcal{A}$ 都能够使得 $E_{in}$ 和 $E_{out}$ PAC，
  
  如果 $\mathcal{A}$ 可以找到 $g$ 使 $E_{in}(g) \approx 0$ 那么PAC可以保证 $E_{out}(g) \approx 0$

2. Why Can Machines Learn?

2.1 Training VS Testing

本节主要介绍假设数量 $M = \infty$ 时，机器学习是否有可能性

$M$ 过小 $E_{in}(g) \approx 0$ 难以实现(选择过少)，$M$ 过大出现坏样本的概率又显著增加，
导致 $E_{in}(g)$ 和 $E_{out}(g)$ 无法PAC
按照对数据集中样本点的分类结果可以将无穷种假设分成 $effective(N)$ 种，
如果 $effective(N) << 2^N$ ，机器学习是有可能的
成长函数 $m_{\mathcal{H}}(N)$ 是含N个数据点的数据集最多的假设种类数
($m_{\mathcal{H}}(N) = \mathop{max}\limits_{\vec{x_1},…,\vec{x_N} \in \mathcal{X}} \lvert \mathcal{H}(x_1,…,x_N) \rvert$)
$m_{\mathcal{H}}(N) = O(N^{k-1})$ ($k$ 是break point，也就是 $k$ 个样本点类别的 $2^k$ 种情况
都能被 $\mathcal{H}$ 中其中一个假设全部正确分类)

2.2 Theory of Generalization

$N > k$ 时，$m_{\mathcal{H}}(N)$ 会比 $2^N$ 小的多
Bounding Function $B(N,k)$ 是 $m_{\mathcal{H}}(N)$ 的上限，以下是它的一些性质:
- $k = 1$ 时，$B(N,1) = 1$
- $N < k$ 时，$B(N,k) = 2^N$ (相当于没有限制)
- $N = k$ 时，$B(N,k) = 2^k - 1$ (刚出现不能被覆盖的分类情况)
通过递推得到 $B(N,k)$ 其他情况下的一些性质:
- 把 $N$ 个样本可以被覆盖的二分情况再分为两类：第一类每两种情况的 $x_1$ 到 $x_{k-1}$ 的类别完全相同，$x_k$ 的类别不同且成对，其他为第二类
- 第一类情况个数记为 $\alpha$，第二类为 $\beta$，存在以下关系：$B(N,k) = 2\alpha + \beta$、
  $\alpha + \beta \leq B(N-1,k)$、$\alpha \leq B(N-1,k-1)$
- 因此可以得到 $B(N,k) = B(N-1,k) + B(N-1,k-1)$ (取等证明略)
- 因此 $B(N,k) = \sum\limits_{i=0}^{k-1} C_i^N$，最高次项为 $N^{k-1}$，所以成长函数 $m_{\mathcal{H}}(N)$ 是 $poly(N)$ 的
用成长函数 $m_{\mathcal{H}}(N)$ 替代 $M$ 证明 $E_{in}$ 和 $E_{out}$ 是PAC的
- 证明略
- VC bound：$P_{\mathcal{D}}(\lvert E_{in} - E_{out} \rvert > \epsilon) \leq 4m_{\mathcal{H}}(N)exp(-\frac{1}{8} \epsilon^2 N)$

2.3 The VC Dimension

本节介绍VC维的意义及其与泛化能力的关系

VC维的定义：使得 $m_{\mathcal{H}}(N) = 2^N$ 成立的最大N，记为 $d_{VC}$
- 机器学习的条件：1、$m_{\mathcal{H}}(N)$ 有间断点k；2、样本数N足够大(这两点保证 $E_{out}$ 和 $E_{in}$ PAC)；
  3、合适的算法 $\mathcal{A}$ (保证 $E_{in} \approx 0$)
- $d_{VC}$ 有限时，$E_{out}$ 和 $E_{in}$ 是PAC的
$d_{VC} = d+1$
- 先证明 $d_{VC} \geq d+1$，由于 $X\vec{w}_{d+1} = \vec{y}_{d+1}$ 可得 $\vec{w} = X^{-1}\vec{y}$
  (X有 $d+1$ 个维度和 $d+1$ 个样本).
  
  因此对每一种 $\vec{y}$，$\vec{w}$ 唯一确定. $\vec{w}$ 的所有情况也就可以覆盖 $\vec{y}$ 的所有情况
- 再证明 $d_{VC} \leq d+1$，也就是对 $d+2$ 个样本 $\vec{w}$ 的所有情况不可以覆盖 $\vec{y}$ 的所有情况
  
  由于 $\vec{x}_{d+2}$ (第 $d+2$ 个样本) 能被表示成前 $d+1$ 个样本的线性组合.
  
  也就是：$\vec{x}_{d+2} = a_1\vec{x}_{1} + … + a_{d+1}\vec{x}_{d+1}$
  
  因此存在 $\vec{w}$ 使得 $\vec{x}_{d+2}\vec{w} = a_1\vec{x}_{1}\vec{w} + … + a_{d+1}\vec{x}_{d+1}*\vec{w}>0$
  
  这种情况下 $\vec{x}_{d+2}$ 一定是正类. $\vec{w}$ 的所有情况不能覆盖 $\vec{y}$ 的所有情况
$d_{VC}$ 的物理意义：假设空间的自由度。所以 $M$ 和 $d_{VC}$ 是成正比的
$d_{VC}$ 和泛化能力、样本复杂度以及模型复杂度的关系
- $E_{out}(g) \leq E_{in}(g) + \sqrt{\dfrac{8}{N} \ln{\dfrac{4(2N)^{d_{VC}}}{\delta}}}$
- $\Omega(N,\mathcal{H},\delta) = \sqrt{\dfrac{8}{N} \ln{\dfrac{4(2N)^{d_{VC}}}{\delta}}}$ 称为模型复杂度的惩罚项
- 随着 $d_{VC}$ 增加，$E_{in}$ 下降，但是 $\Omega$ 上升。所以 $E_{out}$ 随 $d_{VC}$ 先下降后上升
- 样本复杂度：$d_{VC}$ 固定的情况下，$N$ 的合理取值(理论上 $N \approx 10000d_{VC}$ 实际上只需要 $N \approx 10d_{VC}$)

2.4 Noise and Error

本节主要说了在数据集有噪声的情况下，VC维依然是成立的，机器学习依然是可能的

样本由 $P(y|\vec{x})$ (也就是 $f(\vec{x}) + noise$ ) 产生
- 只要 $\vec{x} \stackrel{\text{i.i.d}}{\sim}{P(\vec{x})}$ 和 $y \stackrel{\text{i.i.d}}{\sim}{P(y)}$，VC维理论依然成立
误差的度量方式
- 误差度量的特点：1、只考虑样本外的未知数据，2、分别考虑每个数据点的误差(不一定满足，但本课程只考虑这个)
- 常用误差有：0-1误差和平均平方误差(MSE)，前者用于分类，后者用于回归
- 0-1误差下的 $f(\vec{x}) = \mathop{\arg\max}\limits_{y \in \mathcal{Y}} P(y|\vec{x})$，使得翻转噪声最小
- MSE下的 $f(\vec{x}) = \sum\limits_{y \in \mathcal{Y}} yP(y|\vec{x})$，使得高斯噪声最小
错误衡量设计的两种方式：有意义的或者易于设计算法
通过”虚拟复制”某类错误对应的标签的样本w次的方法，可以计算 $E_{in}^w$ (w为某类错误的权重)

3. How Can Machines Learn?

3.1 Linear Regression

线性回归使用超平面 $h(\vec{x}) = \vec{w}^T\vec{x}$ 估计真实值
线性回归存在用伪逆表示的解析解 $\vec{w}_{LIN} = X^{\dagger}\vec{y}$
- MSE误差最小等价于：$\min\limits_{\vec{w}} E_{in}(\vec{w}) = \frac{1}{N} \Vert X\vec{w} - \vec{y} \Vert^2$
- 因为MSE损失函数为凸函数，所以 $\nabla E_{in}(\vec{w}) = 0$ 处即为最小值点
线性回归相当于使 $\vec{y}$ 投影到由 $X$ 的特征张成的平面内，其中 $y - \hat{y}$ 是误差
- $trace(I - H) = N-(d+1)$ 表示$\vec{y}$ 投影到由 $X$ 的特征张成的平面内损失的自由度
- 如果有真实值来自于$f(X) \in span{X}$，那么对 noise 进行投影即 $I-H$ 操作可得：
  
  $\overline{E_{in}} = \frac{1}{N}\Vert y - \hat{y} \Vert^2 = \frac{1}{N}\Vert (I-H)\textbf{noise} \Vert^2 =
  \textbf{noise} (1-\frac{d+1}{N})$
- $\overline{E_{out}} = \textbf{noise} (1+\frac{d+1}{N})$，随着 $N$ 逐渐增大 $\overline{E_{in}} \approx \overline{E_{out}}$
用回归器进行分类的代价是更松的上界，因为 $err_{0/1} \leq err_{sqr}$，所以 $E_{out} \leq 分类E_{in} + 复杂度 \leq 回归E_{in} + 复杂度$

3.2 Logistic Regression

Logistic 回归的目标函数是 $P(+1|x)$，其假设为 $h(x) = \theta(\vec{w}^T x)$(其中 $\theta = \dfrac{1}{1+e^{-s}}$)
Logistic 回归的损失函数是交叉熵函数(似然函数的负对数 $L(\vec{w}) = \frac{1}{N}\sum\limits_{n=1}^{N} -\ln \theta(y_n \vec{w}^T \vec{x}_n)$)
Logistic 回归的损失函数是凸函数，因此其最小值在
$\nabla E_{in}(\vec{w}) = \frac{1}{N} \sum\limits_{n=1}^{N} \theta(-y_n \vec{w}^T \vec{x}_n) (-y_n \vec{x}_n) = 0$ 处取得
Logistic 回归可以用梯度下降法求得 $L(\vec{w})$ 最小值
- $\vec{w}$ 更新方式：$\vec{w}_{t+1} = \vec{w}_{t} + \eta \vec{v}$
- $\eta$ 很小的时候可以泰勒展开近似，$E_{in}(\vec{w}_{t+1}) \approx E_{in}(\vec{w}_{t} + \eta \vec{v}^T \nabla E_{in}(\vec{w}_t))$
- 当 $\vec{v}$ 与 $\nabla E_{in}(\vec{w}_t)$ 方向相反时(即 $\vec{v} = -\dfrac{\nabla E_{in}(\vec{w}_t)}{\Vert \nabla E_{in}(\vec{w}_t) \Vert}$)
  $E_{in}$ 下降最快
- 我们希望 $\eta$ 与 $\Vert \nabla E_{in}(\vec{w}_t) \Vert$ 正相关，因此更新的式子可以改为:
  $\vec{w}_{t+1} = \vec{w}_{t} - \eta \nabla E_{in}(\vec{w}_t)$

3.3 Linear Models for Classification

线性回归和Logistic 回归都可以解决线性分类问题
随机梯度下降(SGD)可以简化更新操作到 $\mathcal{O}(1)$ 复杂度
简化后的更新操作：$\vec{w}_{t+1} = \vec{w}_{t} - \eta \theta(-y_n \vec{w}_t^T \vec{x}_n) (-y_n \vec{x}_n)$
多分类问题
- OVA：对每一类和所有其他类别数据做二分类，分别计算 $P(k|\vec{x})$
  - 优点：高效，可以和所有类似Logistic 回归的算法结合
  - 缺点：K较大时容易类别不平衡
- OVO：对每一类和每种其他类别数据做二分类
  - 优点：可以和所有二分类算法结合
  - 缺点：时空复杂度高，预测速度慢

3.4 Nonlinear Transformation

可以用一非线性函数 $\Phi$ 将非线性函数映射到线性空间中，实现x域到z域特征转换
z域特征维度 $\tilde{d} = C_{Q+d}^{Q} = C_{Q+d}^{d} = \mathcal{O}(Q^d)$ 较大，
会导致模型泛化能力差，时空复杂度高
优先选择 $Q$ 较小的假设，如果 $E_{in}$ 太高在考虑复杂假设

4. How Can Machines Learn Better?

4.1 Hazard of Overfitting

过拟合：$E_{in}$ 变小但是 $E_{out}$ 变大的过程。以下是过拟合常见原因：
- VC Dimension太大
- 随机噪声或系统性噪声过强
- 训练样本数 $N$ 不够
避免过拟合的措施:
- 从简单的模型开始
- 数据清理(修正明显错误的label或者删除错误样本点)
- 数据增强(注意新增的数据可能和原来数据不是 $i.i.d.$ 的，尽量保证新数据内的样本是 $i.i.d.$ 的)
- 正则化
- 验证

4.2 Regularization

正则化约束条件：$\Vert \vec{w} \Vert^2 \leq C$，$H_n \subset H(C) \subset H_m$ ($n<m$)
最优解需要满足 $-\nabla E_{in}(w_{reg})$ 与 $w^Tw = C$ 的法向量平行，
即 $\nabla E_{in}(w_{reg}) + \frac{2\lambda}{N}w_{reg}=0$
- 求解 $w_{reg}$ 等价于最小化 $E_{aug} = E_{in} + \frac{\lambda}{N} w_{reg}^Tw_{reg}$
- 多项式变换除了可以用朴素的 $x^n$，也可以用勒让德多项式
$E_{aug}$ 可以看成 $E_{out}$ 的代理
- $E_{aug} = E_{in} + \frac{\lambda}{N} w^Tw$ 中的 $w^Tw$ 是单个假设的复杂度，记为 $\Omega(w)$。
  整个 $H$ 的复杂度为 $\Omega(H)$，$\Omega(w)$ 包含在 $\Omega(H)$ 中
- 整个 $H$ 的VC维是 $d_{VC} = \tilde{d} + 1$，引入正则化限定条件 $H(C)$ 后的VC维记为 $d_{EFF}(H,A)$.
  则有 $d_{EFF}(H,A) \leq d_{VC}$
正则化项选择方法
- 基于目标特性，比如目标具有对称性则考虑用 $\sum\mathbb{I}(q \% 2==0)w^2_q$ 作为正则化项
- 接近真实(曲线平滑、简单)，如L1正则化 $\sum \vert w_q \vert$
- 易于实现，如L2正则化 $\sum w^2_q$
- 噪音越大，$\lambda$ 也要越大

4.3 Validation

模型选择指的是在 $M$ 个假设空间 $H_m$ 对应 $M$ 种算法 $A_m$ 中选择最优假设空间 $H_{m^*}$

使得 $g_{m^} = A_{m^}(D)$，$E_{out}(g_{m^*})$ 最小

用验证集选择模型
- 用 $E_{in}$ 选择模型是危险的(因为即用 $D$ 训练模型又用它选择模型)
- 用 $E_{test}$ 选择模型是作弊且无法实现的(难以获得测试数据)
验证集模型选择原理：$E_{out}(g) \mathop{\approx}\limits_{small K} E_{out}(g^-) \mathop{\approx}\limits_{large K} E_{val}(g^-)$
- 验证集大小 $K$ 越大，$g^-$ 越不如 $g$，但是 $E_{val}$ 越接近 $E_{out}$ (学习曲线)
- 验证集大小 $K$ 越小，$g^-$ 越接近 $g$，但是 $E_{val}$ 越不如 $E_{out}$ (学习曲线)
留一法交叉验证(LOOCV) 的期望 $\mathop{\varepsilon}\limits_{D} E_{LOOCV}(H,A) = \overline{E_{out}}(N-1)$
是对 $\overline{E_{out}}$的近似无偏估计
- $E_{LOOCV} = \frac{1}{N} \sum\limits_{n=1}^{N} err(g_m^-(\vec{x}_n),y_n)$ ($K = 1$ 的特殊情况)
- LOOCV的缺点：计算量大、结果不稳定
V折交叉验证公式：$E_{CV} = \frac{1}{V} \sum\limits_{v=1}^{V} E_{val}^{(v)}(g_v^-)$

4.4 Three Learning Principles

奥卡姆剃刀原则：适合数据的最简单的模型是最合适的
抽样误差：数据要匹配测试环境
偷窥数据：容易造成过拟合。应当避免通过数据进行决策，并且对别人的研究成果保持警惕
power of three
- 机器学习相关的三个领域：数据挖掘、机器学习、统计
- 三个理论保证：霍夫丁不等式、多假设霍夫丁不等式、VC维
- 三种线性模型：感知机、线性回归、Logistic回归
- 三种重要的工具：特征转换、正则化、验证
- 三个锦囊妙计：奥卡姆剃刀、防止抽样误差、谨慎偷窥数据
- 机器学习未来方向：更多转换、更多正则化、更少标签

chap4 朴素贝叶斯模型简洁总结

2023-05-13

chap3 KNN模型简洁总结

2023-05-12

由于KNN是一种基于实例学习的算法，不需要训练过程。

只需要确定了数据集、距离度量、k值以及分类规则，某个样本的类别就能被唯一确定。

因此下文不介绍学习策略和学习算法。

1、KNN模型

输入空间：$\mathcal{X} \in \mathbb{R}^n$

输出空间：$\mathcal{y} \in \{c_1,c_2,…,c_K\}$

特征空间：不显式学习

2、距离度量

一般采用 $L_p$ 距离(闵可夫斯基距离，Minkowski distance).

$L_p$ 的表达式：$L_p(\vec{x_i},\vec{x_j}) = (\sum\limits_{l=1}^n \lvert x_i^{(l)} - x_j^{(l)} \rvert ^p)^{\frac{1}{p}}$ $\quad$ ($p \geq 1$)

$p = 2$ 时就是欧氏距离：$L_2(\vec{x_i},\vec{x_j}) = \sqrt{\sum\limits_{l=1}^n (x_i^{(l)} - x_j^{(l)})^2}$

$p = 1$ 时称为曼哈顿距离：$L_1(\vec{x_i},\vec{x_j}) = \sum\limits_{l=1}^n \lvert x_i^{(l)} - x_j^{(l)} \rvert$

$p = \infty$ 时，它是各个维度坐标距离的最大值：$L_{\infty} = \max\limits_{l} \lvert x_i^{(l)} - x_j^{(l)} \rvert$

3、k值选择

k值过小，模型容易受到噪声点影响导致过拟合；k值过大则容易欠拟合.

k值一般通过交叉验证选取。

4、分类决策规则

一般考虑让经验风险最小，也就是误分类率 $\frac{1}{K} \sum\limits_{\vec{x_i} \in N_K(\vec{x})} \mathbb{I}(y_i \neq c_k)$ 最小

也就是要让 $\frac{1}{K} \sum\limits_{\vec{x_i} \in N_K(\vec{x})}\mathbb{I}(y_i = c_j) = 1 - \frac{1}{K} \sum\limits_{\vec{x_i} \in N_K(\vec{x})} \mathbb{I}(y_i \neq c_k)$ 最大

当损失函数为0-1损失很熟时，多数表决规则分类函数为：$y = \mathop{\arg\max}\limits_{c_j} \sum\limits_{\vec{x_i} \in N_K(\vec{x})}\mathbb{I}(y_i = c_j)$

所以多数表决规则等价于经验风险最小

chap2 感知机模型简洁总结

2023-05-12

1、感知机模型

输入空间：$\mathcal{X} \in \mathbb{R}^n$

输出空间：$\mathcal{Y} = \{+1,-1\}$

特征空间：$\{f|f(\vec{x}) = sign(\vec{w} \cdot \vec{x} + b)\}$
($sign$ 为符号函数)

2、学习策略

$x_0$到超平面的距离：$\frac{1}{\Vert \vec{w} \Vert} \lvert \vec{w} \cdot \vec{x_0} + b \rvert$
($\Vert \vec{w} \Vert$ 是 $\vec{w}$ 的 $L_2$ 范数)

由于误分类点实际类别$y_i$与预测类别$f(\vec{x_i}) = sign(\vec{w} \cdot \vec{x_i} + b)$正负相反

因此误分类点到超平面的距离是：$-\frac{1}{\Vert \vec{w} \Vert} y_i (\vec{w} \cdot \vec{x_i} + b)$

为了便于求导，损失函数可以定义为：$L(\vec{w},b) = -\sum\limits_{x_i \in M} y_i (\vec{w} \cdot \vec{x_i} + b)$

3、学习算法

随机梯度下降：一次随机选取一个误分类点进行梯度下降

损失函数$L$ 分别对 $\vec{w}$ 和 $b$ 求梯度得：
$\nabla_{\vec{w}} L(\vec{w},b) = -\sum\limits_{x_i \in M} y_i \vec{x_i}$、
$\nabla_{b} L(\vec{w},b) = -\sum\limits_{x_i \in M} y_i$

参数更新方式：$\vec{w} = \vec{w} + \eta y_i x_i$、$b = b + \eta y_i$
($\eta \in (0,1]$ 为学习率)

参数一直更新，直到样本点中没有误分类点为止。

4、对偶问题

由上文的学习算法可得，$\vec{w}$ 和 $b$ 是通过逐次随机选取一个误分类点更新而来

因此可以设 $\vec{w}$ 的每个元素和 $b$ 都为0，参数总共更新 $n$ 次；

最终学习到的 $\vec{w}$ 和 $b$ 可以表示为：
$\vec{w} = \sum\limits_{i=1}\limits^{N} \alpha_i y_i x_i$、
$b = \sum\limits_{i=1}\limits^{N} \alpha_i y_i$
($\alpha_i = n_i \eta$，其中 $n_i$ 为点i被选中用于更新的次数)

由第三节中提到的 $\vec{w}$ 和 $b$ 的更新方式，可以反推出 $\alpha$ 和 $b$ 的更新方式：

$\alpha_i = \alpha_i + \eta$、$b = b + \eta y_i$

粗糙度定标公式整理

2023-02-19

1 $L_{opt}$ 公式形式

$L_{opt1}$$在低粗糙度时表现为常数，在高粗糙度时表现为指数形式：$

\begin{equation}\tag{1}
L_{opt1}(rms,\theta,pp) = \alpha rms^{\beta}
\end{equation}

$$$L_{opt2}$$在指数粗糙面和分形粗糙面时表现为$$\eqref{1}$$这类幂函数形式，在高斯粗糙面表现为：$$L_{opt2} = \alpha rms + \beta$

2 $L_{opt1}$ 公式

2.1 在HH极化下 $35^{\circ}$ 的公式

$\begin{array} \begin{equation} \end{equation}$