GAMES102 Lecture 01

news/2024/10/3 2:20:11

Lecture 01

图像是离散的像素
图形是具有数学意义的点、线、面，是连续的，有数学表达的
渲染是在解积分方程
仿真是在解偏微分方程

函数拟合

线性空间

元素之间有运算：加法、数乘
线性结构：对加分和数乘封闭
- 加法交换律、结合了、数乘分配律
基/维数：\(L=span\{V_1,V_2,...,V_N\} = \{\sum_{i=1}^na_iV_i\vert a_i\in R\}\)
- 每个元素就表达（对应）为\(n\)个实数，即一个向量\((a_1,a_2,...,a_n)\)
例子
- 欧氏空间：1D空间、2D平面、3D空间
- \(n\)次多项式：\(f(x)sum_{k=0}^na_kx^k\)

映射 (mapping)

一个原象只有对应一个象才是映射
每个原象都和一个象一一对应称为单射
每个象都有原象对应称为满射
同时满足单射和满射称为双射

函数 (Function)

这里特指实数到实数的变换

幂函数
三角函数
对数函数
指数函数
反三角函数
...

函数的集合（函数空间）

用若干个简单函数（“基函数”）线性组合张成一个函数空间
- \(L=span\{f_1,f_2,...,f_n\}=\{\sum_{i=1}^na_if_i(x)\vert a_i\in R\}\)
- 每个函数就表达（对应）\(n\)个实数，即系数向量\(\{a_1,a_2,...,a_n\}\)

空间的完备性：这个函数空间是否可以表示（逼近）任意函数

万能逼近定理：Weierstrass逼近定理

定理1：闭区间上的连续函数可用多项式级数一致逼近
定理2：闭区间上周期为\(2\pi\)的连续函数可用三角函数级数一致逼近

对于\([a,b]\)上的任意连续函数\(g\)，及任意给定的\(\epsilon>0\)，必存在\(n\)次代数多项式\(f(x)=\sum_{k=0}^nw_kx^k\)，使得\(\underset{x\in[a,b]}{min}\lvert f(x)-g(x)\rvert <\epsilon\)

赋范空间

内积诱导函数、距离
- \(<f,g>=\int_a^bf(x)g(x)dx\)
度量空间：可度量函数之间的距离
- Lp番薯
赋范空间+完备性=巴拿赫空间 Banach
内积空间（无限维）+完备性=希尔伯特空间 Hilbert

傅里叶级数

任何一个周期函数都可以写成\(cos\)和\(sin\)的组合

\[f(t)=A_0+\sum_{n=1}^{\infty}[a_n\cos(n\omega t)+b_n\sin(n\omega t)]\\ =A_0+\sum_{n=1}^\infty A_n\sin(n\omega t)+\psi_n\\ A_n是对函数进行伸缩，\psi_n是对函数进行平移 \]

如何求满足要求的函数？

大部分的实际应用问题
- 可建模为：找一个映射/变换/函数
- 输入不一样、变量不一样、维数不一样
三步
- 到哪找？
  - 确定某个函数集合/空间
    - 线性函数空间 \(A=span\{B_0(x),...,B_n(x)\}\)
      - 多项式函数\(span\{1,x,x^2,...,x^n\}\)
      - RBF函数
      - 三角函数
  - 函数表达为
    - \(f(x)=\sum_{k=0}^na_kB_k(x)\)
    - 求\(n+1\)个系数\((a_0,...,a_n)\) 待定系数
- 找哪个？
  - 度量哪个函数是最好的
    
    损失函数小则好
  - 目标1：加入要求很严格，函数一定要经过给定的点，就要插值（零误差）
    - \(y_i=f(x_i),i=0,1,...,n\)
    - 联立，求解线性方程组
      - \(\sum_{k=0}^{n}a_kB_k(x_i)=y_i,i=0,1,...,n\)
        
        求解\((n+1)\times(n+1)\)线性方程组
        
        \(n\)次拉格朗日插值多项式
    - 病态问题：系数矩阵条件数高时，求解不稳定
  - 目标2：函数尽量靠近数据的（逼近），函数与给定值不一定要严格相等，但要误差最小
    - \(min=\sum_{i=0}^n(y_i-f(x_i))^2\)
    - 也可以是绝对值、点到函数的垂足距离
      
      但是这样不好找，不好优化不好求解
    - 最小二乘法
      - 对各系数求导、得Normal equation 法方程（线性方程组）
        
        \(AX=b\)
      - 问题
        
        点多，系数少？
        
        表达能力不够，Underfitting 欠拟合
        
        点少，系数多？
        
        本来是逼近，结果每个点都插值，Overfitting (过拟合)
        
        虽然在给定点的误差为0，但在其他点非常震荡，无使用价值
        
        降低过拟合的概率：数据集中90%做拟合，10%不做拟合而做验证
        
        需要根据不同的应用与需求，不断尝试（不断”调参“）
- 怎么找？
  - 求解或优化：不同的优化方法与技巧，既要快、又要好

Lagrange插值函数

插值\(n+1\)个点、次数不超过\(n\)的多项式是存在且唯一的
- \(n+1\)个变量，\(n+1\)个方程
- \(p_k(x)=\prod_{i\in B_k}\frac{x-x_i}{x_k-x_i}\)
- 插值函数的自由度=未知量个数\(-\)已知量个数

避免过拟合的常用方法

数据去噪
- 剔除训练样本中的噪声
数据增广
- 增加样本数，或者增加样本的代表性和多样性
模型简化
- 预测模型过于复杂，拟合了训练样本中的噪声
- 选用更简单的模型，或者对模型进行裁剪
正则约束
- 适当的正则项，比如方差正则项、系数正则项

岭回归正则项

选择一个函数空间
- 基函数的线性表达
  - \(W=(w_0,w_1,...,w_n)\)
  - \(y=f(x)=\sum_{i=-}^nw_iB_i(x)\)
- 最小二乘拟合
  - \(\underset{W}{min}\lVert Y-XW\rVert^2\)
- Ridge regression 岭回归
  - \(\underset{W}{min}\lVert Y-XW\rVert^2+\mu\lVert W\rVert_2^2\)
    
    这里除了误差要最小，还要求系数的模也很小，\(\mu\)是一个权表示比例，这样可以让模型更加稳定

稀疏学习：稀疏正则化

冗余基函数（过完备）

不知道该选哪些基函数，但知道好多函数都跟要求的函数类似，将它们全拿来，这些函数可能过冗余的，甚至是线性相关的（过完备）
通过优化来选择合适的基函数
- 系数向量的\(L_0\)模（非0元素个数）尽量小
  
  非0元素越少，0元素就越多
  
  那么也就是希望系数为0的项尽量多，通过这样的优化，就只是选了部分我要的基函数来表达我要的函数
- 挑选（“学习”）出合适的基函数
  - \(\underset{\alpha}{min}\lVert Y-XW\rVert^2+\mu\lVert W\rVert_0\)
  - \(\underset{\alpha}{min}\lVert Y-XW\rVert^2,\ \rm s.\rm t. \lVert W\rVert_0 \le\beta\)

压缩感知

有一些信号\(x\)，比如是很高维的，其中只有少量的元素是非0，那么要记录这样的信号需要很长的存储

于是可以通过一个采样矩阵\(\Phi\)，采样矩阵对其进行一个点积（线性乘法）得到一个短的\(y\)

已知采样矩阵\(\Phi\)和\(y\)，能不能恢复出\(x\)
- 数学上不可能，因为方程个数小于未知数个数，\(x\)有无穷多个
- 但是其中有个解最稀疏，这个解是唯一的
那么如果一个信号是稀疏的，通过这样一个优化，就能用很少的存储量存储这个稀疏信号，通过这样的优化反写出\(x\)，并且在以概率1收敛，不保证每次都是真解，但是很大概率是真解（解1000次有999次这样），不是一定真解的原因是中间优化存在一些随机量