Parsing with probabilistic strictly locally testable tree languages

Probabilistic k-testable models (usually known as k-gram models in the case of strings) can be easily identified from samples and allow for smoothing techniques to deal with unseen events during pattern classification. In this paper, we introduce the family of stochastic k-testable tree languages and describe how these models can approximate any stochastic rational tree language. The model is applied to the task of learning a probabilistic k-testable model from a sample of parsed sentences. In particular, a parser for a natural language grammar that incorporates smoothing is shown.     

Parsing and translation of (attributed) expansive graph languages for scene analysis

In this paper, we suggest a class of (attributed) expansive graph grammars which generate languages contained in a graph family ?. It turns out that by means of node renumbering using a very effi-cient algorithm, any graph in ? can be converted into a standard form, which enables the use of related string representation for that graph to facilitate the syntax analysis. As a consequence, the syntax analysis of (attributed) expansive graph language is very efficient and almost like the parsing of tree languages. Furthermore, a syntax-directed transla-tion can be established for mapping one (attributed) expansive graph language to another. Finally, since many relational graphs for scene analysis can be considered as belonging to these graph languages, the proposed graph grammar model appears to be quite attractive from the application point of view.     

基于联合学习的成分句法与AMR语义分析方法

抽象语义表示(Abstract Meaning Representation,AMR)解析任务是从给定的文本中抽象出句子的语义特征,成分句法分析(Constituency Parsing)任务则探寻句子中的层次逻辑结构。由于AMR解析和成分句法分析之间存在着很强的互补性,抽象语义需要把握文本的句法结构,而句法分析可以通过理解句子中的语义信息来避免歧义,因此该文提出了一种联合训练方法用于捕获两个任务之间的内部联系从而提升各自任务的性能。此外,为了解决两个任务由于数据量过少造成的数据依赖问题,该文利用外部语料获得大规模自动标注 AMR 图以及自动标注句法树,并基于上述联合学习方法,采用预训练+微调的半监督学习方法进行训练。实验结果表明,该方法可以有效提高模型的性能,其中AMR解析任务在AMR 2.0上提升了8.73个F₁值,句法分析在PTB上获得了6.36个F₁值的提升。     

Fine-Grained Multi-human Parsing

Despite the noticeable progress in perceptual tasks like detection, instance segmentation and human parsing, computers still perform unsatisfactorily on visually understanding humans in crowded scenes, such as group behavior analysis, person re-identification, e-commerce, media editing, video surveillance, autonomous driving and virtual reality, etc. To perform well, models need to comprehensively perceive the semantic information and the differences between instances in a multi-human image, which is recently defined as the multi-human parsing task. In this paper, we first present a new large-scale database “Multi-human Parsing (MHP v2.0)” for algorithm development and evaluation to advance the research on understanding humans in crowded scenes. MHP v2.0 contains 25,403 elaborately annotated images with 58 fine-grained semantic category labels and 16 dense pose key point labels, involving 2–26 persons per image captured in real-world scenes from various viewpoints, poses, occlusion, interactions and background. We further propose a novel deep Nested Adversarial Network (NAN) model for multi-human parsing. NAN consists of three Generative Adversarial Network-like sub-nets, respectively performing semantic saliency prediction, instance-agnostic parsing and instance-aware clustering. These sub-nets form a nested structure and are carefully designed to learn jointly in an end-to-end way. NAN consistently outperforms existing state-of-the-art solutions on our MHP and several other datasets, including MHP v1.0, PASCAL-Person-Part and Buffy. NAN serves as a strong baseline to shed light on generic instance-level semantic part prediction and drive the future research on multi-human parsing. With the above innovations and contributions, we have organized the CVPR 2018 Workshop on Visual Understanding of Humans in Crowd Scene (VUHCS 2018) and the Fine-Grained Multi-human Parsing and Pose Estimation Challenge. These contributions together significantly benefit the community. Code and pre-trained models are available at https://github.com/ZhaoJ9014/Multi-Human-Parsing_MHP.

     

Story Parsing Grammar

Story understanding is one of the important branches of natural language understanding research in AI techniques.A new approach to story understanding is proposed in this paper.The so-called Story Parsing Grammar (SPG) is used to represent the story abstracting processes with different degrees in story understanding,and the story understanding process is converted to the storyn recognizing process done by the syntactic parser of SPG.This kind of story understanding is called story parsing.In this paper,firstly,a survey of story understanding research is given.Secondly,by the classification of various kinds of story structures,the so-called Case Frame Forest (CFF) is proposed to represent the superficial meaning of story.Based on CFF,a high-dimen-sional grammar,called Forest Grammar (FG),is defined.Furthermore,SPG is defined as a subclass of context-sensitive FG.Considering the context-sensitivity of story content,a type of context-sensitive derivation is defined in the definition of SPG.Lastly,data about runtime efficiency of the syntactic parsing algorithm of weak precedence SPG,a subclass of SPG,are given and analysed.     

Undirected Dependency Parsing

Dependency parsers, which are widely used in natural language processing tasks, employ a representation of syntax in which the structure of sentences is expressed in the form of directed links (dependencies) between their words. In this article, we introduce a new approach to transition‐based dependency parsing in which the parsing algorithm does not directly construct dependencies, but rather undirected links, which are then assigned a direction in a postprocessing step. We show that this alleviates error propagation, because undirected parsers do not need to observe the single‐head constraint, resulting in better accuracy. Undirected parsers can be obtained by transforming existing directed transition‐based parsers as long as they satisfy certain conditions. We apply this approach to obtain undirected variants of three different parsers (the Planar, 2‐Planar, and Covington algorithms) and perform experiments on several data sets from the CoNLL‐X shared tasks and on the Wall Street Journal portion of the Penn Treebank, showing that our approach is successful in reducing error propagation and produces improvements in parsing accuracy in most of the cases and achieving results competitive with state‐of‐the‐art transition‐based parsers.     

解析大数据

随着物联网的发展,大数据的处理无论是从量、还是从处理速度上都成为人们关注的焦点。从大数据的来源及数量、大数据类型、处理速度及方式3方面对大数据进行探讨,给出了大数据模型;分析了大数据的处理技术和策略。     

Scannerless Boolean Parsing

Scannerless generalized parsing techniques allow parsers to be derived directly from unified, declarative specifications. Unfortunately, in order to uniquely parse existing programming languages at the character level, disambiguation extensions beyond the usual context-free formalism are required.This paper explains how scannerless parsers for boolean grammars (context-free grammars extended with intersection and negation) can specify such languages unambiguously, and can also describe other interesting constructs such as indentation-based block structure.The sbp package implements this parsing technique and is publicly available as Java source code.     

Parsing in parallel

Application of parallel methods have become recently a general trend in information processing. We present a technique of parallel parsing of natural language which is based on distribution of elements of a sentence among a number of independent processors so that processing is carried out in parallel in multiple locations within a sentence. All the processors are identical, interchangeable and run the same software. An estimate of the time efficiency of this algorithm is given. The algorithm is suitable for parsing of ungrammatical and illformed sentences.     

合成目标化合物析分系统

在化学反应处理的计算模型的基础上,完成了一个实验性的目标化合物析分系统（Target Parsing System,TPS）。目前它主要用于测试和优化反应规则的选择和表述方法。TPS的工作逻辑基本上模仿人的思维过程,它通过对目标分子析分找出谋略键。根据谋略键将目标分子分拆成前体,再通过对原料库的检索确定是否已是可得原料等3个步骤完成反合成分析。通过对一些小分子和天然产物的测试,表明它已能给出令人满意的反合成分析结果。由于TPS在知识量上的局限性,对复杂化合物的析分还不可能达到实用水平。但是,可以预见通过对知识库的扩充和对TPS的不断完善,它有望发展成为一个真正意义上的计算机辅助合成设计系统。     

面向数据的句法分析消歧

面向数据的分析技术(Data-Oriented Parsing,DOP)是一种概率分析策略,其概率模型的主要目的在于为一个给定的句子找到最可能的分析,即分析消歧。实际上,有关算法计算复杂度的大量研究证明,该类消歧问题属于NP-完全问题。因此,为有效实现最可能的分析,国外学者提出许多近似分析算法。本文主要论述在 DOP 框架中,基于 Monte Carlo 方法找到最可能分析的近似分析算法,并说明该方法可在合理的算法时间代价范围内实现,而且在统计上受控,以确保所获得的近似解确实对应着分析消歧后的精确解。     

Image theorems for simple matrix languages andn-parallel languages

Three image theorems are proved for three families of languages in terms of prototype languages and (nondeterministic) generalized sequential machine maps. Further, for one family, then-right linear simple matrix languages of Ibarra, a new characterization theorem is proved.Work carried out under a National Research Council of Canada Grant No. A-7700.     

Rule-based languages

The paper presents a survey of the main formal rule-based languages and semantics. Both procedural (fixpoint) and declarative (model-theoretic) semantics are defined and discussed, including inflationary and noninflationary fixpoint semantics, and the semi-positive, stratified and well-founded semantics. The relative expressive power and com-plexity of the various languages are provided. Nondeterministic rule-based languages are also discussed, and it is shown how nondeterminism can circumvent some difficulties concerning the expressive power of the deterministic languages. Finally, languages with value invention (in the spirit of object-creation in oodbs) are presented and issues of expressive power specific to such languages are discussed.     

Multi-stack-counter languages

A stack-counter acceptor is a stack acceptor in which the storage alphabet is just one letter. The present paper discusses multi-stack-counter acceptors operating in quasirealtime, i.e., acceptors in which each storage tape is a stack counter and in which there are only a bounded number of consecutive-moves. For each positive integerk let be the family of languages accepted byk-stack-counter acceptors (k-counter acceptors). Each is a principal AFL closed under reversal but not under-free substitution or under intersection. Also, and a specific language in each, is exhibited. For each and there are noi andj such that. It is shown that a quasi-real-timek-stackcounter acceptor is equivalent to one operating in non-deterministic real time. Lastly, it is shown that acceptance by final state of ak-stack-counter acceptor is equivalent to acceptance by empty tape and final state.Also formerly with System Development Corporation, Santa Monica, California. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-70-C-0023; by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR No. F44620-70-C-0013; and by NSF Grant No. GJ454.     

VHD文件结构解析

VHD(Virtual Hard Disk)文件格式是一种重要的虚拟硬盘格式。通过对VHD文件格式的详细分析,论述了虚拟硬盘和VHD文件地址之间的映射关系,以及怎样在宿主文件系统上向不同类型的VHD文件中存储数据。并通过了解VHD的新版本VHDX,明了新版本通过在结构上的改进,提高了性能指标。最后,对VHD、VHDX文件格式在虚拟化应用的前景做出展望。