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
专用集成电路设计实用教程
IC设计经典教材，《专用集成电路设计实用教程》专用集成电路设计实用教程虞希清编著大學出瓶社图书在版编目(CIP)数据专用集成电路设计实用教程/虞希清编著.一杭州:浙江大学出版社,2007.1ISBN978-7-308-05113-2专..Ⅱ.虞..Ⅲ.集成电路一电路设计一高等学校一教材Ⅳ.TN402中国版本图书馆CIP数据核字(2006)第165341号专用集成电路设计实用教程虞希清编著任编辑张真封面设计张真出版发行浙江大学出版社(杭州天目山路148号邮政编码310028)(E-mail:zupress@mail,hz,zj.cn)(网址http://www.zjupress.com排版杭州好友排版工作室印刷杭州浙大同力教育彩印有限公司开本787mm×1092mm1/16印张18.25字数467千印数2001-3000版印次207年1月第1版2007年7月第2次印刷书号ISBN978-7-30805113-2定价38.00元版权所有翻印必究印装差错负责调换内容提要在现代的IC设计中,工程师们广泛地使用数字电路的逻辑综合技术。工程师们使用RTL代码和IP描述设计的功能,进行高级设计,用综合工具对设计进行编辑和优化,以实现满足设计目标的电路。根据多年为客户进行技术培训,技术支持和IC设计的经验,笔者编写了本书。书中主要介绍了IC设计的基本概念,设计流程和设计方法,并就工程师们在设计中常见的问题,提供了解决方法。本书的特点是实用性强全书共分九章,第一章概述EC设计的趋势和流程;第二章介绍用RTL代码进行电路的高级设计和数字电路的逻辑综合;第三章陈述了IC系统的层次化设计和模块划分;第四章详细地说明如何设置电路的设计目标和约束;第五章介绍综合库和静态时序分析;第六章深入地阐述了电路优化和优化策略;第七章陈述物理综合和简介逻辑综合的拓扑技术;第八章介绍可测性设计;第九章介绍低功耗设计和分析本书的主要对象是IC设计工程师,帮助他们解决IC设计和综合过程中遇到的实际问题。也可作为高等院校相关专业的高年级学生和研究生的参考书。前言本书在 Synopsys公司的逻辑综合培训资料基础上编写而成。从事EDA工作和ASIC设计已有十几年了。在给中港台ASIC设计工程师提供的技术培训和支持中,工程师们曾提出了设计和使用设计工具中遇到的各种各样的问题。教学相长,在和工程师讨论问题、提供解决方案的过程中,我得到了很多的经验和启发。在为用户解决一些实际问题,为他们提供培训后,我曾收到热情的掌声和感谢信。用户的掌声和谢意给了我很大的鼓励和鞭策,使我下决心要编写一本实用的中文版的集成电路设计教程和手册,以答谢用户们的支持和帮助。本书讲究实用性,希望其中的内容能帮助ASIC设计工程师清楚明了IC设计的基本概念,IC设计的流程,逻辑综合的基本概念和设计方法,解决进行IC设计时和工具使用时所遇到的问题。全书共分九章,第一章概述IC设计的趋势和流程;第二章介绍用RTL代码进行电路的高级设计和数字电路的逻辑综合;第三章陈述了IC系统的层次化设计和模块划分;第四章详细地说明如何设置电路的设计目标和约束;第五章介绍综合库和静态时序分析;第六章深入地阐述了电路的优化和优化策略;第七章陈述物理综合和简介逻辑综合的拓扑技术;第八章介绍可测性设计;第九章介绍低功耗设计和分析本书的主要对象是IC设计工程师,帮助他们解决IC设计和综合过程中遇到的实际问题。也可作为高等院校相关专业的高年级学生和研究生的参考书。在本书的编写过程中,得到了 Synopsys中国区高级技术经理常绍军先生的大力支持。常绍军先生、资深的应用技术顾问李昂先生和冯源先生审阅了本书,并提出了宝贵的意见和建议。在此,表示衷心的感谢。在本书编写过程中,得到了全家的支持,深表谢意!由于时间仓促,知识水平有限,书中难免有不足和错误之处,敬请各位专家,IC设计工程师和同行们批评指正,不胜感激。来函可发电子邮件( Email: victory_snps@ yahoo.com.hk)。虞希清2006年11月于 Synopsys香港目录第一章集成电路设计概论1.1摩尔定律………………∴…………11.2集成电路系统的组成1.3集成电路的设计流程第二章数字电路的高级设计和逻辑综合132.1RTL硬件描述语言设计132.1.1行为级硬件描述语言( Behavioral Level hdi)132.1.2寄存器传输级硬件描述语言( RTL HDI)172.1.3结构化硬件描述语言( Structure HDL)………………………………232逻辑综合(L。 gic Synthesis)…………………272.2.1逻辑综合的基本步骤…282.2.2综合工具 Design Compiler302.2.3目标库和初始环境设置鲁·自自音甲·是着音鲁备.··非曲●d■···●····第三章系统的层次化设计和模块划分353.1设计组成及 DC- Tcl…·自音···········日·········.···卡器日音是·晶自鲁bt·。……353.1.1设计物体( Design Object)鲁音自353.1.2 DC - Tcl简介香看·鲁·鲁·鲁.鲁自春3.2层次( Hierarchy)结构和模块划分( Partition)及修改463.2.1层次结构的概念463.2.2模块的划分…息鲁483.2.3模块划分的修改·看。51第四章电路的设计目标和约束…°。●看。面●554.1设计的时序约束…普·非鲁·鲁击曲■554.1.1同步( Synchronous)电路和异步( Asynchronous)电路…4.1.2亚稳态( Metastability)574.1.3单时钟同步设计的时序约束…血D。e574.1.4设计环境的约束724,1.5多时钟同步设计的时序约束…………794.1.6异步设计的时序约束832专用集成电路设计实用教程4.1.7保持时间( Hold Time)854.2复杂时序约束看香鲁e鲁曲鲁。自鲁自。a。自鲁自。鲁4.2.1多时钟周期( Multi-Cycle)的时序约束874.2.2门控时钟的约束904.2.3分频电路和多路传输电路的时钟约束鲁·看看看鲁924.3面积约束……………………………96第五章综合库和静态时序分析…985.1综合库和设计规则···········.······.··4·a·.·····◆···—985.1.1综合库……5.1.2设计规则1075.2静态时序分析5.2.1时序路径和分组1125.2.2时间路径的延迟1145.2.3时序报告和时序问题的诊断鲁·.···.·自击击合音。甲。。。●。。●……115第六章电路优化和优化策略…1206.1电路优化..···4····;··.·.·.·.·a·a·;··1226.1.1 Synopsys的知识产权库- Design Ware1236.1.2电路优化的三个阶段………………………1266.2优化策略…………1346.2.1编辑策略垂由d垂……1356.2.2自动芯片综合( Automated Chip Synthesis)………………………………1416.3网表的生成格式及后处理144第七章物理综合1487.1逻辑综合(L。 gic Synthesis)遇到的问题……………………1487.2物理综合( Physical Synthesis)的基本流程鲁鲁自谁…………………………1517.3逻辑综合的拓扑技术( Topographical Technology)…………162第八章可测试性设计…1748.1生产测试简介…………1748.2可测试性设计鲁D曹吾音·非·自·········着4鲁4鲁是1768.2.1物理瑕疵和故障模型1768.2.2D算法( D algorithm)1788.3测试协议( Test protocol)1858.4测试的设计规则·●鲁q鲁·音鲁鲁D鲁香曹音音音·自自··。·非鲁曲··●1908.4.1可测试性设计中的时钟信号1908.4.2三态总线和双向端口的测试。非……………………198录8.5门级网表可测试问题的自动修正2048.6扫描链的插入2088.7可测试设计的输出和流程2228.8自适应性扫描压缩技术………225第九章低功耗设计和分析2299.1工艺库的功耗模型…………2319.2功耗的分析…鲁鲁鲁……………2379.3低功耗电路的设计和优化2519.3.1门控时钟电路25293.2操作数分离………2619.3.3门级电路的功耗优化●·4·■D鲁曹春击自由2669.3.4多个供电电压( Multi-VDD)…2749.3.5电源门控………276参考文献……………………281第一章集应电路设计概记集成电路( Integrated Circuits)是现代电子设备的重要组成部分。因此,成功设计集成电路对整个电子信息技术产业的发展起到重要的作用。由于科技的发展,半导体芯片的集成化程度越来越高,设计的系统越来越复杂,规模越来越大,设计的性能越来越髙,功耗也越来越大,这些不断地给芯片设计工程师和电子设计自动化( Electronics Design Automation,简称EDA)厂商提出新的课题和挑战。1.1摩尔定律摩尔提出著名的“摩尔定律”已经40多年了。1965年4月,摩尔在《电子学( Electronics)》杂志上发表文章预言,半导体芯片上集成的晶体管数量将每年翻一番。1975年,他又提出修正说,芯片上集成的晶体管数量将每两年翻一番。晶体管数量MOORES LAWIntels Tanuma 2 Processo1000000000ante△nmtele Pentium Pr100000000Intels Pentium m Processoitels Pentium Pro10000000Intelstuma Printels*v Proces1000000Intel388 pre28610000080801000080084004●100019701975198019851990199520002005年度图1.1.1图1.1.1为在过去25年, ntel CPu中晶体管增长的情况。集成电路的规模不断地稳
- 2021-05-06下载
- 积分：1
