clique是一个图中两两相邻的一个点集,或是一个完全子图.ppt

Efficient Unsupervised Discovery of Word Categories Using Symmetric Patterns and High Frequency Words Dmitry Davidov, Ari Rappoport The Hebrew University ACL 2006 Introduction Discovering word categories, sets of words sharing a significant aspect of their meaning context feature vectors pattern-based discovery Manually prepared pattern set (ex. x and y) requiring POS tagging or partial or full parsing Pattern Candidates high frequency word (HFW) A word appearing more than TH times per million words Ex. and, or, from, to … content word (CW) word appearing less than TC times per a million words Pattern Candidates meta-patterns obey the following constraints at most 4 words exactly two content words no two consecutive CWs Example CHC, CHCH, CHHC, and HCHC from x to y (HCHC), x and y (CHC), x and a y (CHHC) Symmetric Patterns In order to find a usable subset from pattern candidates, we focus on the symmetric patterns Example x belongs to y (asymmetric relationships) X and y (asymmetric relationships) Symmetric Patterns We use single pattern graph G(P) to identifying symmetric patterns there is a directed arc A(x, y) from node x to node y iff the words x and y both appear in an instance of the pattern P as its two CWs x precedes y in P SymG(P), the symmetric subgraph of G(P), containing only the bidirectional arcs and nodes of G(P) Symmetric Patterns We compute three measures on G(P) M1 counts the proportion of words that can appear in both slots of the pattern M2, M3 measures count the proportion of the number of symmetric nodes and edges in G(P) Symmetric Patterns We removed patterns that appear in the corpus less than TP times per million words We remove patterns that are not in the top ZT in any of the three lists We remove patterns that are in the bottom ZB in at least one of the lists Discovery of Categories words that are highly interconnected are good candidates to form a category word relationship graph G merging all of the single-pattern graphs