结构模式识别的概率文法及其应用

描述了概率文法的基本特性及其在铁路路轨探伤中的应用．文章首先给出了概率文法的定义，描述了它的树型结构，并为了得到非歧义的产生规则序列，对概率文法进行了修改，然后利用概率文法构造了模式识别器．介绍了应用于路轨探伤的识别程序的实现过程，并结合实例讨论了利用概率文法在提高识别器的可靠性。

使用概率规则文法评估人机界面可用性

提出一种在界面系统设计规约的基础上使用的可用性评估方法.首先使用有限状态自动机抽象界面系统设计,根据概率规则文法对有限状态自动机的状态转换概率进行预测;然后结合用户的熟练程度提出了界面可用性评估算法;最后讨论了一个手机界面的可用性计算实例.文中方法能够在界面系统生命周期的早期使用,以较早地对不同设计方案进行比较,降低开发风险.

一种基于概率上下文无关文法的汉语句法分析

本文研究了PCFG独立性假设的局限性,并针对这一局限性提出了句法结构共现的概念以引入上下文信息,给出了计算方法;为了打破中文树库规模过小的局限性,对于句法规则参数的获取,本文利用In-side-Outside算法进行迭代,最后提出了一个基于统计模型的自顶向下的汉语句法分析器。在封闭测试下,其标记精确率和标记召回率分别为88.1%和86.8%。实验结果表明,这种方法确实能够提高标记的精确率和召回率,值得深入研究。

应用概率LR文法分析器于语音识别系统

将概率ＬＲ文法分析器应用于语音识别系统中．模拟实验表明，系统使用该模型后识别性能优于使用二元文法模型的系统．其中。

基于概率上下文无关文法的句法分析歧义消解新模式

基于自然语言句法歧义消解常用的一种概率模型—概率上下文无关文法,融入上下文相关的概率信息,提出一种新的歧义消解计 算模式,该模式经测试可以有效地提高句法分析中歧义消解的正确率。

基于概率上下文无关文法的口令强度评估方法

口令作为当前互联网应用最主要的安全认证方式之一,口令的强弱决定着用户账户和系统的安全。文中针对目前常用的口令强度评估工具Passwordmeter等存在口令强度评估简单、参数较少等口令易遭受字典攻击等问题,利用信息熵进行口令强度的方法研究,提出一种新的口令强度评估方法。该方法采用概率上下文无关文法建模,对网络泄露的真实口令明文进行特征分析,通过口令的结构划分来计算其出现的概率,从而计算信息熵得出口令强度值,该方法计算代价较小,能够有效抵抗字典攻击。

基于内外概率算法的音乐节奏自动生成

针对计算机音乐领域中音乐自动生成问题,提出了一种将音乐关系的基本元素分开进行建模、分析、生成、融合的研究方法.基于音乐节奏本身具有可被形式化的特性,定义了一个概率上下文无关文法(PCFG)系统来描述相对独立的音乐节奏元素.该系统对实际音乐作品进行分析学习,将音乐节奏转化为形式化的文法语句.采用内外概率算法得到文法系统每条文法语句被使用的概率值,利用PCFG指导计算机生成新的音乐节奏,并构建了音乐节奏自动生成的原型系统.结果表明,该方法生成的音乐节奏与被分析的音乐节奏类似.

一种基于样本的模拟口令集生成算法

大规模的用户口令集因可用于评估口令猜测算法的效率、检测现有用户口令保护机制的缺陷等,而广受系统安全研究领域的重视.然而,尽管可以通过一些渠道,譬如网站口令泄露、用户自愿征集或者个别网站出于研究目的的共享等,获取真实的大规模用户明文口令对当前研究人员来说仍然非常困难.为应对上述问题,该文提出了一种基于样本的模拟口令集生成算法(Sample Perturbation Based Password Generation,SPPG).该算法利用较容易获得的小规模真实口令样本,通过学习生成概率模型,并产生大规模用户口令集合.为评估这一算法的效能,该文提出了一组模拟口令集质量的检测指标,包括真实口令覆盖率、Zipf分布拟合度等.最后,论文对比了SPPG算法与当前常见的用户口令猜测概率模型,包括概率上下文无关文法和多种马尔科夫模型,在生成用户口令集上的效能差异.结果显示,SPPG算法产生的模拟口令集在各指标下都有更好的表现.平均地,在真实口令覆盖率上,相对上下文无关文法和四阶马尔科夫模型分别提高了9.58%和72.79%,相对三阶和一阶马尔科夫模型分别提高了10.34倍和13.41倍,并且Zipf分布的拟合度保持在0.9及以上的水平.同时,其口令结构分布和特殊模式的使用也更符合真实用户生成口令的情况.

融合越南语语言特征与改进PCFG的越南语短语树库构建

短语树库是自然语言处理的研究和实际应用的重要资源,就越南语而言目前也缺乏这类树库资源,不利于汉越双语信息处理工作.提出一种融合越南语语法特征与改进PCFG(概率上下文无关文法)的越南语短语树库构建方法,能够自动分析出越南语的短语结构树,从而可解决了越南语短语树库的自动构建问题.首先通过分析越南语的语言特征,制定出越南语的语言特征集;然后利用Inside-Outside算法从人工标注的少量越南语短语树获取PCFG模型中的语法规则集;最后将语法特征集作为语法规则集的补充融入PCFG模型,用得到的新模型最终完成越南语短语树库的构建.实验结果表明,新的PCFG模型针对越南语短语树库构建的准确率达到了81.14%,相比传统PCFG模型以及基于最大熵的树库构建方法准确率明显提高了2%~3%.

参数化混合口令猜测方法

基于文本口令的认证方法仍是当前用户身份认证的主流方式.为更好地研究口令安全性,研究人员提出了多种数据驱动的口令猜测方法,如概率上下文无关文法(probabilistic context-free grammars,PCFG)和马尔可夫(Markov)方法等.这些方法在猜测口令时有其独特的猜测优势,即能够以更小的猜测数猜中特定类型的口令.为充分利用这些优势以实现更优的猜测效率,提出了一个通用的参数化混合猜测框架.该框架由模型剪枝方法和理论证明最优的猜测数分配策略构成,能够混合不同数据驱动方法的猜测优势以生成更高效的猜测集.为了验证框架的通用性和最优性,通过分析并混合现有数据驱动猜测方法的不同优势,基于该框架设计了多个混合多元模型的参数化混合猜测方法(统称为hyPassGu)用于猜测实践.并且,还利用从真实网站泄露的4个大规模口令数据集(总共超过1.5亿条口令)对这些混合猜测方法进行了评估实验.实验结果表明,由不同方法组合构建的hyPassGu均表现出超越单一方法的猜测效率,且在10^(10)猜测数下超越了单一方法最优效率的1.52%~35.49%.此外,不同猜测数下的对比实验结果表明,提出的最优分配策略的猜测表现稳定,优于平均分配策略和随机分配策略,并在分布离散程度最大的口令数据集上有16.87%的相对提升,同时更多元的混合方法整体上也表现出更好的猜测效率.

基于主题PCFG的口令猜测模型研究

口令是一种重要的身份认证方式,用户为了能够方便记住口令,常把一些与人相关的要素信息加入口令中。传统基于概率上下文无关文法(PCFG)算法进行的口令安全评估,并没有关注用户兴趣爱好、文化背景等与人相关的主题因素。文章基于传统PCFG算法,重点针对口令字母字段进行分析研究,通过对所收集的数据库字母字段的对比,提取用户口令与主题的关系,进而提出基于主题PCFG的口令猜测模型--T-PCFG模型。文章围绕收集的7个数据库中的3300万口令数据集进行实验,结果显示,主题为兴趣爱好时口令的猜测成功率比普通口令的猜测成功率高2.37-8.2个百分点。

EM算法在统计自然语言处理中的应用

在统计自然语言处理中会经常遇到一类参数估值问题,就是当观察数据为不完全数据时如何求解参数的最大似然估计,EM算法就是解决这类问题的经典算法。给出了EM算法的基本框架,结合HMM和PCFG模型给出如何应用EM算法求解参数的极大似然估计,讨论了EM算法的优点和不足之处。

使用角色反演句法分析器RNA二级结构的预测

RNA二级结构预测问题是生物信息学的一个研究重点。该文主要利用自然语言理解中句法分析的方法来研究RNA二级结构预测。使用基于角色反演算法建立起来的,采用概率上下文无关文法进行分析的句法分析器,来预测RNA二级结构。结合传统Chart算法分析器和广义LR算法分析器的优点,建立角色反演句法分析器;根据RNA二级结构的构建方法建立相应的概率上下文无关文法;给出对RNA二级结构进行预测的具体实例。

无监督的中文商品属性结构化方法

从非结构化商品描述文本中抽取结构化属性信息,对于电子商务实现商品的对比与推荐及用户需求预测等功能具有重要意义.现有结构化方法大多采用监督或半监督的分类方法抽取属性值与属性名,通过文法分析器分析属性值与属性名之间的文法依存关系,并根据关联规则实现属性值与属性名的匹配.这些方法存在以下不足:(1)需要人工标记部分属性值、属性名及它们之间的对应关系;(2)属性值-属性名匹配的准确度受到语言习惯、句意逻辑、语料库及属性名候选集质量的严重制约.提出了一种无监督的中文商品属性结构化方法.该方法借助搜索引擎,基于小概率事件原理分析文法关系来抽取属性值与属性名.同时,提出相对不选取条件概率场,并使用Page Rank算法来计算属性值与属性名的配对概率.该方法无需人工标记的开销,且无论商品描述中是否显式地包含相应的属性名,该方法都能自动抽取到属性值并匹配相应的属性名.使用百度搜索引擎上的真实语料,针对4类商品的中文描述进行了实验.实验结果验证了对于候选属性名的自动生成,所提出的基于搜索引擎搜索属性值,并在包含属性值的搜索结果中抽取一般名词的候选属性名生成方法与只在描述句中抽取一般名词的候选属性名生成方法相比,查全率提高了20%以上;对于非量化类属性,所提出的基于相对不选取条件概率场的属性值-属性名匹配方法与基于依存关联的方法相比,Rank-1的准确率提高了30%以上,平均MRR提高了0.3以上.

基于规则的模糊语句分析

针对当前常用的处理模糊语句的方法进行了分析,介绍了概率和规则相结合的消除模糊的方法:概率上下文无关文法,比较了几种方法的优缺点。

基于PChart算法的哈萨克语句法分析

为研究哈萨克语的句法分析,研究自然语言处理的统计方法的句法分析。根据概率上下无关文法模型和Chart算法的特点,将概率引入Chart算法,提出一种PChart算法。利用PChart算法对哈萨克语进行句法分析,解决句法分析中哈萨克文法的获取和歧义消解问题,实现一个基于PChart算法的哈萨克语句法分析器,识别正确的哈萨克语句子。实验结果表明,该分析器在准确率、召回率等方面的性能都有所提高。

基于PCFG模型的哈萨克语句法分析

为了实现哈萨克语的句法分析,研究概率上下无关文法,结合哈萨克语自身的语法特征得到哈萨克语的概率上下无关文法,获取哈萨克语PCFG参数,结合自底向下的Viterbi算法进行句法分析的歧义消除,进而实现一种有自学习能力的哈萨克语句法分析器,哈萨克语句子分析达到不错的效果。实验结果显示,PCFG模型可以适用于到哈萨克语的句法分析研究。

一种基于结构划分及字符串重组的口令攻击方法

身份认证是网络安全的一道重要防线,口令长期以来一直是身份认证的主流方式,口令攻击是口令安全研究的重要手段.基于概率上下文无关文法(Probabilistic Context-Free Grammar,PCFG)和基于Markov链的模型是目前效果最为显著的两类口令攻击方法,它们分别从子结构组成层面和字符前后依赖层面对口令进行有效地建模刻画.该文中,作者在综合上述两类模型优点的基础上提出了一种基于结构划分及字符串重组的口令攻击方法,记为SPSR模型:首先将口令划分成抽象的子结构,然后利用改进的Markov链模型生成子结构中字符、数字和符号等构成的子串,以同时兼顾模型的准确性和泛化能力.此外,作者在结构划分阶段还额外引入了常用字符段,并加入了索引位对特殊字符在口令中的位置进行了明确地刻画;在字符串重组阶段,通过递归的思想减少子串概率计算中的重复计算,给出了一个改进的OMEN算法——Recursive-OMEN算法.为了验证SPSR模型的有效性,分别在6个真实的中英文口令集上进行了实验测试.结果表明,按概率递减顺序生成相同规模的猜测口令集时,新提出的Recursive-OMEN算法比OMEN算法用时缩短了10倍左右;在相同的猜测次数下考察攻击效果时,SPSR模型比基于Markov链的模型能多破解出40%～50%的口令,比基于PCFG的模型能多破解出20%左右的口令.

基于改进PCFG算法的口令猜测方法

近年来口令泄露事件频出,有效的口令猜测方法是保障口令安全的重要手段,其中基于概率上下文无关文法(PCFG)的口令猜测方法效果尤为显著,然而仍存在无法生成新的口令字符子段、对生成口令的概率估计不准确等问题。以基于PCFG的口令猜测方法为研究对象,对其在口令构造过程中关键阶段的命中率进行分析,提出基于Backoff-RNN与概率平衡的改进PCFG口令猜测方法。在口令结构划分阶段,通过分析用户在构造口令时的行为与偏好,将口令从汉语拼音和英文单词两方面进行更细粒度的结构划分,提取口令更深层次的结构信息。在口令填充阶段,将Backoff思想应用于字符级RNN模型,生成子结构中长序列字符子段,提高模型准确性和泛化能力。在口令概率计算阶段,改进口令生成概率的计算方法,解决了使用传统计算规则时因口令结构长度不一致造成的概率不平衡问题。实验结果表明:在中英文两种语言环境交叉数据集上,该方法的漫步口令猜测攻击命中率相较于基于PCFG的口令猜测方法分别提升了20.6%和22.4%;在中文语言环境数据集上,定向口令攻击命中率相较于TarGuess-I模型提升了2.8%。

基于结构文法的机器人模仿学习方法

针对机器人模仿学习方法泛化性弱、对低级检测器准确率要求较高的问题,提出了一种基于结构文法的模仿学习方法.该方法通过视觉传感器提取场景的符号描述,形成含有噪声的符号基元序列;采用概率上下文无关文法(PCFG)对这些序列进行表征和语法操作,从而形成语法空间;基于最小描述长度(MDL)准则对语法空间中的语法质量进行评价,用改进的Beam Search算法寻找最优语法,即演示活动的一般结构;获得的一般结构能够将含有噪声的符号基元序列进行解析,得到正确的序列.数据合成实验和汉诺塔实验的对比效果验证了该方法优秀的数据表达性能和良好的抗干扰性能,在高噪声环境下该方法的解析成功率约为90%.