Yuchen You

χ2\chi^2χ2 Distribution 卡方分布就是通过 n 个(维) 标准正态随机变量的平方和的分布 对于 Z ∼N(0,1)\sim N(0,1)∼N(0,1) 的分布 U = Z2Z^2Z2 被称为1自由度卡方分布 (chi-square distribution with 1 degree of freedom) , 写作 χ2(1)\chi^2(1)χ2(1) 定义 U1,U2,⋯UnU_1, U_2,\cdots U_nU1​,U2​,⋯Un​ 是独立卡方分布变量且有一个自由度，那么 分布 V=U1+U2+⋯+Un=χ2(n)V = U_1 + U_2 + \cdots + U_n = \chi^2(n) V=U1​+U2​+⋯+Un​=χ2(n) 就拥有chi-square distribution with n degrees of freedom 从 Gamma 函数到卡方分布 注意到，欧拉 gamma 函数的参数 α=n2,β=2\alpha = \frac{n}{2}, \beta = 2α=2n​,β=2 的情况就是卡方分布的函数 χ2(n)\chi^ ...

定理内容 SAT 问题是 NP-complete 问题 由于 SAT 问题在给定 certificate 的情况下只需要逐个检验是否符合, 复杂度是 polynomial -> NP, 因此这里只需要证明其是 NP-hard 即可 证明 NP-Hard 利用 NP-hard 的定义, 这里需要证明对所有的 language L∈NPL\in NPL∈NP 都有 L≤pSATL\le_p SATL≤p​SAT (因为 SAT 问题往往会作为 NP-hard origin 来归纳其他的问题是否 NP-hard, 这里不能用其他 NP-hard 来归纳之) 因此假设我们有一个任意 np 问题的 instance x 和一个输入语言 L ∈\in∈ NP, 即存在 Verify−LVerify-LVerify−L 可以在多项式时间内决定 L; 证明目的是是否存在一个 SAT instance ϕ\phiϕ satisfiable iff 存在 c 使得 Verify-L(x,c) accept 定义 VL 算法为一个 TM, 并将其编码为一个 ∣x∣k×∣x∣k|x|^k\times | ...

定义 A language LLL is NP-complete if L∈L\inL∈ NP LLL is NP-hard 证明方法: polynomial-time mapping reduction 定义归纳关系 A≤pBA\le_p BA≤p​B 表示 ∃f s.t. x∈A⇔f(x)∈B\exists f \text{ s.t. } x \in A\Leftrightarrow f(x) \in B∃f s.t. x∈A⇔f(x)∈B 引理 lemma B∈P⇒A∈PB\in P \Rightarrow A \in PB∈P⇒A∈P AAA NP-hard ⇒\Rightarrow⇒ B NP-hard 用法 选取一个已知的 NP-hard 问题 A 来归纳关系 A≤pBA\le_p BA≤p​B 定义问题转变映射: 如何将问题集合 A 的某个确定 instance 转变为 B 的对应的 instance 证明这个转变 f 的时间复杂度是 polynomial 证明 correctness: 证明一个能解决 A 的 answer 同样在转变的问题中可以以同样的答案 ...

树的定义 没有 cycle 的无向图 rooted tree 存在某个 node 作为根节点 每个节点事实上都可以作为 root 二叉树的操作复杂度 二叉树的方法时间复杂度看的主要是二叉树自身的结构形状，如果是 complete 树是最好情况; 如果是 每个节点都只有一个子枝，其复杂度最大，是 worst case 数组法 insert 最好 O(1) 最差 O(n) 和树的排布方式有关，如果树的根节点的某个字节点为空那么直接插入，复杂度 O(1); 如果全部排满我们需要遍历找到空节点位置那么时间复杂度 O(n) remove 最差 O(n) parent O(1) child O(1) space 最好 O(n) 最差 O(2^n) 这里取决于数据的排布方式, 如果是完全二叉树，那只需要 O(n) 空间; 如果是完全一叉树 (每个node最多只有一个节点) 就需要 O(2^n) 空间 指针法 insert 好 O(1) 坏 O(n) remove 坏 O(n) parent O(n) 因为没有爹指针 child O(1) space 好 O(n) 坏 ...

SRAM, DRAM, SSD SRAM 静态随机访问内存 由六个三极管组成 脆弱volatile：需要常量的电压来保存数据 快速: 1ns 左右的数据访问时间 空间占用率低: 只能在芯片上存储 MB 大小的数据 DRAM 动态随机访问内存 每一个 bit 用一个 三极管和一个电容组成 需要常量的电压来保存数据 缓慢: 大约 50 ns 的访问时间 便宜，可以提供 GB 单位的内存空间 现代硬件结构中这个往往被用作是主要内存硬盘 Disk 光盘 硬件将数据存储在 磁电,通过光盘的旋转来进行数据获取 数据获取非常缓慢，约 3ms 的访问时间 不脆弱：即使没有电压也可以保存数据 固态硬盘 solid-state disk, SSD 相比光盘，访问时间快很多，大约 0.1 ms 的时间 十分便宜 总结 reg, cache, memory 的速度和内存大小的关系如下图: 缓存 Caches 功能 缓存存储了我们认为最有可能会被使用的数据, 从时间和空间维度，共有两种可能： 空间(spatial locality)：最近被调用的数据的附近更有可能会被调用 时间(temp ...

NP-hard 定义 一个语言 LLL 是 NP-hard 若对任意 NP 中的语言 X 存在关系 X≤pLX\le_p LX≤p​L 定义这个关系为：at least as hard as 并不要求 NP-hard 问题属于 NP NP-complete 定义语言 LLL 是 NP-complete 的如果 1. L∈L\inL∈ NP 且 2. L∈L\inL∈ NP-hard 从简单上来认识这个 class，可以理解为这是最难解决的 NP 问题 NP-hard 的复杂度性质 如果对于任何一个 NP-hard 的问题，存在一个 多项式复杂度的解 那么任何 NP 问题都可以在 P 时间内解决 因此有两种可能性: NP-complete 问题全部都属于 P NP-complete 问题全部需要超过 多项式时间复杂度的求解难度 NP-hard reduction 定义符号 ≤p\le_p≤p​ 使得 A≤pB⇔A\le_p B \LeftrightarrowA≤p​B⇔ ∃f\exists f∃f 多项式函数 s.t. x∈A⇔f(x)∈Bx\in A \Leftrightarrow ...

P 类 多项式可解类 定义 P class:= 所有的 decidable 的 problem 中可以在多项式中决定的集合 即若有 L∈PL\in PL∈P, 那么就会存在图灵机 MMM decides LLL, 且 MMM 的时间复杂度是 O(nk)O(n^k)O(nk) 难以解决的问题-例: traveling salesperson problem (TSP) 旅行商问题 在一个图中，是否存在一条路径经过每个点一次且路径权值和小于常数 b ? 这个问题的求解步骤或许非常麻烦，但是当我们提出一种解之后，我们很容易就可以根据定义来进行验证其真伪，我们称这类容易验证的问题为 efficiently verifiable 其他难解决易证明问题 走迷宫问题、数独求解问题 证明属于 P 类 证明属于 decidable 问题 (用伪代码定义图灵机的存在, 需要证明 correctness) 证明过程可以在 O(nk)O(n^k)O(nk) 时间内停止，这里 nnn 表示 input size NP 类 多项式可验证类 定义 NP class := 所有的能在多项式时间内验证一个问题的真 ...

point estimator 和 point estimate estimator 一个从样本数据计算实验参数的过程，本质上是一个随机变量, 或者说是一个随机变量的函数 (简单理解为随机变量的函数还是随机变量); 其作为函数而言，输入量是 多个随机变量 (注意表达式这里不能用数值，应该用随机变量)，但不能包括实验的参数 θ\thetaθ 其观测值为 estimate estimate 是一个数值 目的 通过样本的数据来估算 population 具有的特征 两个研究角度 对于给定的 point estimate 如何评价估计效果？ 如何计算 point estimate? MSE 最小平方误差 bias B[θ^]=E[θ^−θ]=E[θ^]−θB[\hat \theta ] = E[\hat \theta - \theta] = E[\hat\theta] - \thetaB[θ^]=E[θ^−θ]=E[θ^]−θ unbiased: B[θ^]=0B[\hat\theta] = 0B[θ^]=0 MSE MSE[\hat \theta] = (E[\hat \theta - ...

定义 总体分布函数完全未知或只知形式不知参数情况下，推断总体某些特性，提出某些关于整体的假设，根据样本对所提出的假设作出接受或是拒绝的决策 假设思路 有两种假设: 零假设和备择假设, 证明思路是将目标论点作为备择假设，定义补集为零假设，通过积分证明零假设不成立，从而证明备择假设(证明目的)成立 两类决策错误 第一类决策错误 弃真错误: H0H_0H0​ 为真的时候拒绝 H0H_0H0​ 第二类决策错误 取伪错误: H0H_0H0​ 不为真的时候接受 H0H_0H0​ 零假设的错误可能 如果用假设检验的思路，只会说明 reject H0H_0H0​ 或者 not reject H0H_0H0​, 那么我们只有可能会犯弃真错误而不会犯第二类错误，而第一类错误我们可以用一个变量来进行描述 显著性水平 α\alphaα significance level 当原假设实际上正确时, 检验统计量落在拒绝域的概率, 就是犯弃真错误的概率 在正态分布的cdf积分表中属于是积分结果一类 P-value 描述了当前样本在零假设前提下更加极端的概率和，也就是不符合零假设的概率大小 如果 p-val 越大 ...