【概率模型】HMM(隐马尔可夫模型)

马尔科夫过程

马尔科夫过程就是一个状态转移图
其可以有N个状态。状态到状态的转换是赋予概率的。
于是可以用$NN$的*概率转移矩阵表示
如一个例子
假设几个月大的宝宝每天做三件事：玩（兴奋状态）、吃（饥饿状态）、睡（困倦状态），这三件事按下图所示的方向转移：

这就是一个简单的马尔可夫过程。需要注意的是，这和确定性系统不同，每个转移都是有概率的，宝宝的状态是经常变化的，而且会任意在两个状态间切换：

如图。这个过程的概率转移矩阵A为

每行累加和为1.

HMM

有时我们无法看到$状态序列Q$,只能看到观察序列（或输出序列）$O$
这时隐马尔可夫模型就产生了。
一个是可观测的状态集O和一个隐藏状态集Q
还是上面的例子。为了简化描述，将“玩”这个状态去掉，让宝宝每天除了吃就是睡

在HMM里。我们使用混淆矩阵B

且运用独立性假设：假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其它观测状态无关。

模型定义

• N 表示隐藏状态的数量，我们要么知道确切的值，要么猜测该值；
• M 表示可观测状态的数量，可以通过训练集获得；
• π={πi} 为初始状态概率；代表的是刚开始的时候各个隐藏状态的发生概率；
• $A=\{a_{ij}\}$为隐藏状态的转移矩阵；N*N维矩阵，代表的是第一个状态到第二个状态发生的概率；
• $B=\{b_{ij}\}$为混淆矩阵，N*M矩阵，代表的是处于某个隐状态的条件下，某个观测发生的概率。

HMM要解决的问题

HMM主要解决三大类问题

• 模型评估问题
  已知一个观察序列。和模型λ=（A,B,π}的条件下，观察序列O的概率，即P(O|λ}。
  对应算法：向前算法、向后算法
• 解码问题
  从观察序列推断隐藏状态序列
  也就是已知模型参数和可观察状态序列，怎样选择一个状态序列S={S1,S2,…,ST}，能最好的解释观测序列O。
  对于算法维特比算法
• 参数估计问题
  数据集仅有观测序列，如何调整模型参数 λ=(π, A, B), 使得P(O|λ)最大
  对应算法：鲍姆-韦尔奇算法

【概率模型】CRF:Conditional Random Field(条件随机场)

CRF主要用于序列标注，可以简单理解为对序列的每一帧都进行分类

逐帧softmax

为了解决上述问题。可以利用逐帧softmax
将这个序列用 CNN 或者 RNN 进行编码后，接一个全连接层用 softmax 激活，如下图所示：

条件随机场

然而，当我们设计标签时，比如用 s、b、m、e 的 4 个标签来做字标注法的分词，目标输出序列本身会带有一些上下文关联，比如 s 后面就不能接 m 和 e，等等。逐标签 softmax 并没有考虑这种输出层面的上下文关联，所以它意味着把这些关联放到了编码层面，希望模型能自己学到这些内容，但有时候会“强模型所难”。

而 CRF 则更直接一点，它将输出层面的关联分离了出来，这使得模型在学习上更为“从容”：

而在序列标注任务中，我们的正确答案是一般是唯一的。比如“今天天气不错”，如果对应的分词结果是“今天/天气/不/错”，那么目标输出序列就是 bebess，除此之外别的路径都不符合要求。

换言之，在序列标注任务中，我们的研究的基本单位应该是路径，我们要做的事情，是从 k^n 条路径选出正确的一条，那就意味着，如果将它视为一个分类问题，那么将是 k^n 类中选一类的分类问题。

这就是逐帧 softmax 和 CRF 的根本不同了：前者将序列标注看成是 n 个 k 分类问题，后者将序列标注看成是 1 个 k^n 分类问题。
具体来讲，在 CRF 的序列标注问题中，我们要计算的是条件概率：

我们举个例子：

我们可以得到以下模型图：

当模型输入句子 ”Dog caught the cat“ 时，我们希望模型能够输出标注序列：“n v a n”的概率最大
那么如何根据这个状态图计算出序列”n v a n“的出现的概率呢？
这里就引出了概率无向图模型：（注：个人认为条件随机场模型是一个概率无向图模型，而线性链条件随机场是一个有向图模型）

对于上列图，我们定义两种特征

• 转移特征
  定义在边上的特征。
  表示观察序列X在i及i-1位置上的标记转移概率
• 状态特征
  定义在点上的特征 $$s_k(y_i,X,i)$$ 表示对于观察序列X其i位置的标记概率

定义CRF中的特征函数

现在，我们正式地定义一下什么是CRF中的特征函数，所谓特征函数，就是这样的函数，它接受四个参数：

【ソフト工学】Gitコマンド

よく使用のコマンド

远程仓库相关

检出仓库：git clone git://github.com/jquery/jquery.git
查看远程仓库：git remote -v
添加远程仓库：git remote add [name] [url]
删除远程仓库：git remote rm [name]
修改远程仓库： git remote set-url —push[name][newUrl]
拉取远程仓库： git pull [remoteName] [localBranchName]
推送远程仓库： git push [remoteName] [localBranchName]

上传项目到远程分支

1.初始化本地仓库
Git init
2.上传修改的文件
git add *
3.commit 文件
git commit -m "test"
4.创建分支
git branch test
5.切换分支
git checkout test
6.关联远程分支
git remote add origin https://github.com/yangxiaoyan20/BowlingScore.git
7.push
git push origin test

修改后重新push
1、git add .
2、git commit -m “test”  （”test“为分支名）
3、git branch test（创建分支）
4、git checkout  test （切换分支）
5、git push origin test:test

commit，然后pull，然后再push

error：

1.fatal: refusing to merge unrelated histories
git pull origin master -–allow-unrelated-histories

【Robotics】机器人学导论

基础知识

基本部件：机械手、末端执行器、驱动器（肌肉）、传感器、控制器、处理器、软件

自由度

一般有6个自由度。3个用来确定 空间中的位置，3个用来确定姿态

坐标系

1、基坐标系（Base Coordinate System）
2、大地坐标系（World Coordinate System）
3、工具坐标系（Tool Coordinate System）
4、工件坐标系（Work Object Coordinate System）

位置运动学

1.n、o、a坐标轴

【OS】オペレーティングシステム復習

序論

オペレーティングシステムの目的:

Provide a environment in which a user can execute programs in a convenient and efficient manner
i.e ユーザー操作を易いになる

オペレーティングシステムって、何をする？

オペレーティングシステムは３つのコンポーネントを分けられます

• hardware
  CPU, I/O devices, memory
• operating system
• application software
• user

ユーザービュー(User view)

OS is designed mostly for ‘EASE OF USE’

システムビュー(System View)

【OS】FCFS,SJF,SRT

班级:软1708
姓名:黄万鸿
学号:201792015
算法选择:FCFS,SJF,SRT

[TOC]

运行结果展示

程序内部，使用时钟进行每次时间+1的模拟，为了简化输出，只输出重要的时间点（非每个单位时间都输出）

第一部分:FCFS

执行过程:

结果评估:

第二部分:SJF

执行过程:

结果评估:

第三部分:SRT

执行过程:

【NLP】Skip-gram

上图的Skip-gram的结构图
我们的目标是利用最左边的输入词向量(图里为shape=(100001))来训练隐藏层
隐藏层的结果是shape=(10000300)的矩阵。也就是词向量
于是$W_1$是大小为$(1,300)$的矩阵
如果我们一次输入多个词向量那就是
输入$(10000,n)大小,W_1’s\quad size=(n,300)$
中间层是线性的。不用激活函数，
于是经过$W_2$（也是词向量）到输出层得到结果。输出层结果为(10000,1)的大小。经过softmax后就得到分类概率

分析

假设输入的word pair为$（ants, able）$，则模型拟合的目标是 $Max P(able|ants)$ ,同时也需要满足 $Min P (other words 丨ants) $，这里利用的是对数似然函数作为目标函数。上述表述中$ P（able 丨ants）$ 可表示为：

根据$ P（able丨ants）$ 和 $P(other words丨ants) $，可构建似然函数:

对数化

模型优化

负采样 negative sample

负采样是加快训练速度的一种方法，这里的负可以理解为负样本。针对训练样本（ants, able），able这个词是正样本，词表中除able外的所有词都是负样本。负采样是对负样本进行采样，不进行负采样时，对每一个训练样本模型需要拟合一个正样本和九千九百九十九个负样本。加入负采样后，只需要从这九千九百九十九个负样本中挑出来几个进行拟合，大大节省了计算资源。那么应该挑几个负样本，根据什么进行挑呢？Google给出的建议是挑5-20个，怎么挑是根据词在语料中出现的概率，概率越大越有可能被选中，具体计算公式为：

其中f()表示出现的概率。

层次softmax

层次softmax的目的和负采样一样，也是为了加快训练速度，但它相对复杂，没有负采样这种来的简单粗暴。具体来说，使用层次softmax时图4中的模型输出层不再是使用one-hot加softmax回归，而是使用Huffman树加softmax回归。在模型训练的时候首先统计语料中词语的词频，然后根据词频来构建Huffman树，如图7所示，树的根节点可理解为输入词的词向量，叶子节点表示词表中的词，其它节点没有什么实际含义，仅起到辅助作用。

【NLP】LSA(Latent Semantic Analysis:潜在语义分析)

LSA是基于co-occurance matrix的

步骤

1.计算courpus中出现的词的集合
2.创建co-occurance matrix
3.计算co-occurance矩阵
4.SVD降维。得到词向量

【NLP】GloVe(Global Vectors for Word Representation)

Algorithm

• 1.Construct A co-occurance matrix $X$ according to corpus
  Commonly element $X_{i,j}$ in co-occurance matrix represent the time of word j appear in i’s context window.
  Generally,it’s minimun unit is 1.
  But GloVe don’t think so. It think the weight should decrease with distance.
  提出了一个衰减函数（decreasing weighting）：
  decay=1/d
  用于计算权重

• 构建词向量（Word Vector）和共现矩阵（Co-ocurrence Matrix）之间的近似关系，论文的作者提出以下的公式可以近似地表达两者之间的关系：

  $$w_i^Tw_j+b_i+b_j=log(X_{ij})$$

  

• loss function
  
  

• 训练
  

解释

首先GloVe是基于共现矩阵(co-occurrance Matrix)的
于是第一步也是需要先计算共现矩阵$X$
$X_{i,j}$表示词j在词i窗口内出现的次数
$X_i=\sum_j^NX_{i,j}$表示共现矩阵的某行和。也就是在窗口内出现词的总数
那么
$P_{i,k}=\frac{X_{i,k}}{X_i}$表示条件概率。也就是词$k$在词$i$上下文出现的概率
作者发现对于两个条件概率的比例
$ratio_{i,j,k}=\frac{P_{i,k}}{P_{j,k}}$
有

于是我们想到用一个函数$g(v_i,v_j,v_k)$（参数为3个词向量），去拟合$ration_{i,j,k}$。这样就能训练出词向量了。
代价函数可以这么写

..但是会发现复杂度是$O(N^3)$.需要想办法降低复杂度

我们要考虑词向量$v_i$,$v_j$的关系。所以$(v_i-v_j)^T$应该是个不错的选择
然后ratio是个标量。$g$的计算结果应该也是标量。那么$(v_i-v_j)^Tv_k$应该不错

然后套层exp就是我们要的函数g了$g(v_i,v_j,v_k)=exp[(v_i-v_j)^Tv_k]$
至于为什么要加exp是为了化简。
我们的目标是让$\frac{P_{i,k}}{P_{j,k}}$和$g(v_i,v_j,v_k)$尽可能接近。
那么由上式有$g=exp(v_i^Tv_k-v_j^Tv_k)$
那么有$P_{i,k}=exp(v_i^Tv_k)和P_{j,k}=exp(v_j^Tv_k)$
两边取对数就变成

那代价函数可以变成

【Cipher Theory】Elliptic Curve Cipher