[C++] [ICS-46] 为什么std::stack会有const T& top() const方法?Why std::stack has const T& top() const method?

[C++] [ICS-46] 为什么std::stack会有const T& top() const方法?Why std::stack has const T& top() const method?

C++|计算机 ComputerScience


@ZYX 写于2020年11月01日

结论 Conclusion

该方法与复制/赋值初始化有关,若没有这个方法,那么通过复制/赋值初始化的stack将会无法使用top()方法。 This method is related with copy/assignment initialization. If stack did not have this method, the const stack, which initialized through copy or assignment, could not call top() method. (更多…)
           
[Anaconda] Jupyter Notebook 更改默认浏览器 / Change Jupyter Notebook Default Browser

[Anaconda] Jupyter Notebook 更改默认浏览器 / Change Jupyter Notebook Default Browser

闲谈 Digressions


@ZYX 写于2020年10月19日

Jupyter Notebook 更改默认浏览器 / Change Jupyter Notebook Default Browser

Steps

  1. Generate jupyter notebook config through CMD. 通过命令行生成jupyter notebook的配置文件 >jupyter notebook --generate-config
    • The config file jupyter_notebook_config.py will be generated in the (user directory) /.jupyter directory. 配置文件将生成在 (用户目录) / .jupyter 目录下
(更多…)
           
[Python Data Science Handbook] Ch 2 Introduction to Numpy

[Python Data Science Handbook] Ch 2 Introduction to Numpy

闲谈 Digressions


@ZYX 写于2020年10月06日

Chapter 2 Introduction to NumPy

Understanding Data Types in Python

A Python Integer Is More Than Just an Integer

  • A Python integer is a pointer to a position in memory containing all the Python object information, including the bytes that contain the integer value.

A Python List Is More Than Just a List

  • The Python list, on the other hand, contains a pointer to a block of pointers, each of which in turn points to a full Python object like the Python integer we saw earlier

Fixed-Type Arrays in Python

  • The built-in array module (available since Python 3.3) can be used to create dense arrays of a uniform type
    In[6]:import array
            L = list(range(10))
            A = array.array('i', L)
            A
    Out[6]: array('i', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
    
    • Much more useful is the ndarray object of the NumPy package.
      • While Python’s array object provides efficient storage of array-based data
      • NumPy adds to this efficient operations on that data.
(更多…)
           
自然语言处理NLP训练营笔记 Day02

自然语言处理NLP训练营笔记 Day02

闲谈 Digressions


@ZYX 写于2020年08月24日

Day 02

文本处理流程

  • Pipeline Day02-01图

分词 Word Segementation

  • 分词工具
    • Jieba分词
    • SnowNLP
    • LTP
    • HanNLP

最大匹配算法 max-matching

  • 本质上是贪心算法
    • 可能无法找到全局最优解
  • 参数
    • max_len
  • 缺点
    • 只能保证局部最优
    • 效率低
    • 难处理歧义 (不能考虑语义)
前向最大匹配算法 forward-max matching
  • 步骤
    • 取 前 $max\_len$ 个字符为 str
    • 若 str 在词典里则返回第一步, 否则
      • 取 $max\_len-1$ 个字符为 str
      • 重复第二步
        def max_matching(ss:str,d:set):
        if len(ss)==0 or ss in d:
            return ss
        else:
            return max_matching(ss[:-1],d)
        def forward_max_matching(s:str,d:set,max_len:int)
        i=0
        result=list()
        while i<len(s):
            word=max_matching(s[i:i+max_len],d)
            result.append(word)
            i+=len(word)
        
(更多…)
           
[机器学习西瓜书] 第06章 支持向量机 笔记

[机器学习西瓜书] 第06章 支持向量机 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年08月10日

第06章 支持向量机

6.1 间隔与支持向量

  • 训练样本集 $D=\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})\}, y_{i} \in \{-1,+1\}$
  • 最基本的想法就是基于训练集 $D$ 在样本空间中找到一个划分超平面,将不同类别分开
    • 可能有很多
    • 应该去找位于两类训练样本正中间
      • 因为该超平面对训练样本局部扰动容忍性最好
  • 在样本空间中,划分超平面可通过如下线性方程来描述: [6.1] $w^{T}x+b=0$
    • 法向量 $w=(w_{1};w_{2};\dots;w_{d})$ 决定了超平面的方向
    • 位移项 $b$ 决定了超平面与原点之间的距离
    • 划分超平面 可表达为 $(w,b)$
    • 样本空间中任意点 $x$ 到超平面 $(w,b)$ 的距离 [6.2] $r=\frac{|w^{T}x+b|}{||w||}$
    • 假设超平面能正确分类,则令 [6.3] $\begin{cases} w^{T}x+b\ge +1 &\text{, } y_{i}=+1; \\ w^{T}x+b\le -1 &\text{, } y_{i}=-1; \end{cases}$
  • 支持向量 (support vector) 图6.2 支持向量与间隔
    • 距超平面最近的这几个训练样本点使式[6.3]成立, 称为支持向量(support vector)
    • 间隔(margin)
      • 两个异类支持向量到超平面的距离之和 $\gamma = \frac{2}{||w||}$ , 称为间隔(margin)
    • 最大间隔(maximum margin)
      • 欲找到具有最大间隔(maximum margin)的划分超平面
      • 找到能满足式[6.3]中约束的参数 $w$ 和 $b$ , 使得 $\gamma$ 最大,即 [6.5] $\begin{aligned} &\max_{w,b} \frac{2}{||w||} \\ &\text{s.t.} y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$
  • 支持向量机
    • 为了最大化间隔,仅需最大化 $||w||^{-1}$,等价于最小化 $||w||^{2}$。可重写[6.5] 为 $\begin{aligned} &\min_{w,b} \frac{1}{2}||W||^{2} \\ &\text{s.t. } y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$
      • 这就是支持向量机(Support Vector Machine,简称SVM)的基本型

6.2 对偶问题

  • 对[6.6]使用拉格朗日乘子法可得到其对偶问题(dual problem)
    • 对[6.6]的每条约束添加拉格朗日乘子 $\alpha_{i} \ge 0$,则该问题的拉格朗日函数可写为 [6.8] $L(w,b,\alpha)=\frac{1}{2}||w||^{2}+\sum^{m}_{i=1}\alpha_{i}(1-y_{i}(w^{T}x_{i}+b))$
      • 其中 $\alpha=(\alpha_{1};\alpha_{2};\dots;\alpha_{m})$
      • 令 $w$ 和 $b$ 的偏导为零,得
        • [6.9] $w=\sum^{m}_{i=1}\alpha_{i}y_{i}x_{i}$
        • [6.10] $0=\sum^{m}_{i=1}\alpha_{i}y_{i}$
      • 将[6.9]代入[6.8],可消去 $w$ 和 $b$。再考虑[6.10]的约束,就得到[6.6]的对偶问题 [6.11] $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}x^{T}_{i}x_{j} \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$
      • 解出 $\alpha$ 后,求出 $w$ 与 $b$ 得到模型 [6.12] $\begin{aligned} f(x)&=w^{T}x+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}x^{T}_{i}x+b \end{aligned}$
  • KKT条件
    • 从对偶问题[6.11]解出的 $\alpha_{i}$ 是[6.8]中的拉格朗日乘子, $\alpha_{i}$ 恰对应着训练样本 $(x_{i},y_{i})$
      • SMO(Sequential Minimal Optimization) 求解算法
        • 基本思路: 先固定 $\alpha_{i}$ 之外的所有参数,然后求向上的极值
          • 因为有约束 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$
            • 若固定 $\alpha_{i}$ 之外的其他变量,则 $\alpha_{i}$ 可由其他变量导出.
        • 每次选择两个变量 $\alpha_{i}$ 和 $\alpha_{j}$,并固定其他参数
        • 在参数初始化后, SMO不断执行如下两步直至收敛:
          1. 选取一对需更新的变量 $\alpha_{i}$ 和 $\alpha_{j}$
            • 只需选取的 $\alpha_{i}$ 和 $\alpha_{j}$ 中有一个不满足KKT条件[6.13],目标函数就会在选代后减小
            • SMO先选取违背KKT条件程度最大的变量。第二个变量应选择一个使目标函数值减小最快的变量
              • KKT 条件违背的程度越大,则更新后可能导致的函数值减幅越大.
              • SMO采用了一个启发式:使选取的两变量所对应样本之间的间隔最大
          2. 固定 $\alpha_{i}$ 和 $\alpha_{j}$ 以外的参数,求解[6.11],更新$\alpha_{i}$ 和 $\alpha_{j}$
            • 仅考虑 $\alpha_{i}$ 和 $\alpha_{j}$ 时,[6.11]中的约束可重写为 [6.14] $\alpha_{i}y_{i}+\alpha_{j}y_{j}=c, \alpha_{i} \ge 0, alpha_{j} \ge 0$
              • $c=-\sum_{k \not = i,j}\alpha_{k}y_{k}$ 是使 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$ 成立的常数
            • 消去[6.11]中的变量 $\alpha_{j}$,则得到一个关于 $\alpha_{i}$ 的单变量二次规划问题
              • 这样的二次规划问题具有闭式解,于是不必调用数值优化算法即可高效地计算出新的 $\alpha_{i}$ 和 $\alpha_{j}$
      • 如何确定偏移项b
        • 到对任意支持向量$(x_{s}, y_{s})$,都有 $y_{s}f(x_{s})=1$,即 [6.17] $y_{s}(\sum_{i \in s}\alpha_{i}y_{i}x^{T}_{i}x_{s}+b)=1$
          • 其中 $S=\{ i| \alpha_{i}>0 , i=1,2,\dots,m \}$ 为所有支持向量的F标集
        • 现实任务中, 使用所有支持向量求解的平均值 [6.18] $b=\frac{1}{|S|}\sum_{s\in S}(y_{s}-\sum_{i\in S}\alpha_{i}y_{i}x^{T}_{i}x_{s})$
    • 因为[6.6]中有不等式约束,因此上述过程需满足KKT(Karush-Kuhn-Tucker)条件,即要求 [6.13] $\begin{cases} &\alpha_{i}\ge 0; \\ &y_{i}f(x_{i})-1\ge 0; \\ &\alpha_{i}(y_{i}f(x_{i})-1)=0 \end{cases}$
      • 对任意训练样本,总有$\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1$
        • 若 $\alpha_{i}=0$,则该样本将不会在[6.12]的求和中出现,也就不会对 $f(x)$ 有任何影响
        • 若 $\alpha_{i}>0$,则有 $y_{i}f(x_{i})=1$,所对应的样本点位于最大间隔边界上,是一个支持向量
        • 这显示出支持向量机的一个重要性质:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关
(更多…)
           
[机器学习西瓜书] 第05章 神经网络 笔记

[机器学习西瓜书] 第05章 神经网络 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年08月06日

第05章 神经网络

5.1 神经元模型

  • 神经网络是由具有适应性的简单单元组成的广泛并行互连的网络,它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应
    • 谈论神经网络时指的是神经网络学习
      • 机器学习神经网络这两学科的交叉部分
  • 最基本的成分是神经元(neuron)模型,即"简单单元"
    • 如果某神经元的电位超过了一个阈值(threshold),就会被激活
      • 兴奋起来,向其他神经元发送化学物质
    • M-P神经元模型1943年,[McCulloch and Pitts, 1943]
      • 神经元接收到来自 $n$ 个其他神经元传递过来的输入信号
        • 这些输入信号通过带权重的连接(connection)进行传递
      • 神经元接收到的总输入值将与神经元的阀值进行比较
      • 然后通过激活函数 (activation function) 处理,以产生输出
        • 理想的是阶跃函数,将输入值映射为输出值01
        • 实际常用Sigmoid函数,因为阶跃函数具有不连续、不光滑等不太好的性质
          • 它把可能在较大范围内变化的输入值挤压到(0 , 1) 输出值范围内,因此有时也称为挤压函数(squashing function)
  • 神经网络
    • 把许多个这样的神经元按一定的层次结构连接起来,就得到了神经网络
      • 只需将一个神经网络视为包含了许多参数的数学模型,即若干个函数相互(嵌套)代入而得
(更多…)
           
[机器学习西瓜书] 第04章 决策树 笔记

[机器学习西瓜书] 第04章 决策树 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年08月04日

第04章 决策树

4.1 基本流程

  • 决策树(decision tree) 二分类任务为例
    • 可看作对"当前样本属于正类吗?"这个问题的决策判定过程
    • 决策树是基于树结构来进行决策的
      • 例如对"这是好瓜吗?"进行决策时,通常会进行一系列的判断或子决策
        • 先看"它是什么颜色?" 如果是"青绿色"
        • 再看"它的根蒂是什么形态?" 如果是"蜷缩"
        • 再判断"它敲起来是什么声音?"
        • 最后得出决策: 好瓜
    • 结构
      • 每个结点包含的样本集合根据属性测试被划分到子结点
      • 根结点 一个
        • 对应于一个属性测试
        • 包含样本全集
        • 内部结点 若干个
        • 对应于一个属性测试
      • 叶结点 若干个
        • 对应于决策结果
      • 根结点每个叶结点路径对应了一个判定测试序列
    • 目的
      • 为了产生一棵泛化能力强的决策树
  • 基本流程遵循分治(divide-and-conquer)策略
    输入: 训练集D={(X1,Y1) , (X2,Y2),.. . , (Xm, Ym)}
            属性集A={a1, a2, ..., ad}
    输出: 以node为根结点的决策树
    TreeGenerate(D,A):
        生成结点node;
        if D 中样本金属于同一类别C then
            将node 标记为C 类叶结点return #递归返回,情形(1)
        end if
        if A= 0 ORD 中样本在A上取值相同 then
            将node 标记为叶结点,其类别标记为D 中样本数最多的类; return #递归返回,情形(2)
        end if
        从A中选择最优划分属性向_a
        for _a_v in _a:
            为node 生成一个分支; 令D_v 表示D 中在_a上取值为_a_v的样本子集;
            if D_v为空 then
                将分支结点标记为叶结点,其类别标记为D 中样本最多的类; return #递归返回,情形(3)
            else
                以TreeGenerate(D_v, A-{_a})为分支结点 #从A中去掉_a
            end if
        end for
    
    • 决策树的生成是一个递归过程
      • 有三种情形会导致递归返回:
        1. 无需划分: 当前包含的样本属于同一类别
        2. 无法划分: 当前属性集为空,或是所有样本在所有属性上取值相同
          • 把当前结点标记为叶结点
          • 并将其类别设定为该结点所含样本最多的类别
            • 是在利用当前结点的后验分布
        3. 不能划分: 当前结点包含的样本集合为空
          • 同样把当前结点标记为叶结点
          • 但将其类别设定为其父结点所含样本最多的类别
            • 是把父结点的样本分布作为先验分布
(更多…)
           
[机器学习西瓜书] 第03章 线性模型 笔记

[机器学习西瓜书] 第03章 线性模型 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年08月02日

第03章 线性模型

3.1 基本形式

  • 数学表达
    • 变量:x
      • 示例$x=(x_{1};x_{2};\cdots;x_{d})$
        • 由 $d$ 个属性描述
        • $x_{i}$是 $x$ 在第 $i$ 个属性上的取值
    • 线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数 $f(x)=w_{1}x_{1}+w_{2}x_{2}+\cdots+w_{d}x_{d}+b$
      • 一般用向量形式写成 $f(x)=w^{T}x+b$
        • $w=(w_{1};w_{2};\cdots;w_{d})$ $w$ 和 $b$ 学得之后,模型就得以确定.
  • 许多非线性模型(nonlinear model),可在线性模型的基础上,通过引入层级结构或高维映射而得
  • 由于$w$ 直观表达了各属性在预测中的重要性,因此线性模型有很好的可解释性(comprehensibility)

3.2 线性回归

  • "线性回归" (linear regression)试图学得一个线性模型
    • 以尽可能准确地预测实值输出标记.
  • 数学表达
    • 变量
      • 数据集$D=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots, (x_{m},y_{m})\}$
        • 其中$x_{i}=(x_{i1}; x_{i2}; \cdots; x_{id}), y_{i}\in \R$
        • 简化为 $D=\{(x_{i},y_{i})\}^{m}_{i=1}$
          • 其中 $x_{i}\in \R$
    • 对离散属性
      • 若属性值间存在"序" (order)关系,可通过连续化将其转化为连续值
        • 高,中,低 → 1.0, 0.5, 0.0
      • 若属性值间不存在序关系,假定有 $k$ 个属性值,则通常转化为 $k$ 维向量
        • 属性"瓜类"的取值"西瓜" "南瓜" "黄瓜"可转化为(0,0,1) ,(0,1,0),(1,0,0)
    • 线性回归试图学得 $f(x_{i})=wx_{i}+b$,使得 $f(x_{i})\simeq y_{i}$
  • 确定 $w$ 和 $b$:
    • 关键在于如何衡量 $f(x)$ 与 $y$ 之间的差别
      • 均方误差是回归任务中最常用的性能度量
        • 均方误差有非常好的几何意义
          • 它对应了欧几里得距离或简称"欧氏距离" (Euclidean distance)
    • 试图让均方误差最小化 $(w^{*},b^{*})\begin{aligned} &=\arg\min_{(w,b)}\sum^{m}_{i=1}(f(x_{i})-y_{i})^{2} \\ &=\arg\min_{(w,b)}\sum^{m}_{i=1}(y_{i}-wx_{i}-b)^{2} \end{aligned}$
      • 基于均方误差最小化来进行模型求解的方法称为最小二乘法 (least square method)
        • 就是试图找到一条直线
          • 使所有样本到直线上的欧氏距离之和最小.
      • 最小二乘"参数估计" (parameter estimation)
        • 求解 $w$ 和 $b$ 使 $E_{(w,b)}=\sum^{m}_{i=1}(y_{i}-wx_{i}-b)^{2}$ 最小化的过程,称为线性回归模型的最小二乘参数估计(parameter estimation)
        • 可将 $E_{(w,b)}$ 分到对 $w$ 和 $b$ 求导
          • $\frac{\partial E_{(w,b)}}{\partial w}=2(w\sum^{m}_{i=1}x_{i}^{2}-\sum^{m}_{i=1}(y_{i}-b)x_{i})$
          • $\frac{\partial E_{(w,b)}}{\partial b}=2(mb-\sum^{m}_{i=1}(y_{i}-wx_{i}))$
        • 令偏导为零,可得到 $w$ 和 $b$ 最优解的闭式(closed-form)解
          • $w=\frac{\sum^{m}_{i=1}y_{i}(x_{i}-\bar{x})}{\sum^{m}_{i=1}x_{i}^{2}-\frac{1}{m}(\sum^{m}_{i=1}x_{i})^{2}}$
          • $b=\frac{1}{m}\sum^{m}_{i=1}(y_{i}-wx_{i})$
  • 多元线性回归(multivariate linear regression)
    • 更一般的情形 $f(x_{i})=w^{T}x_{i}+b$,使$f(x_{i})\simeq y_{i}$
    • 数学表达
      • 令向量$\hat w=(w;b)$
      • 把数据集 $D$ 表示为一个 $m \times (d+1)$ 大小的矩阵 $X$
        • 每行对应于一个示例
        • 每行前 $d$ 个元素对应于示例的 $d$ 个属性值,最后一个元素恒置为1 $X=\begin{pmatrix}x_{11}&x_{12}&\dots&x_{1d}&1 \\ x_{21}&x_{22}&\dots&x_{2d}&1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{m1}&x_{m2}&\dots&x_{md}&1 \end{pmatrix}=\begin{pmatrix} x^{T}_{1}&1 \\ x^{T}_{2}&1 \\ \vdots&\vdots \\ x^{T}_{m}&1 \end{pmatrix}$
      • 把标记也写成向量形式 $y=(y_{1};y_{2};\dots;y_{m})$
        • 有$\hat w^{*}=\arg\min_{\hat w}(y-X\hat w)^{T}(y-X\hat w)$
      • 令 $E_{\hat w}=(y-X\hat w)^{T}(y-X\hat w)$,对 $\hat w$求导 $\frac{\partial E_{\hat w}}{\partial \hat w}=2X^{T}(X\hat w-y)$
        • 令上式为零可得 $\hat w$ 最优解的闭式解
          • 当 $X^{T}X$ 为满秩矩阵(full-rank matrix)或正定矩阵(positive definite matrix)时,可得 $\hat w^{*}=(X^{T}X)^{-1}X^{T}y$
            • $(X^{T}X)^{-1}$ 是 $(X^{T}X)$ 的逆矩阵
            • 令 $\hat x_{i}=(x_{i},1)$,得 $f(\hat x_{i})=\hat x^{T}_{i}(X^{T}X)^{-1}X^{T}y$
          • 然而,现实任务中 $X^{T}X$ 往往不是满秩矩阵
            • 此时可解出多个 $\hat w$ ,它们都能使均方误差最小化
            • 选择哪一个解作为输出,将由学习算法的归纳偏好决定
              • 常见的做法是引入正则化(regularization)项
  • 线性模型虽简单,却有丰富的变化
    • 对数线性回归(log-linear regression) $\ln y=w^{T}x+b$
      • 它实际上是在试图让 $e^{w^{T}x+b}$ 逼近 $y$
      • 形式上仍是线性回归,但实质上已是在求取非线性函数映射
    • 广义线性模型(generalized linear model)
      • 更一般地,考虑单调可微函数 $g(\cdot)$
        • 令 $y=g^{-1}(w^{T}x+b)$
        • $g(\cdot)$ 称为联系函数(link function)
(更多…)
           
已到首页—下一页>>