Google word2vec算法 数学原理
文档是 word2vec 算法 数学原理详解。word2vec是google的一个开源工具，能够仅仅根据输入的词的集合计算出词与词直接的距离，既然距离知道了自然也就能聚类了，而且这个工具本身就自带了聚类功能，很是强大。32预备知识本节介绍word2v中将用到的一些重要知识点,包括 sigmoid函数、 Bccs公式和Huffman编码等821 sigmoid函数sigmoid函数是神经网络中常用的激活函数之一,其定义为1+e该函数的定义域为(-∞,+∞),值域为(0,1).图1给出了 sigmoid函数的图像0.56图1 sigmoid函数的图像sigmoid函数的导函数具有以下形式(x)=0(x)1-0(x)由此易得,函数loga(x)和log(1-0(x)的导函数分别为log a(a)-1 a(a),log(1 o(a))l-a(a),(2.1)公式(2.1)在后面的推导中将用到32.2逻辑回归生活中经常会碰到二分类问题,例如,某封电子邮件是否为垃圾邮件,某个客户是否为潜在客户,某次在线交易是否存在欺诈行为,等等设{(x;)}温1为一个二分类问题的样本数据,其中x∈Rn,∈{0,1},当v=1时称相应的样本为正例当v=0时称相应的样本为负例利用 sigmoid函数,对于任意样本x=(x1,x2,…,xn),可将二分类问题的 hypothesis函数写成h(x)=o(6o+b1x1+62+…+bnxn)其中θ=(0,61,…,On)为待定参数.为了符号上简化起见,引入x0=1将x扩展为(x0,x1,x2,……,xn),且在不引起混淆的情况下仍将其记为ⅹ.于是,he可简写为取阀值T=0.5,则二分类的判别公式为ho(x)≥0.5:X)=0,ha(x)6),可分别用000001、010、011、100、101对“A,E,R,T,F,D”进行编码发送,当对方接收报文时再按照三位一分进行译码显然编码的长度取决报文中不同字符的个数.若报文中可能出现26个不同字符,则固定编码长度为5(25=32>26).然而,传送报文时总是希望总长度尽可能短.在实际应用中各个字符的出现频度或使用次数是不相同的,如A、B、C的使用颗率远远高于X、Y、Z,自然会想到设计编码时,让使用频率高的用短码,使用频率低的用长码,以优化整个报文编码为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀),可用字符集中的每个字符作为叶子结点生成一棵编码二叉树,为了获得传送报文的最短长度,可将每个字符的岀现频率作为字符结点的权值赋于该结点上,显然字使用频率越小权值起小,权值越小叶子就越靠下,于是频率小编码长,频率高编码短,这样就保证了此树的最小带权路径长度,效果上就是传送报文的最短长度.因此,求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点,由字符出现频率作为其权值所产生的 Huffman树的问题.利用 Huffman树设计的二进制前缀编码,称为 Huffman编码,它既能满足前缀编码的条件,又能保证报文编码总长最短本文将介绍的word2ve工具中也将用到 Huffman编码,它把训练语料中的词当成叶子结点,其在语料中岀现的次数当作权值,通过构造相应的 Huffman树来对每一个词进行Huffman编码图3给岀了例2.1中六个词的 Huffman编码,其中约定(词频较大的)左孩子结点编码为1,(词频较小的)右孩子编码为0.这样一来,“我”、“喜欢”、“观看”、“巴西”、“足球”、“世界杯”这六个词的 Huffman编码分别为0,111,110,101,1001和100000欢观有巴西足球图3 Huffman编码示意图注意,到目前为止关于 Huffman树和 Huffman编码,有两个约定:(1)将权值大的结点作为左孩子结点,权值小的作为右孩子结点;(②)左孩子结点编码为1,右孩子结点编码为0.在word2vee源码中将权值较大的孩子结点编码为1,较小的孩子结点编码为θ.为亐上述约定统一起见,下文中提到的“左孩子结点”都是指权值较大的孩子结点3背景知识word2vec是用来生成词向量的工具,而词向量与语言模型有着密切的关系,为此,不妨先来了解一些语言模型方面的知识83.1统计语言模型当今的互联网迅猛发展,每天都在产生大量的文本、图片、语音和视频数据,要对这些数据进行处理并从中挖掘出有价值的信息,离不开自然语言处理( Nature Language processingNIP)技术,其中统计语言模型( Statistical language model)就是很重要的一环,它是所有NLP的基础,被广泛应用于语音识别、机器翻译、分词、词性标注和信息检索等任务例3.1在语音识别亲统中,对于给定的语音段Voie,需要找到一个使概率p(Tcrt| Voice最大的文本段Tert.利用 Bayes公式,有P(Teact Voice)p(VoiceTert)p(Text)P(Veonce其中p( Voice Teat)为声学模型,而p(Tert)为语言模型(l8])简单地说,统计语言模型是用来计算一个句子的概率的概率模型,它通常基于一个语料库来构建那什么叫做一个句子的概率呢?假设W=m1:=(n1,w2,…,tr)表示由T个词1,2,…,ur按顺序构成的一个句子,则n,U2,…,wr的联合概率p(W)=p(u1)=p(u1,u2,…,r)就是这个句子的概率.利用 Baves公式,上式可以被链式地分解为1)=p(u1)·p(u2l1)·p(vai)…p(ur1-)3.1其中的(条件)概率p(1),p(U2mn1),p(u3),…,p(urln1-1)就是语言模型的参数,若这些参数巳经全部算得,那么给定一个句子1,就可以很快地算出相应的p(1)了看起来妤像很简单,是吧?但是,具体实现起来还是有点麻烦.例如,先来看看模型参数的个数.刚才是考虑一个给定的长度为T的句子,就需要计算T个参数.不妨假设语料库对应词典D的大小(即词汇量)为N,那么,如果考虑长度为T的任意句子,理论上就有N种可能,而每种可能都要计算T个参数,总共就需要计算TN个参数.当然,这里只是简单估算,并没有考虑重复参数,但这个量级还是有蛮吓人.此外,这些概率计算好后,还得保存下来,因此,存储这些信息也需要很大的內存开销此外,这些参数如何计算呢?常见的方法有 II-gram模型、决策树、最大熵模型、最大熵马尔科夫模型、条件随杋场、神经网络等方法.本文只讨论n-gram模型和神经网络两种方法.首先来看看n-gram模型32n-gram模型考虑pko4-)(k>1)的近似计算.利用 Baves公式,有p(wr wi)P(uP(w根据大数定理,当语料库足够大时,p(k4-1)可近似地表示为P(wwi)count(wi)(3.2)count(a其中 count(u4)和 count-)分别表示词串t和v-在语料中出现的次数,可想而知,当k很大时, count(o4)和 count(4-1)的统计将会多么耗时从公式(3.1)可以看出:一个词出现的慨率与它前面的所有词都相关.如果假定一个词出现的概率只与它前面固定数目的词相关呢?这就是n-gran模型的基本思想,它作了一个n-1阶的 Markov假设,认为一个词出现的概率就只与它前面的n-1个词相关,即-1)≈p(kk-1+),于是,(3.2)就变成了p(wxJuk-)count(n+1countri(3.3以〃=2为例,就有p(uk4-1)≈count(k-1, Wk)count(Wk-1)这样一简化,不仅使得单个参数的统计变得更容易(统计时需要匹配的词串更短),也使得参数的总数变少了那么, n-gran中的参数n取多大比较合适呢?一般来说,n的选取需要同时考虑计算复杂度和模型效果两个因素表1模型参数数量与n的关系模型参数数量1( ingram)2×1052(bigram)4×10103( trigram)8×10154(4grm)16×10在计算复杂度方面,表1给出了n-gram模型中模型参数数量随着n的逐渐增大而变化的情况,其中假定词典大小N=2000(汉语的词汇量大致是这个量级).事实上,模型参数的量级是N的指数函数(O(N"),显然n不能取得太大,实际应用中最多的是采用n=3的三元模型在模型效果方面,理论上是π越大,效果越奷.现如今,互联网的海量数据以及机器性能的提升使得计算更高阶的语言模型(如n>10)成为可能,但需要注意的是,当n大到一定程度时,模型效果的提升幅度会变小.例如,当n从1到2,再从2到3时,模型的效果上升显著,而从3到4时,效果的提升就不显著了(具体可参考吴军在《数学之美》中的相关章节).事实上,这里还涉及到一个可靠性和可区别性的问题,参数越多,可区别性越好,但同时单个参数的实例变少从而降低了可靠性,因此需要在可靠性和可区别性之间进行折中另外, n-gran模型中还有一个叫做平滑化的重要环节.回到公式(3.3),考虑两个问题:若 count(uk-n+1)=0,能否认为p(kln1-1)就等于0呢?若 count(kn+)= count(uk-+1,能否认为p(uur-)就等于1呢?显然不能!但这是一个无法回避的问题,哪怕你的语料库有多么大.平滑化技术就是用来处理这个问题的,这里不展开讨论,具体可参考[11总结起来,n-gram模型是这样一种模型,其主要工作是在语料中统计各种词串岀现的次数以及平滑化处理.概率值计算好之后就存储起来,下次需要计算一个句子的概率时,只需找到相关的概率参数,将它们连乘起来就好了然而,在机器学习领域有一种通用的招数是这样的:对所考虑的问题建模后先为其构造一个目标函数,然后对这个目标函数进行优化,从而求得一组最优的参数,最后利用这组最优参数对应的模型来进行预測对于统计语言模型而言,利用最大似然,可把目标函数设为plwlConteat(w))∈C其中C表示语料( Corpus), Context(u)表示词U的上下文( Context),即周边的词的集合.当 Context(u)为空时,就取p( Context(w)=p(u).特别地,对于前面介绍的 n-gran模型,就有 Context(mn)=2-n+1注3.1语料￠和词典仍的区别:词典仍是从语料￠中抽取岀来的,不存在重复的词;而语料C是指所有的文本內容,包括重复的词当然,实际应用中常采用最大对数似然,即把目标函数设为∑ logp(u( ontext(o)(3.4)然后对这个函数进行最大化从(3.4)可见,概率p( CONtex()已被视为关于和 Context()的函数,即p(w Context(w))= F(w, Conteact(w), 0)
- 2020-06-14下载
- 积分：1
GMT0030-服务器密码机技术规范
GMT0030-服务器密码机技术规范，用于服务器密码机的开发与使用，国家统一标准规范。GM/T0030—20149.5环境适应性检测………119.6其他检测…………………………………………………………………………………1110合格判定……………………………………………………………………………11GM/T0030-2014前言本标准按照GB/T1.1—2009给出的规则起草请注意本文件的某些内容可能涉及专利。本文件的发布机构不承担识别这些专利的责任。本标准由密码行业标准化技术委员会提出并归口。本标准起草单位:山东得安信息技术有限公司、成都卫士通信息产业股份公司、无锡江南信息安全工程技术中心、兴唐通信科技有限公司、上海格尔软件股份有限公司海泰方圆科技有限公司。本标准主要起草人:刘平、孔凡玉、李元正、徐强、李玉峰、谭武征、柳增寿GM/T0030-2014服务器密码机技术规范1范围本标准定义了服务器密码机的相关术语,规定了服务器密码机功能要求、硬件要求、软件要求、安全性要求和检测要求等有关内容。本标准适用于服务器密码机的研制、使用,也可用于指导服务器密码机的检测2规范性引用文件下列文件对于本文件的应用是必不可少的。凡是注日期的引用文件,仅注日期的版本适用于本文件。凡是不注日期的引用文件,其最新版本(包括所有的修改单)适用于本文件GB/T9813微型计算机通用规范GM/T005随机性检测规范GM/T0018密码设备应用接口规范3术语和定义下列术语和定义适用于本文件服务器密码机 cryptographic server又称主机加密服务器,能独立或并行为多个应用实体提供密码服务和密钥管理的设备3.2对称密码算法 symmetric cryptographic algorithm加密和解密使用相同密钥的密码算法3.3非对称密码算法/公钥密码算法asymmetric cryptographic algorithm/public keycrytographic algorwth加密和解密使用不同密钥的密码算法。其中一个密钥(公钥)可以公开,另一个密钥(私钥)必须保密,且由公钥求解私钥是计算不可行的3.4密码杂凑算法cryptographic hash algorithm又称杂凑算法、密码散列算法或哈希算法。该算法将一个任意长的比特串映射到一个固定长的比特串,且满足下列三个特性:(1)为一个给定的输出找出能映射到该输出的一个输入是计算上困难的(2)为一个给定的输入找出能映射到同一个输出的另一个输入是计算上困难的;(3)要发现不同的输入映射到同一输出是计算上困难的。3.5公钥/私钥 public key/ private key非对称密码算法中可以公开的密钥称为公钥。非对称密码算法中只能由拥有者使用的不公开密钥GM/T0030-2014称为私钥。3.6加密/解密 encipherment/ encryption/ decipherment,/ decryption加密是对数据进行密码变换以产生密文的过程解密是加密过程对应的逆过程3.7数字签名/验证 digital signature/ verification签名者使用私钥对待签名数据的杂凑值做密码运算得到的结果,该结果只能用签名者的公钥进行验证,用于确认待签名数据的完整性、签名者身份的真实性和签名行为的抗抵赖性。验证是验证者使用签名者的公开密钥对数字签名进行验证的过程。3.8管理密钥 manager key用于保护服务器密码机中密钥和敏感信息安全的对称密钥3.9设备密钥 device key用于表明设备身份、对设备进行管理的非对称密钥对3.10用户密钥 user key存储在设备内部的用于应用密码运算的非对称密钥对,包含签名密钥对和加密密钥对3.11密钥加客密钥 key encryption key;KEK用于对密钥进行加密或解密的密钥。3.12会话密钥 session key在一次会话中使用的数据加密密钥。3.13私钥访问控制码 private key access passwor用于验证私钥使用权限的口令字3.14SM2算法SM2 algorithm一种椭圆曲线公钥密码算法,其密钥长度为256比特3.15SM3算法SM3 algorithm种密码杂凑算法,其输出为256比特3.16SM4算法SM4 algorithm一种分组密码算法,分组长度为128比特,密钥长度为128比特4缩略语下列缩略语适用于本文件。API:应用程序接口( Application Program Interface)CBC:(分组密码的)密码分组链接(工作方式)( Cipher Block Chaining)GM/T0030-—2014CFB:(分组密码的)密码反馈(工作方式)( Cipher Feedback)ECB:(分组密码的)电码本(工作方式)( Electronic codebook)OFB:(分组密码的)输出反馈(工作方式)( Output Feedback)5服务器密码机的功能要求5.1初始化服务器密码机的初始化主要包括密钥的生成(恢复)与安装生成管理员,按照安全机制对密钥进行安全存储和备份,使设备处于正常工作状态5.2密码运算服务器密码机应具有对称密码运算、公钥密码运算以及杂凑运算等密码运算功能,并且支持多任务并发访问。5.2.1对称密码算法服务器密码机必须至少支持SM4分组密码算法,包括电子密本(ECB)和密码分组链接(CBC)两种模式5.22公钥密码算法服务器密码机必须至少支持SM2公钥密码算法5.2.3密码杂凑算法服务器密码机必须至少支持SM3密码杂凑算法。5.3密钥管理5.3.1密钥管理功能服务器密码机应具有对所有密钥的产生、安装、存储、使用、销毁以及备份和恢复等功能。5.3.2密钥结构服务器密码机必须至少支持三层密钥结构:管理密钥、用户密钥/设备密钥/密钥加密密钥、会话密钥。如图1所示管理密钥用户密钥/设备密钥/密钥加密密钥等会话密钥图1密钥结构GM/T0030—2014管理密钥:用于保护服务器密码机中其他密钥和敏感信息的安全,包括对其他密钥的管理、备份、恢复等。不同服务器密码机的管理密钥互不相同。管理密钥必须安全存储。用广密钥:包括签名密钥对和加密密钥对,用于实现用户签名、验证、身份鉴别以及会话密钥的保护和协商等,代表用户或应用者的身份设备密钥:是服务器密码机的身份密钥,包括签名密钥对和加密密钥对,用于设备管理,代表服务器密码机的身份。密钥加密密钥:是定期更换的对称密钥,用于在预分配密钥情况下,对会话密钥的保护。服务器密码机可选择支持密钥加密密钥。会话密钥:用于数据加解密53.3密钥产生及安装管理密钥:由设备初始化时使用的管理工具生成或者安装,存储在服务器密码机内部的安全存储区域用户密钥:用户密钥分为签名密钥和加密密钥,答名密钥由服务器密码机生成或安装,必须支持使用物理噪声源芯片生成,必须支持使用强素数;加密密钥由密钥管理系统下发到设备中,加密密钥下发的格式遵循GM/T0018中对加密密钥的保护格式的规定,根据系统需要必须支持一定数量用户密钥对的存储区域;用户密钥对的私有密钥必须支持硬件内部安全存储,宜支持私钥访问控制码的安全访问控制。设备密钥:设备密钥分为签名密钥和加密密钥,签名密钥在设备初始化时使用管理工具生成或者安装,加密密钥由密钥管理系统下发到设备中,设备密钥存储服务器密码机内部的安全存储区域。密钥加密密钥:由密码设备管理工具生成或者安装,必须支持物理噪声源芯片生成;根据系统需要必须支持一定数量密钥加密密钥的存储区域;该密钥必须支持服务器密码机内部安全存储。会话密钥:必须支持使用物理噪声源芯片生成,以确保会话密钥的质量;必须支持一次会话更换次会话密钥;不得以明文方式导出服务器密码机;在会话密钥长期存储时,必须支持用户密钥对或者密钥加密密钥加密存储等安全保护措施。5.34密钥使用对称密钥:根据对称密钥索引号或其他密钥唯一标识,可使用内部对称密钥做运算,同时需满足对服务器密码机的运算操作权限。非对称密钥:根据非对称密钥索引号或其他密钥唯一标识,可使用内部对称密钥做运算,同时需满足对服务器密码机的运算操作权限;服务器密码机可配置是否使用私钥访问控制权限的机制,若使用私钥访问控制权限机制,在涉及签名和解密等使用内部私钥运算的操作时,应先验证该私钥的权限码是否正确。5.3.5密钥安全存储及销毁服务器密码机必须能够至少保存32对非对称密钥和100个对称密钥。服务器密码机中长期保存的密钥必须安全存储,可采用两种方式:一为采用加密存储,用于加密存储的密钥应由安全机制保证其安全,并提供对指定密钥的销毁功能;二可采用微电保护存储,应设计销毁密钥的触发装置。当触发装置被触发时,销毁微电保护所存储的所有密钥。采用微电保护的密钥可以不加密。536备份/恢复对长期保存的密钥,服务器密码机应具备备份/恢复功能。备份操作产生的备份文件必须以密文形GM/T0030—2014式存储到服务器密码机外的存储介质中,加密备份文件的密钥应有安全机制保证其安全。备份出的密钥可以恢复到服务器密码机中,同厂家的同型号的服务器密码机之间应能够互相备份恢复。密钥恢复操作只能在服务器密码机中进行。54随机数生成和检验服务器密码机应具备随机数生成功能。服务器密码机应能对生成的随机数进行随机性检验。随机数检验应符合GM/T0005的要求。5.5访问控制服务器密码机应具备管理界面,设置管理人员并赋予操作权限,通过管理界面进行密钥产生、安装备份和恢复以及日志査询等管理操作管理人员进入管理界面应进行身份鉴别。不同的管理操作应有不同的操作权限5.6设备管理服务器密码机宜具有接受管理中心的管理功能,设备管理功能的实现按照国家密码管理主管部门的要求进行。5.7日志审计服务器密码机应提供日志记录、查看和导出功能。日志内容包括:a)管理员操作行为,包括登录认证、系统配置、密钥管理等操作;b)异常事件,包括认证失败、非法访问等异常事件的记录;c)如与设备管理中心连接,则对相应操作进行记录5.8设备自检服务器密码机应具有上电时自检和接收自检指令时自检的功能设备自检功能应包括密码算法正确性检查、随机数发生器检査、存储密钥和数据的完整性检査等6服务器密码机的硬件要求6.1对外接口服务器密码机应分别提供服务接口和管理接口。支持目前主流服务器对外的RJ-45以太网接口、串口、光纤通道、USB等硬件接口协议,可以通过TCP/IP网络(100M/100M/10G)、USB或者其他接口形式与服务器和管理设备连接。6.2随机数发生器服务器密码机的随机数发生器应釆用国家密码管理主管部门批准的物理噪声源芯片,应提供多路随机源,至少采用两个独立的物理噪声源芯片实现随机数发生器应支持出厂检测、上电检测、使用检测三种检测方式a)出厂检测检测量:采集50×106比特随机数,分成50组,每组106比特;检测项目:依据GM/T0005进行检测;GM/T0030-2014检测通过标准:检测中如果有一项不通过检测标准,则告警检测不合格。允许重复1次随机数采集与检测,如果重复检测仍不合格,则判定为产品的随机数发生器失效。b)上电检测:检测量:采集20×10°比特随机数,分成20组,每组10°比特;检测项目:依据GM/T0005进行检测;检测通过标准:检测中如果有一项不通过检测标准,则告警检测不合格。允许重复1次随机数采集与检测,如果重复检测仍不合格,则判定为产品的随机数发生器失效c)使用检测:1)周期检测:检测量:釆集4×105比特随机数,分成20组,每组20000比特。检测项目:对采集随机数按照GM/T0005中除离散傅立叶检测、线性复杂度检测、通用统计检测外的12项项目检测。检测通过标准:检测中如果有一项不通过检测标准,则告警检测不合格。允许重复1次随机数采集与检测,如果重复检测仍不合格,则判定为产品的随机数发生器失效。·检测周期:可配置,检测间隔最长不超过12h。2)单次检测:检测量:根据实际应用时每次所采随机数大小确定,但长度不应小于128比特,且已通过检测的未用序列可继续用。检测项目:扑克检测。当样本长度小于320比特时,参数m=2检测通过标准:检测中如果不通过检测标准,则告警检测不合格。允许重复1次随机数采集与检测,如果重复检测仍不合格,则判定为产品的随机数发生器失效。6.3环境适应性服务器密码机的工作环境应根据实际需要遵循GB/T9813中关于“气候环境适应性”的规定要求。6.4可靠性服务器密码机的平均无故障工作时间应不低于10000h。7服务器密码机的软件要求7.1基本要求服务器密码机底层软件应采用模块化设计,应通过技术措施防止用户的非法调用。7.2应用编程接口服务器密码机的应用编程接口必须遵循GM/T0018。7.3管理工具服务器密码机应通过管理界面实现对该服务器密码机的管理功能管理工具可以安装服务器密码机上,也可以安装在服务器密码机之外的管理终端上。除管理工具对密码机进行管理,还可通过外部管理中心管理。
- 2020-12-09下载
- 积分：1
|
联系客服（QQ：3324461878）
