NP难解问题是计算机算法和理论界长期研究的课题 .在求解 NP难解问题时 ,随机算法的性能往往很不稳定 .在以往的实验中 ,人们发现基于重启的优化方法可以提高 L as Vegas算法的性能和稳定性 .尽管它的思想比较直观 ,但对它的性能进行理...NP难解问题是计算机算法和理论界长期研究的课题 .在求解 NP难解问题时 ,随机算法的性能往往很不稳定 .在以往的实验中 ,人们发现基于重启的优化方法可以提高 L as Vegas算法的性能和稳定性 .尽管它的思想比较直观 ,但对它的性能进行理论分析却并不容易 ,这在很大程度上限制了其应用 .该文使用连续概率分布对算法性能分布建模 ,针对 L as Vegas算法提出了一种高效的重启策略构造方法 .该文从平均性能和稳定性两个角度分析了该方法的效率 ,同时通过将其应用于求解大规模旅行商问题 (TSP)展开更多
提出一种基于判别模型的拼写校正方法.它针对已有拼写校正系统Aspell的输出进行重排序,使用判别模型Ranking SVM来改进其性能.将现今较为成熟的拼写校正技术(包括编辑距离、基于字母的n元语法、发音相似度和噪音信道模型)以特征的形式...提出一种基于判别模型的拼写校正方法.它针对已有拼写校正系统Aspell的输出进行重排序,使用判别模型Ranking SVM来改进其性能.将现今较为成熟的拼写校正技术(包括编辑距离、基于字母的n元语法、发音相似度和噪音信道模型)以特征的形式整合到该模型中来,显著地提高了基准系统Aspell的初始排序质量,同时性能也超过了一些商用系统(如Microsoft Word 2003)的拼写校正模块.此外,还提出了一种在搜索引擎查询日志链中自动抽取拼写校正训练对的方法.基于这种方法训练的模型获得了基于人工标注数据所得结果相近的性能,它们分别将基准系统的错误率降低了32.2%和32.6%.展开更多
文摘NP难解问题是计算机算法和理论界长期研究的课题 .在求解 NP难解问题时 ,随机算法的性能往往很不稳定 .在以往的实验中 ,人们发现基于重启的优化方法可以提高 L as Vegas算法的性能和稳定性 .尽管它的思想比较直观 ,但对它的性能进行理论分析却并不容易 ,这在很大程度上限制了其应用 .该文使用连续概率分布对算法性能分布建模 ,针对 L as Vegas算法提出了一种高效的重启策略构造方法 .该文从平均性能和稳定性两个角度分析了该方法的效率 ,同时通过将其应用于求解大规模旅行商问题 (TSP)
基金Supported by the National Natural Science Foundation of China under Grant No.60603027 (国家自然科学基金)the Science-Technology Development Project of Tianjin of China under Grant No.04310941R (天津市科技发展计划)the Applied Basic Research Project of Tianjin of China under Grant No.05YFJMJC11700 (天津市应用基础研究计划)
文摘提出一种基于判别模型的拼写校正方法.它针对已有拼写校正系统Aspell的输出进行重排序,使用判别模型Ranking SVM来改进其性能.将现今较为成熟的拼写校正技术(包括编辑距离、基于字母的n元语法、发音相似度和噪音信道模型)以特征的形式整合到该模型中来,显著地提高了基准系统Aspell的初始排序质量,同时性能也超过了一些商用系统(如Microsoft Word 2003)的拼写校正模块.此外,还提出了一种在搜索引擎查询日志链中自动抽取拼写校正训练对的方法.基于这种方法训练的模型获得了基于人工标注数据所得结果相近的性能,它们分别将基准系统的错误率降低了32.2%和32.6%.
