natural language toolkit tree transformations c 20052007 oregon graduate institute nathan bodenstab bodenstabcslu ogi edu url https www nltk org for license information see license txt from nltk internals import deprecated from nltk tree transforms import chomskynormalform as cnf from nltk tree transforms import collapseunary as cu from nltk tree transforms import unchomskynormalform as ucnf chomskynormalform deprecated import using from nltk tree import chomskynormalform instead cnf unchomskynormalform deprecated import using from nltk tree import unchomskynormalform instead ucnf collapseunary deprecated import using from nltk tree import collapseunary instead cu all chomskynormalform unchomskynormalform collapseunary natural language toolkit tree transformations c 2005 2007 oregon graduate institute nathan bodenstab bodenstab cslu ogi edu url https www nltk org for license information see license txt a collection of methods for tree grammar transformations used in parsing natural language although many of these methods are technically grammar transformations ie chomsky norm form when working with treebanks it is much more natural to visualize these modifications in a tree structure hence we will do all transformation directly to the tree itself transforming the tree directly also allows us to do parent annotation a grammar can then be simply induced from the modified tree the following is a short tutorial on the available transformations 1 chomsky normal form binarization it is well known that any grammar has a chomsky normal form cnf equivalent grammar where cnf is defined by every production having either two non terminals or one terminal on its right hand side when we have hierarchically structured data ie a treebank it is natural to view this in terms of productions where the root of every subtree is the head left hand side of the production and all of its children are the right hand side constituents in order to convert a tree into cnf we simply need to ensure that every subtree has either two subtrees as children binarization or one leaf node non terminal in order to binarize a subtree with more than two children we must introduce artificial nodes there are two popular methods to convert a tree into cnf left factoring and right factoring the following example demonstrates the difference between them example original right factored left factored a a a b c d b a c d or a b c d c d b c 2 parent annotation in addition to binarizing the tree there are two standard modifications to node labels we can do in the same traversal parent annotation and markov order n smoothing or sibling smoothing the purpose of parent annotation is to refine the probabilities of productions by adding a small amount of context with this simple addition a cyk inside outside dynamic programming chart parse can improve from 74 to 79 accuracy a natural generalization from parent annotation is to grandparent annotation and beyond the tradeoff becomes accuracy gain vs computational complexity we must also keep in mind data sparcity issues example original parent annotation a a b c d b a a c d where is the parent of a c a d a 3 markov order n smoothing markov smoothing combats data sparcity issues as well as decreasing computational requirements by limiting the number of children included in artificial nodes in practice most people use an order 2 grammar example original no smoothing markov order 1 markov order 2 etc __a__ a a a b c d e f b a c d e f b a c b a c d c c c annotation decisions can be thought about in the vertical direction parent grandparent etc and the horizontal direction number of siblings to keep parameters to the following functions specify these values for more information see dan klein and chris manning 2003 accurate unlexicalized parsing acl 03 https www aclweb org anthology p03 1054 4 unary collapsing collapse unary productions ie subtrees with a single child into a new non terminal tree node this is useful when working with algorithms that do not allow unary productions yet you do not wish to lose the parent information example a b a b c d c d
r

from nltk.internals import deprecated
from nltk.tree.transforms import chomsky_normal_form as cnf
from nltk.tree.transforms import collapse_unary as cu
from nltk.tree.transforms import un_chomsky_normal_form as ucnf

chomsky_normal_form = deprecated(
    "Import using `from nltk.tree import chomsky_normal_form` instead."
)(cnf)
un_chomsky_normal_form = deprecated(
    "Import using `from nltk.tree import un_chomsky_normal_form` instead."
)(ucnf)
collapse_unary = deprecated(
    "Import using `from nltk.tree import collapse_unary` instead."
)(cu)


__all__ = ["chomsky_normal_form", "un_chomsky_normal_form", "collapse_unary"]