科学网

 找回密码
  注册
科学网 标签 ACL

tag 标签: ACL

相关帖子

版块 作者 回复/查看 最后发表

没有相关内容

相关日志

ACL2012正传
热度 1 gothere 2012-7-14 15:01
完整图文版见附件 ACL.pdf ACL 是一个传说,记得 2003 年黄昌宁先生到南师大讲学一周,说起微软亚洲研究院开创中国人在国际顶级计算语言学大会 ACL 上发表论文的贡献,我们无不佩服、向往,也开始了我们查阅 ACL 网站论文资料的习惯。 9 年过去了,缺粮少炮的我们,凭着一腔兴趣,勉强参加了每年的国内会议,从没有过出国的念想,只因为家贫、文科贫。终有机会在南大计算机系博士后,导师的支持加上申请到了足够的经费,可以去看一看了。冬季是 ACL 的 deadline ,而秋季学期教学特别繁重,每每想投稿,每每不成。于是乎,没有论文的我,在女儿诞生的第五天,就乘上了飞往济州岛的班机。 大会开幕式开宗明义:今年是 ACL 的 50 周年,借用孔子的名言“五十而知天命”。此番 ACL 的主旨比起平常,就多了一个要义:回顾与展望。回顾者乃一老休,饶有兴味地谈起他最初的研究兴趣、方法和教学心得。这么多年过去了,他仍然喜欢教学生用最原初的模型,以加强对问题的理解。 介绍了 1950s 末,他们开发的世界第一款句法分析器—— Uniparse ,基于有限状态机,可以分析出句子的名词短语、动词类别等基本信息。最后谈及了语言学和计算语言学的关系,虽然 20 多年来计算语言学家在很大程度上抛弃了语言学,但当处理的问题涉及语篇的时候,语言学该上场了。我们所要做的只是踮起脚尖,努力向上,摘下那颗属于自己的苹果。 走在大厅里,会议信息很丰富,百度作为本届大会最大的赞助商,获取了最醒目的位置和最大的展台。但不得不说,侧重单语的百度,在展台上空空如也,没有像样的 demo 或者展示,只是为了招纳海外军团归国吧。老外对于百度也没多大兴趣,这样的公司到底算不算竞争对手呢? Poster 展示厅很大,中间是即将开始的自助晚餐,趁着人少,抓拍了一张。 最佳论文被 NTT 拿去了。 最佳学生论文虽然是中国人的,仍是出自微软亚洲研究院。 这两个最佳都给了亚洲,难道也是 ACL 特别照顾了亚洲?两篇论文并不是具有重大意义或标志性建筑,有点晕乎,其实欧美的 paper 也不错啊。还好,真正的大奖是欧美的。不过这颁奖也出人意外得狠! 在 Skyp 网络直播中,我们看到 Fillmore 接过了 ACL Lifetime Award 。由于身体原因,老菲没法亲临现场。接下来,播放了他早先录制好的 40 分钟获奖感言。在这 40 分钟里,他回顾了自己的学术历程,从一个小伙子,目睹乔姆斯基带来的语言学革命。历经 10 年,从阿拉伯语、日语中获得灵感,创制了跨语言的格语法。有趣的是,他老婆是日本人,也给了他不少灵感吧:)可是他并没有止步不前,在格 case 和事件关系的矛盾中,以及 1970s Shank 的脚本理论等带来的思索,进一步提出了 Frame Semantics ,终成一个较为自足的语法体系。这位语言学家更令人敬佩之处在于,不像 Chomsky 只谈理论,他在退休后依然四处找资助,建成了 FrameNet 的数据库,给计算语言学带来了理论框架下的真实数据。这个奖给他,确实是实至名归。在现场直播问答环节中,他还饶有兴味地对比了自己和 WordNet 的相似处。这两个资源的建设者都是 ACL Lifetime Award 的获得者,只是 FrameNet 目前单语数据还不够完备,跨语言做的还不够好。说起来也巧,我们的背景是语言学多些的,听起来觉得特别过瘾,难得有这样的机会听听他的研究思路。也倍感国际学术交流的重要性,如果有机会出去学习就更棒了。可现场大多是计算机背景的,不少人打起了哈欠,看来复合型人才还是稀缺的。 Mark Johnson 做了第二个特邀报告,展望了一下 ACL 的未来。他的报告出人意料地哲理化。从技术进步的角度,谈到了计算语言学貌似不错的未来,而真正的危机在于这门学科过于技术化、工业化的倾向,会变得越来越狭隘。计算语言学对“科学”的贡献在哪里?他引用了 Box 和 Vapnik 的话,也谈到了目前脑神经研究的进展。引入了地图的演变史,隐喻地说出了他的观点,在科学和技术中,寻求结合点和创新力。 大会还专门设立了一整天 50 周年纪念的分会,大都是用文献统计方法和 LDA 等模型,自动得出文献、话题、年代分布,乏善可陈。有趣的是 Stanford 做的作者性别分布,以及男女代表学者的研究主题。 在各个分会场的报告中,仍然是欧美正牌名校的报告最吸引眼球。 Stanford 、 Berkeley 为代表,无论是老师还是博士生的报告,都让人为之一振,选题、工作、陈述都很漂亮。相形之下,亚洲(中国)学者论文也算不少了,但让人听起来费劲,在陈述准备上也明显没下足功夫,即使是一流的工作,也被三流的报告陈述拉下马了。 Demo Session ,和 Poster 的地点一致。这里我遇到了一个不曾想到又非见不可的人物—— Veale Tony ,英语明喻的研究者。我引用了七八次他的论文,做了汉语明喻抽取和中英对比工作,这次遇到,着实请教了一番,他听了我的工作,也较有兴趣。希望他不嫌弃,后面可以有实质性的合作。 有小女在家等着,顾不上听 EMNLP 啦,赶紧回家咯!
个人分类: Computational Linguistics|4942 次阅读|2 个评论
ACL2012见闻
gothere 2012-7-9 15:30
济州岛—所谓新的世界七大自然奇迹之地,迎来了2012年ACL大会。本届大会意义非凡,赶上ACL50年纪念,有一整天的大会来回顾历史展望未来。济州岛空气清新、天气多云、海水墨蓝、植被丰富,人口不多,路上车子也少。ACL的举办地在ICC(国际会议中心)。这次大会中国人并不甚多,白人仍是主力,韩国学者和学生明显增多。承办方花了很大力气,住宿安排、会标制作、餐饮会场、班车接送,做足了功课。接风宴上有韩国舞蹈,以及半立方大的冰雕的ACL纪念狮子,煞是惹眼。 第一天会议,昏昏欲睡,完全要归咎于会议方太狠,不让蹭tutorial,导致我们不得不出去逛逛景点(Hallasum),累得腿脚不灵,困乏不已。其二呢,也是程序委员会有点放水,full paper的质量有些下滑,讲者循规蹈矩,没有激情,听众自然躺倒一片。中国兵团(包括留学兵团)做了不少报告,北大的孙微微一个人连做了2个报告,也算开先河了吧。 晚上大佬Mark Johnson亲自做了long paper的poster,门庭若市。 (第二天见闻且待后文)
个人分类: Computational Linguistics|3336 次阅读|0 个评论
土耳其膝关节前交叉韧带损伤重建与康复的当前趋势
GaoXurenKnee 2011-6-24 18:03
土耳其伊斯坦布尔Yeditepe大学的Dilber Coşkunsu等于2010年的土耳其骨科与创伤学杂志(第44卷第6期)上撰文,介绍了土耳其膝关节前交叉韧带损伤重建与康复的当前趋势。 文中称:本研究为了归纳出当前土耳其骨科医师进行前交叉韧带重建的所采用的手术方法和康复步骤。然后将结果与国际前交叉韧带研究小组("ACL Study Group")的进行比较,看有什么区别。方法:作者制作了一个问卷。该问卷包含16个问题。这16个问题包括:手术方法、术前的要求、常规术后应用的手段、康复步骤以及术后重返运动等等的情况。这张问卷通过电子邮件被寄给了土耳其的55位年前交叉韧带手术量在25台以上的骨科医师。结果:39人(70.9%)回复了问卷调查。19名骨科医生(48.7%)常规仅开展腘绳肌重建前交叉韧带。4名骨科医生(10.3%)仅仅使用髌韧带。而有16名骨科医生(41%) 不光做腘绳肌重建前交叉韧带,也做髌韧带重建前交叉韧带。既做腘绳肌重建前交叉韧带,又做髌韧带重建前交叉韧带的16名骨科医生中有3名(18.8%)对两种方法重建前交叉韧带后采用不同的康复锻炼方法。研究结果表明,39名回复的骨科医生中,对腘绳肌重建前交叉韧带和髌韧带重建前交叉韧带后开始进行特殊活动的时间没有明显统计学差异(p0.05)。土耳其骨科医师的前交叉韧带损伤重建后的康复锻炼步骤和国际前交叉韧带研究小组("ACL Study Group")的数据相似。在术后使用支具和CPM机方面,土耳其骨科医师和国际前交叉韧带研究小组不同。土耳其骨科医师比国际前交叉韧带研究小组更普遍地应用支具和CPM机。结论:在土耳其,腘绳肌重建前交叉韧带和髌韧带重建前交叉韧带后的康复锻炼上有所区别。但总的来所,土耳其骨科医生在处理膝关节前交叉韧带损伤重建与康复上与国际前交叉韧带研究小组当前的理念基本相似。 Pubmed原文链接: http://www.ncbi.nlm.nih.gov/pubmed/21358252 Acta Orthop Traumatol Turc. 2010;44(6):458-63. doi: 10.3944/AOTT.2010.2388. Current trends in reconstruction surgery and rehabilitation of anterior cruciate ligament in Turkey. Coşkunsu D, Bayrakcı Tunay V, Akgün I. SourceYeditepe University Faculty of Health Sciences, Department of Physical Therapy and Rehabilitation, İstanbul, Turkey. 感悟:在我们的临床工作实践中,越来越多地可以见到膝关节前交叉韧带损伤重建的患者。我们是用腘绳肌重建前交叉韧带呢?还是做髌韧带重建前交叉韧带呢?对二者手术后的康复计划有何需要区别对待的么?我们中国目前的情况是什么样的呢?和国际前交叉韧带研究小组的认识有何相同和区别?这将是我们下一个课题研究的方向。国际前交叉韧带研究小组("ACL Study Group") www.aclstudygroup.com 成立于25年前,目前已经汇集了120余位来自世界各地的膝关节前交叉韧带专家,他们每两年举行一次聚会,一起更新对膝关节前交叉韧带的认识。2010年2月在泰国普吉岛举办了上一次的前交叉韧带研讨会。2012年2月将在美国怀俄明州最具西部风情的小镇-"杰克逊镇"举行下一次的前交叉韧带研讨会。期盼新的膝关节前交叉韧带研讨会能够给我们带来更新的、更实用、更可行的理念和技术。 ( 江苏省徐州医学院附属医院 骨科 膝关节研究与治疗中心 高绪仁 编译) 欢迎被膝关节问题困扰的患者朋友前来诊治 欢迎对膝关节感兴趣的医学生、医生前来见习、交流 高绪仁:每天以解决膝关节问题为乐:)
个人分类: 膝关节韧带损伤|5348 次阅读|0 个评论
肌音图(VMG)在运动医学中的应用: 前交叉韧带(ACL)康复检测
热度 2 sonosticschn 2011-2-20 16:54
受到前交叉韧带损伤的运动员,在返回运动场之前都要进行前交叉韧带重建。无论是前交叉韧带损伤还是前交叉韧带重建都会引起四头肌抑制现象和萎缩,需要康复训练来恢复。准确地测量肌肉对于运动员能否回到常规训练中是很重要地,然而传统的检测技术,比如等速肌力测量法在医学界就普遍不被接受,因为肌力测力法可对开链,单关节运动进行检测但无法应用于人类普遍的闭链运动模式。 肌音图 (VMG) 与肌力测量法相比有明显的优势,肌音图可准确地重复反映肌肉自主收缩所产生地力量, 肌音图可以瞬时检测出个体肌肉力量(比如, 拮抗肌对 )随时间的变化或左右的差别。我们在这里对一名年轻成年男性在前交叉韧带重建后的康复过程中检测其四头肌。 实验方法: 实验个体: 21 岁成年男性足球运动员,曾在右膝有过前交叉韧带损伤, 6 个月前进行了重建。 被检测肌肉: 股外侧肌和股二头肌 检测方法:将 BIOPAC 传导器附于左腿,被实验人员进行 10 次蹲起,蹲起间隔为 3 秒种。再对右腿进行同样实验。 分析: 分析其中 60 秒的数据 数据以 2000 赫兹的频率进行取样,然后使用肌音图过滤器将其转化为肌肉力量值。 数据经过低通滤波器( 0.2Hz )后,每次蹲起实验的中心点就是曲线的最高峰处。确定了中心点后,对前后各 2.5 秒的未经过滤波器的 10 组数据取平均值。 结果: 图一显示了左腿(未受伤腿)的数据,数据显示了典型的外侧肌在离心的收缩阶段(下蹲过程)中的主导作用,在向心阶段(站起)的很好的平衡作用。 有趣的是,左四头肌在休息阶段并没有停止,比肌腱肌肉在休息时期的活动水平高 2 倍以上。这显示被实验者在休息时在“保护”受伤的腿 。 图一: 即时显现的在运动中的未受伤腿的 股外侧肌和股二头肌的肌音图数据记录。 右腿(受伤腿)的数据显示显著的四头肌抑制现象,即使已经经过了 6 个月的康复时间。外侧肌的抑制现象在离心收缩期很明显,但是在同心收缩期股二头肌也明显地超过了股外侧肌。 图二: 即时显现的在运动中的受伤腿的 股外侧肌和股二头肌的肌音图数据记录 即使进行了 6 个月的康复期,外侧肌的四头肌抑制现象仍很显著 . 结论: 肌音图提供了一种简便的测量前交叉韧带损伤康复过程的技术手段。因为肌音图可以在闭链运动中使用。 肌音图提供了绝对并且可重复的肌肉力量检测方式,可以对个体的左右肌肉进行对比,也可以在个体在康复过程中的不同时间进行比较。并且,肌音图也许可以在赛季前对运动员进行检测,找出肌肉不平衡严重的运动员(容易发生拉伤),以便对他们进行加强训练来避免运动损伤。 更多关于肌音图的研究,请查看我们的网站: www.sonostics.com
4711 次阅读|2 个评论
[转载]CFP: 4th WORKSHOP ON BUILDING AND USING COMPARABLE CORPORA
timy 2010-12-22 16:44
4th WORKSHOP ON BUILDING AND USING COMPARABLE CORPORA Comparable Corpora and the Web Co-located with ACL-HLT 2011 Portland, Oregon 24 June 2011 DEADLINE FOR PAPERS: 1st April 2011 http://www.limsi.fr/~pz/bucc2011-comparable-corpora/ Submission: https://www.softconf.com/acl2011/comparable/ Endorsed by ACL SIGWAC (Special Interest Group on Web as Corpus) INVITED SPEAKER Kevin Knight, Information Sciences Institute, USC Putting a Value on Comparable Data ============================================================ MOTIVATION In the language engineering and the linguistics communities, research in comparable corpora has been motivated by two main reasons. In language engineering, it is chiefly motivated by the need to use comparable corpora as training data for statistical NLP applications such as statistical machine translation or cross-lingual retrieval. In linguistics, on the other hand, comparable corpora are of interest in themselves by making possible inter-linguistic discoveries and comparisons. It is generally accepted in both communities that comparable corpora are documents in one or several languages that are comparable in content and form in various degrees and dimensions. We believe that the linguistic definitions and observations related to comparable corpora can improve methods to mine such corpora for applications of statistical NLP. As such, it is of great interest to bring together builders and users of such corpora. Parallel corpora are a key resource as training data for statistical machine translation, and for building or extending bilingual lexicons and terminologies. However, beyond a few language pairs such as English-French or English-Chinese and a few contexts such as parliamentary debates or legal texts, they remain a scarce resource, despite the creation of automated methods to collect parallel corpora from the Web. Interest in non-parallel forms of comparable corpora in language engineering primarily ensued from the scarcity of parallel corpora. This has motivated research concerning the use of comparable corpora: pairs of monolingual corpora selected according to the same set of criteria, but in different languages or language varieties. Non-parallel yet comparable corpora overcome the two limitations of parallel corpora, since sources for original, monolingual texts are much more abundant than translated texts. However, because of their nature, mining translations in comparable corpora is much more challenging than in parallel corpora. What constitutes a good comparable corpus, for a given task or per se, also requires specific attention: while the definition of a parallel corpus is fairly straightforward, building a non-parallel corpus requires control over the selection of source texts in both languages. With the advent of online data, the potential for building and exploring comparable corpora is growing exponentially. Comparable documents in languages that are very different from each other pose special challenges as very often, the non-parallelness in sentences can result from cultural and political differences. TOPICS The theme of the workshop will be Comparable Corpora and the Web. Nevertheless we solicit contributions to other topics as well, including the following: Building Comparable Corpora: * Human translations * Automatic and semi-automatic methods * Methods to mine parallel and non-parallel corpora from the Web * Tools and criteria to evaluate the comparability of corpora * Parallel vs non-parallel corpora, monolingual corpora * Rare and minority languages * Across language families * Multi-media/multi-modal comparable corpora Applications of comparable corpora: * Human translations * Language learning * Cross-language information retrieval document categorization * Bilingual projections * Machine translation * Writing assistance Mining from Comparable Corpora: * Extraction of parallel segments or paraphrases from comparable corpora * Extraction of bilingual and multilingual translations of single words and multi-word expressions; proper names, named entities, etc. IMPORTANT DATES 1st April 2010 Deadline for submission 25 April 2011 Notification 6 May 2011 Final version 24 June 2011 Workshop SUBMISSION INFORMATION Submissions should follow the ACL HLT 2011 length and formatting requirements for long papers of six to eight (6--8) pages of content with two (2) additional pages of references, found at http://www.acl2011.org/call.shtml . They should be submitted as PDF documents to the following address: https://www.softconf.com/acl2011/comparable/ For further information, please contact Pierre Zweigenbaum pz(erase_at)limsi(erase_dot)fr ORGANISERS Pierre Zweigenbaum, LIMSI, CNRS, Orsay, and ERTIM, INALCO, Paris (France) Reinhard Rapp, Universities of Mainz (Germany) and Tarragona (Spain) Serge Sharoff, University of Leeds (UK) SCIENTIFIC COMMITTEE Srinivas Bangalore (ATT Labs, US) Caroline Barrire (National Research Council Canada) Chris Biemann (Microsoft / Powerset, San Francisco, US) Lynne Bowker (University of Ottawa, Canada) Herv Djean (Xerox Research Centre Europe, Grenoble, France) Kurt Eberle (Lingenio, Heidelberg, Germany) Andreas Eisele (European Commission, Luxembourg) Gregory Grefenstette (Exalead, Paris, France) Silvia Hansen-Schirra (University of Mainz, Germany) Kyo Kageura (University of Tokyo, Japan) Adam Kilgarriff (Lexical Computing Ltd, UK) Natalie Kbler (Universit Paris Diderot, France) Philippe Langlais (Universit de Montral, Canada) Tony McEnery (Lancaster University, UK) Emmanuel Morin (Universit de Nantes, France) Reinhard Rapp (University of Tarragona, Spain) Sujith Ravi (Information Sciences Institute, University of Southern California, US) Serge Sharoff (University of Leeds, UK) Michel Simard (National Research Council, Canada) Richard Sproat (OGI School of Science Technology, US) Dragos Stefan Munteanu (Language Weaver, Inc., US) Yujie Zhang (National Institute of Information and Communications Technology, Japan) Michael Zock (Laboratoire d'Informatique Fondamentale, CNRS, Marseille, France) Pierre Zweigenbaum (LIMSI-CNRS, France)
个人分类: 自然语言处理|2573 次阅读|0 个评论
Time automate
chaohelijuan 2010-11-6 15:15
最近在看一篇2010年的文章。文章的主要内容就是建立一个用于ACL的模型,其中对于Time-automate这内容不甚清楚,先把维基上的简单说明放下,呵呵,慢慢研究研究了! 自动机 维基百科,自由的百科全书 跳转到: 导航 , 搜索 在 理论计算机科学 中, 自动机 理论是对 抽象机 和它们能解决的问题的研究。自动机理论密切关联于 形式语言 理论,因为自动机经常按它们所能识别的 形式语言 类来分类。 目录 1 基本描述 2 术语 3 形式描述 4 有限自动机的分类 4.1 有限自动机的扩展 5 有限状态自动机的最小化 6 计算能力与判定问题 7 外部链接 8 引用 9 参见 // 基本描述 自动机是 有限状态机 (FSM)的数学模型。FSM 是给定符号输入,依据(可表达为一个表格的) 转移函数 跳转过一系列状态的一种机器。在常见的 FSM 的 Mealy 变体中,这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。 逐个读取输入中的符号,直到被完全耗尽(把它当作有一个字写在其上的磁带,通过自动机的读磁头来读取它;磁头在磁带上前行移动,一次读一个符号)。一旦输入被耗尽,自动机被称为停止了。 依赖自动机停止时的状态,称呼这个自动机要么是接受要么拒绝这个输入。如果停止于接受状态,则自动机接受了这个字。在另一方面,如果它停止于拒绝状态,则这个字被拒绝。自动机接受的所有字的集合被称为这个自动机接受的 语言 。 但要注意,自动机一般不必须有有限数目甚至 可数 个状态。比如, 量子有限自动机 有 不可数无限 个状态,因为所有可能状态的集合是在 复投影空间 中所有点的集合。所以,量子有限自动机和有限状态机一样,都是更一般想法 拓扑自动机 的特殊情况,它的状态的集合是 拓扑空间 ,而状态转移函数取自在这个空间上的所有可能函数。拓扑自动机经常叫做 M-自动机 ,简单是 半自动机 加上接受状态集合的补充,这里的集合交集确定初始状态是被接受还是被拒绝。 一般的说,自动机不需要严格的接受或拒绝一个输入;它可以按某个在零和一之间的 概率 接受它。还是用量子有限自动机作为展示例子,它只按某个概率接受输入。这个想法也是更一般情况 几何自动机 或 度量自动机 的特殊情况,它的状态的集合是 度量空间 ,一个语言被这个自动机接受如果在初始点和接受状态的集合之间的距离关于这个度量是足够的小。 术语 自动机有如下基本概念: 符号 有某种意义或在这个机器上有效的任意数据(datum)。符号有时就叫做字母。 字 通过一些符号 串接 而形成的有限 字符串 。 字母表 符号的有限集合。字母表经常指示为 ,它是在字母表中所有字母的 集合 。 语言 字的集合,由给顶字母表中的符号形成。可以是也可以不是无限的。 Kleene闭包 一个语言可以被认为是所有可能字的子集。所有可能字的集合可以被认为是所有可能的字符串串接的集合。形式上说,所有可能字符串的集合叫做 自由幺半群 。它被指示为 * ,上标 * 被称为 Kleene星号 。 形式描述 自动机 可以表示为 5-元组 ,这里的: Q 是 状态 的集合。 是符号的有限集合,我们称为这个自动机接受的语言的 字母表 。 是 转移函数 ,就是 。 (对于非确定自动机,空串是允许的输入)。 q 0 是 开始状态 ,就是说自动机在还未处理输入的时候的状态(明显的 q 0 Q)。 F 是叫做 接受状态 的 Q 中的状态的集合(就是 FQ)。 给定一个输入字母 ,可以使用简单的 currying 技巧写转移函数为 ,就是说,写 ( q , a ) = a ( q ) 对于所有 。这种方式下转移可以被更简单的看待: 它就是动作于 Q 中一个状态上的生成另一个状态的某种东西。你可以接着考虑重复的应用 函数复合 于各种函数 a , b 等等的结果。重复的函数复合形成一个 幺半群 。对于转移函数,这个幺半群叫做 转移幺半群 ,有时也叫做变换半群。 给定一对字母 ,可以通过坚持 定义一个新函数 ,这里的 指示函数复合。明显的,可以递归的继续这个过程,这样就有了为所有字 定义的函数 的递归定义,因此有了映射 这个构造也可以反过来: 给定 ,可以重新构造一个 ,因此两个描述是等价的。 三元组 被称为 半自动机 。半自动机位于自动机底下,它们就是忽略了开始状态和接受状态的自动机。开始状态和接受状态的补充概念允许自动机做半自动机不能做的事情: 它们可以识别 形式语言 。确定有限自动机 接受的语言 L 是: 就是说,一个自动机所接受的语言是在字母表 之上所有字 w 的集合,当给定为自动机的输入的时候,将导致它停止于 F 中的某个状态。被自动机接受的语言叫做 可识别语言 。 当状态集合 Q 是有限的时候,自动机被称为 有限状态自动机 ,而所有可识别的语言是 正则语言 。事实上,有一个强等价: 对于所有正则语言,都有一个有限状态自动机,反之亦然。 如上所述,集合 Q 不必须是有限或可数的;它可以采用一般的 拓扑空间 ;这就得到了一般的 拓扑自动机 。另一种可能的推广是 度量自动机 或几何自动机。在这种情况下,改变了对语言的接受: 替代在 中的最终状态的集合包含,以在最终状态 和集合 F 之间的 度量距离 的方式给出。特定类型的概率自动机是度量自动机,其度量空间是在 概率空间 上的 测量 。 有限自动机的分类 下面是三类有限自动机 确定有限自动机 (DFA) 对字母表中每个符号,自动机的状态都有且仅有一个转移。 DFA 非确定有限自动机 (NFA) 自动机的状态对字母表中的每个符号可以有也可以没有转移,对一个符号甚至可以有多个转移。自动机接受一个字,如果存在至少一个从 q 0 到 F 中标记(label)着这个输入字的一个状态的路径。如果一个转移是未定义的,自动机因此不知道如何继续读取输入,则拒绝这个字。 等价于前面例子 DFA 的 NFA 有转移的非确定有限自动机 (FND-或-NFA) 除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外,它们可以做根本不关于符号的跳转。就是说,如果一个状态有标记着 的转移,则 NFA 可以处在 -转移可到达的任何状态中,直接或通过其他有 -转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 -闭包。 尽管可以证明所有这些自动机都可以接受同样的语言。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。 有限自动机的扩展 上述自动机接受的语言家族被称为 正则语言 家族。更强力的自动机可以接受更复杂的语言。比如: 下推自动机 (PDA) 这种机器等同于 DFA (或 NFA),除了它们额外的装备了 栈 形式的 内存 。转移函数 也依赖于在栈顶的符号,并在每次转移时指定如何变更栈。非确定 PDA 接受 上下文无关语言 。 线性有界自动机 (LBA) LBA 是有限制的图灵机;不使用无限磁带,它的磁带有同输入字符串成正比的空间。LBA 接受 上下文有关语言 。 图灵机 它们是最强力的计算机器。它们拥有磁带形式的无限内存,和可以读取和变更磁带的磁头,它可在磁带上向任何方向移动。图灵机等价于算法,是现代计算机的理论基础。图灵机判定 递归语言 并识别 递归可枚举语言 。 有限状态自动机的最小化 根据 Myhill-Nerode定理 ,在同构意义下接受一个正则语言的最少状态的确定有限状态自动机是唯一的。同时我们还存在有效的算法(时间开销是O(n 2 )的)构造出与给定确定有限状态自动机等价的最小化的确定有限状态自动机。 计算能力与判定问题 确定有限状态自动机与非确定有限状态自动机识别的语言都是正则语言。由于正则语言的良好性质,许多为其他自动机( 下推自动机 或 图灵机 )不能判定的问题,在有限状态自动机的情形下,都可以得到判定,并且存在有效的算法。 对一个确定有限状态自动机,下述判定问题都可以判定,并且存在有效的算法。 该自动机识别的语言是否为空集。 该自动机识别的语言是否为有限集。 该自动机是否与另一个确定有限状态自动机识别同一个的语言。 外部链接 Visual Automata Simulator JFLAP Proyecto SEPa (in Spanish) Exorciser (in German) 引用 John E. Hopcroft , Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (2nd Edition) Michael Sipser . Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X . Part One: Automata and Languages, chapters 12, pp.29122. Section 4.1: Decidable Languages, pp.152159. Section 5.1: Undecidable Problems from Language Theory, pp.172183. 参见 自动机理论: 形式语言和形式文法 乔姆斯基层级 文法 语言 极小 自动机 类型 0 无限制 递归可枚举 图灵机 n/a (无公用名) 递归 判定器 类型 1 上下文有关 上下文有关 线性有界 n/a 附标 附标 嵌套堆栈 n/a 树-邻接 适度上下文有关 嵌入下推 类型 2 上下文无关 上下文无关 非确定下推 n/a 确定上下文无关 确定上下文无关 确定下推 类型 3 正则 正则 有限 每个语言或文法范畴都是其直接上面的范畴的 真子集 。 自动机(维基): http://zh.wikipedia.org/zh/%E8%87%AA%E5%8A%A8%E6%9C%BA
个人分类: 生活点滴|3605 次阅读|0 个评论
ACL short paper 被拒内容及感受
热度 1 zeroiszero 2010-4-22 17:04
ACLshort paper被拒,有点郁闷,本以为short paper本来就是考虑到是一个正在进行中的工作的前期部分,可能实验不会太完整,不过似乎我想错了,在文章中由于篇幅,没有将实验部分交待的很细致,实验也没有完全展开,本以为能对前面的基本假设做一个初步证明即可,结果3个评审倒是意见一致了: (1)the description of the experiment on Semeval 2007 needs more details. Its not clear how the training set expansion is done and the different systems are defined. This could be the more interesting part of the paper but is vaguely described in one paragraph and consequently difficult to understand. A comparison with the features used by other Semeval participants would help to understand the contribution of the proposed technique. (2)All in all, the results over ngrams are interesting, but the application to WSD needs more work. (3)It will be more interesting to see your comparison for several languages--- currently I find your results too limited for ACL. 当然,外语写作的问题再次暴露,虽然我找了个人帮我改过了。 The paper would really profit from an English native speaker for proof-reading. It is partially very hard to understand and some sentences just don't make much sense. Ths goes beyond the standard number of mistakes that are unavoidable for non-native speakers.
个人分类: 会议与期刊动态|9385 次阅读|0 个评论

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-5-19 23:43

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部