text: Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural
  Language Learning, pages 940?951, Jeju Island, Korea, 12?14 July 2012. c?2012 Association for Computational Linguistics
  Learning Syntactic Categories Using Paradigmatic Representations of
  Word Context
  Mehmet Ali Yatbaz Enis Sert Deniz Yuret
  Artificial Intelligence Laboratory
  Koc? University, I?stanbul, Turkey
  {myatbaz,esert,dyuret}@ku.edu.tr
  Abstract
  We investigate paradigmatic representations
  of word context in the domain of unsupervised
  syntactic category acquisition. Paradigmatic
  representations of word context are based on
  potential substitutes of a word in contrast to
  syntagmatic representations based on prop-
  erties of neighboring words. We compare
  a bigram based baseline model with several
  paradigmatic models and demonstrate signif-
  icant gains in accuracy. Our best model based
  on Euclidean co-occurrence embedding com-
  bines the paradigmatic context representation
  with morphological and orthographic features
  and achieves 80% many-to-one accuracy on a
  45-tag 1M word corpus.
  1 Introduction
  Grammar rules apply not to individual words (e.g.
  dog, eat) but to syntactic categories of words (e.g.
  noun, verb). Thus constructing syntactic categories
  (also known as lexical or part-of-speech categories)
  is one of the fundamental problems in language ac-
  quisition.
  Syntactic categories represent groups of words
  that can be substituted for one another without alter-
  ing the grammaticality of a sentence. Linguists iden-
  tify syntactic categories based on semantic, syntac-
  tic, and morphological properties of words. There is
  also evidence that children use prosodic and phono-
  logical features to bootstrap syntactic category ac-
  quisition (Ambridge and Lieven, 2011). However
  there is as yet no satisfactory computational model
  that can match human performance. Thus identify-
  ing the best set of features and best learning algo-
  rithms for syntactic category acquisition is still an
  open problem.
  Relationships between linguistic units can be
  classified into two types: syntagmatic (concerning
  positioning), and paradigmatic (concerning substitu-
  tion). Syntagmatic relations determine which units
  can combine to create larger groups and paradig-
  matic relations determine which units can be sub-
  stituted for one another. Figure 1 illustrates the
  paradigmatic vs syntagmatic axes for words in a
  simple sentence and their possible substitutes.
  In this study, we represent the paradigmatic axis
  directly by building substitute vectors for each word
  position in the text. The dimensions of a substi-
  tute vector represent words in the vocabulary, and
  the magnitudes represent the probability of occur-
  rence in the given position. Note that the substitute
  vector for a word position (e.g. the second word in
  Fig. 1) is a function of the context only (i.e. ?the
  cried?), and does not depend on the word that
  does actually appear there (i.e. ?man?). Thus substi-
  Figure 1: Syntagmatic vs. paradigmatic axes for words
  in a simple sentence (Chandler, 2007).
  940
  tute vectors represent individual word contexts, not
  word types. We refer to the use of features based on
  substitute vectors as paradigmatic representations of
  word context.
  Our preliminary experiments indicated that using
  context information alone without the identity or the
  features of the target word (e.g. using dimension-
  ality reduction and clustering on substitute vectors)
  has limited success and modeling the co-occurrence
  of word and context types is essential for inducing
  syntactic categories. In the models presented in this
  paper, we combine paradigmatic representations of
  word context with features of co-occurring words
  within the co-occurrence data embedding (CODE)
  framework (Globerson et al 2007; Maron et al
  2010). The resulting embeddings for word types are
  split into 45 clusters using k-means and the clusters
  are compared to the 45 gold tags in the 1M word
  Penn Treebank Wall Street Journal corpus (Mar-
  cus et al 1999). We obtain many-to-one accura-
  cies up to .7680 using only distributional informa-
  tion (the identity of the word and a representation of
  its context) and .8023 using morphological and or-
  thographic features of words improving the state-of-
  the-art in unsupervised part-of-speech tagging per-
  formance.
  The high probability substitutes reflect both se-
  mantic and syntactic properties of the context as
  seen in the example below (the numbers in paren-
  theses give substitute probabilities):
  ?Pierre Vinken, 61 years old, will join the
  board as a nonexecutive director Nov. 29.?
  the: its (.9011), the (.0981), a (.0006), . . .
  board: board (.4288), company (.2584),
  firm (.2024), bank (.0731), . . .
  Top substitutes for the word ?the? consist of
  words that can act as determiners. Top substitutes
  for ?board? are not only nouns, but specifically
  nouns compatible with the semantic context.
  This example illustrates two concerns inherent in
  all distributional methods: (i) words that are gener-
  ally substitutable like ?the? and ?its? are placed in
  separate categories (DT and PRP$) by the gold stan-
  dard, (ii) words that are generally not substitutable
  like ?do? and ?put? are placed in the same category
  (VB). Freudenthal et al(2005) point out that cat-
  egories with unsubstitutable words fail the standard
  linguistic definition of a syntactic category and chil-
  dren do not seem to make errors of substituting such
  words in utterances (e.g. ?What do you want?? vs.
  *?What put you want??). Whether gold standard
  part-of-speech tags or distributional categories are
  better suited to applications like parsing or machine
  translation can be best decided using extrinsic eval-
  uation. However in this study we follow previous
  work and evaluate our results by comparing them to
  gold standard part-of-speech tags.
  Section 2 gives a detailed review of related work.
  Section 3 describes the dataset and the construction
  of the substitute vectors. Section 4 describes co-
  occurrence data embedding, the learning algorithm
  used in our experiments. Section 5 describes our
  experiments and compares our results with previ-
  ous work. Section 6 gives a brief error analysis
  and Section 7 summarizes our contributions. All the
  data and the code to replicate the results given in
  this paper is available from the authors? website at
  http://goo.gl/RoqEh.
  2 Related Work
  There are several good reviews of algorithms
  for unsupervised part-of-speech induction
  (Christodoulopoulos et al 2010; Gao and Johnson,
  2008) and models of syntactic category acquisition
  (Ambridge and Lieven, 2011).
  This work is to be distinguished from supervised
  part-of-speech disambiguation systems, which use
  labeled training data (Church, 1988), unsupervised
  disambiguation systems, which use a dictionary of
  possible tags for each word (Merialdo, 1994), or
  prototype driven systems which use a small set
  of prototypes for each class (Haghighi and Klein,
  2006). The problem of induction is important for
  studying under-resourced languages that lack la-
  beled corpora and high quality dictionaries. It is also
  essential in modeling child language acquisition be-
  cause every child manages to induce syntactic cat-
  egories without access to labeled sentences, labeled
  prototypes, or dictionary constraints.
  Models of unsupervised part-of-speech induction
  fall into two broad groups based on the information
  they utilize. Distributional models only use word
  941
  types and their context statistics. Word-feature mod-
  els incorporate additional morphological and ortho-
  graphic features.
  2.1 Distributional models
  Distributional models can be further categorized into
  three subgroups based on the learning algorithm.
  The first subgroup represents each word type with its
  context vector and clusters these vectors accordingly
  (Schu?tze, 1995). Work in modeling child syntac-
  tic category acquisition has generally followed this
  clustering approach (Redington et al 1998; Mintz,
  2003). The second subgroup consists of proba-
  bilistic models based on the Hidden Markov Model
  (HMM) framework (Brown et al 1992). A third
  group of algorithms constructs a low dimensional
  representation of the data that represents the empir-
  ical co-occurrence statistics of word types (Glober-
  son et al 2007), which is covered in more detail in
  Section 4.
  Clustering: Clustering based methods represent
  context using neighboring words, typically a sin-
  gle word on the left and a single word on the right
  called a ?frame? (e.g., the dog is; the cat is). They
  cluster word types rather than word tokens based on
  the frames they occupy thus employing one-tag-per-
  word assumption from the beginning (with the ex-
  ception of some methods in (Schu?tze, 1995)). They
  may suffer from data sparsity caused by infrequent
  words and infrequent contexts. The solutions sug-
  gested either restrict the set of words and set of con-
  texts to be clustered to the most frequently observed,
  or use dimensionality reduction. Redington et al
  (1998) define context similarity based on the num-
  ber of common frames bypassing the data sparsity
  problem but achieve mediocre results. Mintz (2003)
  only uses the most frequent 45 frames and Biemann
  (2006) clusters the most frequent 10,000 words us-
  ing contexts formed from the most frequent 150-200
  words. Schu?tze (1995) and Lamar et al(2010b)
  employ SVD to enhance similarity between less fre-
  quently observed words and contexts. Lamar et al
  (2010a) represent each context by the currently as-
  signed left and right tag (which eliminates data spar-
  sity) and cluster word types using a soft k-means
  style iterative algorithm. They report the best clus-
  tering result to date of .708 many-to-one accuracy
  on a 45-tag 1M word corpus.
  HMMs: The prototypical bitag HMM model max-
  imizes the likelihood of the corpus w1 . . . wn
  expressed as P (w1|c1)
  ?n
  i=2 P (wi|ci)P (ci|ci?1)
  where wi are the word tokens and ci are their (hid-
  den) tags. One problem with such a model is its ten-
  dency to distribute probabilities equally and the re-
  sulting inability to model highly skewed word-tag
  distributions observed in hand-labeled data (John-
  son, 2007). To favor sparse word-tag distributions
  one can enforce a strict one-tag-per-word solution
  (Brown et al 1992; Clark, 2003), use sparse pri-
  ors in a Bayesian setting (Goldwater and Griffiths,
  2007; Johnson, 2007), or use posterior regulariza-
  tion (Ganchev et al 2010). Each of these techniques
  provide significant improvements over the standard
  HMM model: for example Gao and Johnson (2008)
  show that sparse priors can gain from 4% (.62 to .66
  with a 1M word corpus) in cross-validated many-
  to-one accuracy. However Christodoulopoulos et al
  (2010) show that the older one-tag-per-word models
  such as (Brown et al 1992) outperform the more
  sophisticated sparse prior and posterior regulariza-
  tion methods both in speed and accuracy (the Brown
  model gets .68 many-to-one accuracy with a 1M
  word corpus). Given that close to 95% of the word
  occurrences in human labeled data are tagged with
  their most frequent part of speech (Lee et al 2010),
  this is probably not surprising; one-tag-per-word is
  a fairly good first approximation for induction.
  2.2 Word-feature models
  One problem with the algorithms in the previous
  section is the poverty of their input features. Of the
  syntactic, semantic, and morphological information
  linguists claim underlie syntactic categories, con-
  text vectors or bitag HMMs only represent limited
  syntactic information in their input. Experiments
  incorporating morphological and orthographic fea-
  tures into HMM based models demonstrate signifi-
  cant improvements. (Clark, 2003; Berg-Kirkpatrick
  and Klein, 2010; Blunsom and Cohn, 2011) incor-
  porate similar orthographic features and report im-
  provements of 3, 7, and 10% respectively over the
  baseline Brown model. Christodoulopoulos et al
  (2010) use prototype based features as described in
  (Haghighi and Klein, 2006) with automatically in-
  942
  duced prototypes and report an 8% improvement
  over the baseline Brown model. Christodoulopou-
  los et al(2011) define a type-based Bayesian multi-
  nomial mixture model in which each word instance
  is generated from the corresponding word type mix-
  ture component and word contexts are represented
  as features. They achieve a .728 MTO score by ex-
  tending their model with additional morphological
  and alignment features gathered from parallel cor-
  pora. To our knowledge, nobody has yet tried to
  incorporate phonological or prosodic features in a
  computational model for syntactic category acquisi-
  tion.
  2.3 Paradigmatic representations
  Sahlgren (2006) gives a detailed analysis of paradig-
  matic and syntagmatic relations in the context of
  word-space models used to represent word mean-
  ing. Sahlgren?s paradigmatic model represents word
  types using co-occurrence counts of their frequent
  neighbors, in contrast to his syntagmatic model that
  represents word types using counts of contexts (doc-
  uments, sentences) they occur in. Our substitute
  vectors do not represent word types at all, but con-
  texts of word tokens using probabilities of likely sub-
  stitutes. Sahlgren finds that in word-spaces built by
  frequent neighbor vectors, more nearest neighbors
  share the same part-of-speech compared to word-
  spaces built by context vectors. We find that rep-
  resenting the paradigmatic axis more directly using
  substitute vectors rather than frequent neighbors im-
  prove part-of-speech induction.
  Our paradigmatic representation is also related to
  the second order co-occurrences used in (Schu?tze,
  1995). Schu?tze concatenates the left and right con-
  text vectors for the target word type with the left con-
  text vector of the right neighbor and the right con-
  text vector of the left neighbor. The vectors from the
  neighbors include potential substitutes. Our method
  improves on his foundation by using a 4-gram lan-
  guage model rather than bigram statistics, using the
  whole 78,498 word vocabulary rather than the most
  frequent 250 words. More importantly, rather than
  simply concatenating vectors that represent the tar-
  get word with vectors that represent the context we
  use S-CODE to model their co-occurrence statistics.
  2.4 Evaluation
  We report many-to-one and V-measure scores for
  our experiments as suggested in (Christodoulopou-
  los et al 2010). The many-to-one (MTO) evaluation
  maps each cluster to its most frequent gold tag and
  reports the percentage of correctly tagged instances.
  The MTO score naturally gets higher with increas-
  ing number of clusters but it is an intuitive met-
  ric when comparing results with the same number
  of clusters. The V-measure (VM) (Rosenberg and
  Hirschberg, 2007) is an information theoretic met-
  ric that reports the harmonic mean of homogeneity
  (each cluster should contain only instances of a sin-
  gle class) and completeness (all instances of a class
  should be members of the same cluster). In Sec-
  tion 6 we argue that homogeneity is perhaps more
  important in part-of-speech induction and suggest
  MTO with a fixed number of clusters as a more in-
  tuitive metric.
  3 Substitute Vectors
  In this study, we predict the part of speech of a word
  in a given context based on its substitute vector. The
  dimensions of the substitute vector represent words
  in the vocabulary, and the entries in the substitute
  vector represent the probability of those words be-
  ing used in the given context. Note that the substi-
  tute vector is a function of the context only and is
  indifferent to the target word. This section details
  the choice of the data set, the vocabulary and the es-
  timation of substitute vector probabilities.
  The Wall Street Journal Section of the Penn Tree-
  bank (Marcus et al 1999) was used as the test cor-
  pus (1,173,766 tokens, 49,206 types). The tree-
  bank uses 45 part-of-speech tags which is the set we
  used as the gold standard for comparison in our ex-
  periments. To compute substitute probabilities we
  trained a language model using approximately 126
  million tokens of Wall Street Journal data (1987-
  1994) extracted from CSR-III Text (Graff et al
  1995) (we excluded the test corpus). We used
  SRILM (Stolcke, 2002) to build a 4-gram language
  model with Kneser-Ney discounting. Words that
  were observed less than 20 times in the language
  model training data were replaced by UNK tags,
  which gave us a vocabulary size of 78,498. The per-
  plexity of the 4-gram language model on the test cor-
  943
  pus is 96.
  It is best to use both left and right context when
  estimating the probabilities for potential lexical sub-
  stitutes. For example, in ?He lived in San Francisco
  suburbs.?, the token San would be difficult to guess
  from the left context but it is almost certain look-
  ing at the right context. We define cw as the 2n ? 1
  word window centered around the target word posi-
  tion: w?n+1 . . . w0 . . . wn?1 (n = 4 is the n-gram
  order). The probability of a substitute word w in a
  given context cw can be estimated as:
  P (w0 = w|cw) ? P (w?n+1 . . . w0 . . . wn?1)(1)
  = P (w?n+1)P (w?n+2|w?n+1)
  . . . P (wn?1|w
  n?2
  ?n+1) (2)
  ? P (w0|w
  ?1
  ?n+1)P (w1|w
  0
  ?n+2)
  . . . P (wn?1|w
  n?2
  0 ) (3)
  where wji represents the sequence of words
  wiwi+1 . . . wj . In Equation 1, P (w|cw) is pro-
  portional to P (w?n+1 . . . w0 . . . wn+1) because the
  words of the context are fixed. Terms without w0
  are identical for each substitute in Equation 2 there-
  fore they have been dropped in Equation 3. Finally,
  because of the Markov property of n-gram language
  model, only the closest n ? 1 words are used in the
  experiments.
  Near the sentence boundaries the appropriate
  terms were truncated in Equation 3. Specifically, at
  the beginning of the sentence shorter n-gram con-
  texts were used and at the end of the sentence terms
  beyond the end-of-sentence token were dropped.
  For computational efficiency only the top 100
  substitutes and their unnormalized probabilities
  were computed for each of the 1,173,766 positions
  in the test set1. The probability vectors for each po-
  sition were normalized to add up to 1.0 giving us the
  final substitute vectors used in the rest of this study.
  1The substitutes with unnormalized log probabilities can be
  downloaded from http://goo.gl/jzKH0. For a descrip-
  tion of the FASTSUBS algorithm used to generate the substitutes
  please see http://arxiv.org/abs/1205.5407v1.
  FASTSUBS accomplishes this task in about 5 hours, a naive
  algorithm that looks at the whole vocabulary would take more
  than 6 days on a typical 2012 workstation.
  4 Co-occurrence Data Embedding
  The general strategy we follow for unsupervised
  syntactic category acquisition is to combine features
  of the context with the identity and features of the
  target word. Our preliminary experiments indicated
  that using the context information alone (e.g. clus-
  tering substitute vectors) without the target word
  identity and features had limited success.2 It is the
  co-occurrence of a target word with a particular type
  of context that best predicts the syntactic category.
  In this section we review the unsupervised meth-
  ods we used to model co-occurrence statistics: the
  Co-occurrence Data Embedding (CODE) method
  (Globerson et al 2007) and its spherical extension
  (S-CODE) introduced by (Maron et al 2010).
  Let X and Y be two categorical variables with fi-
  nite cardinalities |X| and |Y |. We observe a set of
  pairs {xi, yi}ni=1 drawn IID from the joint distribu-
  tion of X and Y . The basic idea behind CODE and
  related methods is to represent (embed) each value
  of X and each value of Y as points in a common
  low dimensional Euclidean space Rd such that val-
  ues that frequently co-occur lie close to each other.
  There are several ways to formalize the relationship
  between the distances and co-occurrence statistics,
  in this paper we use the following:
  p(x, y) =
  1
  Z
  p?(x)p?(y)e?d
  2
  x,y (4)
  where d2x,y is the squared distance between the em-
  beddings of x and y, p?(x) and p?(y) are empirical
  probabilities, and Z =
  ?
  x,y p?(x)p?(y)e
  ?d2x,y is a
  normalization term. If we use the notation ?x for
  the point corresponding to x and ?y for the point
  corresponding to y then d2x,y = ??x ? ?y?
  2. The
  log-likelihood of a given embedding `(?, ?) can be
  2A 10-nearest-neighbor supervised baseline using cosine
  distance between substitute vectors gives .7213 accuracy. Clus-
  tering substitute vectors using various distance metrics and di-
  mensionality reduction methods give results inferior to this up-
  per bound.
  944
  expressed as:
  `(?, ?) =
  ?
  x,y
  p?(x, y) log p(x, y) (5)
  =
  ?
  x,y
  p?(x, y)(? logZ + log p?(x)p?(y)? d2x,y)
  = ? logZ + const ?
  ?
  x,y
  p?(x, y)d2x,y
  The likelihood is not convex in ? and ?. We use
  gradient ascent to find an approximate solution for
  a set of ?x, ?y that maximize the likelihood. The
  gradient of the d2x,y term pulls neighbors closer in
  proportion to the empirical joint probability:
  ?
  ??x
  ?
  x,y
  ?p?(x, y)d2x,y =
  ?
  y
  2p?(x, y)(?y ? ?x)
  (6)
  The gradient of the Z term pushes neighbors apart
  in proportion to the estimated joint probability:
  ?
  ??x
  (? logZ) =
  ?
  y
  2p(x, y)(?x ? ?y) (7)
  Thus the net effect is to pull pairs together if their
  estimated probability is less than the empirical prob-
  ability and to push them apart otherwise. The gradi-
  ents with respect to ?y are similar.
  S-CODE (Maron et al 2010) additionally re-
  stricts all ?x and ?y to lie on the unit sphere. With
  this restriction, Z stays around a fixed value dur-
  ing gradient ascent. This allows S-CODE to sub-
  stitute an approximate constant Z? in gradient calcu-
  lations for the real Z for computational efficiency.
  In our experiments, we used S-CODE with its sam-
  pling based stochastic gradient ascent algorithm and
  smoothly decreasing learning rate.
  5 Experiments
  In this section we present experiments that evaluate
  substitute vectors as representations of word con-
  text within the S-CODE framework. Section 5.1
  replicates the bigram based S-CODE results from
  (Maron et al 2010) as a baseline. The S-CODE
  algorithm works with discrete inputs. The substi-
  tute vectors as described in Section 3 are high di-
  mensional and continuous. We experimented with
  two approaches to use substitute vectors in a dis-
  crete setting. Section 5.2 presents an algorithm that
  partitions the high dimensional space of substitute
  vectors into small neighborhoods and uses the par-
  tition id as a discrete context representation. Sec-
  tion 5.3 presents an even simpler model which pairs
  each word with a random substitute. When the left-
  word ? right-word pairs used in the bigram model
  are replaced with word ? partition-id or word ? sub-
  stitute pairs we see significant gains in accuracy.
  These results support our running hypothesis that
  paradigmatic features, i.e. potential substitutes of
  a word, are better determiners of syntactic category
  compared to left and right neighbors. Section 5.4
  explores morphologic and orthographic features as
  additional sources of information and its results im-
  prove the state-of-the-art in the field of unsupervised
  syntactic category acquisition.
  Each experiment was repeated 10 times with dif-
  ferent random seeds and the results are reported
  with standard errors in parentheses or error bars in
  graphs. Table 1 summarizes all the results reported
  in this paper and the ones we cite from the literature.
  5.1 Bigram model
  In (Maron et al 2010) adjacent word pairs (bi-
  grams) in the corpus are fed into the S-CODE algo-
  rithm as X,Y samples. The algorithm uses stochas-
  tic gradient ascent to find the ?x, ?y embeddings for
  left and right words in these bigrams on a single 25-
  dimensional sphere. At the end each word w in the
  vocabulary ends up with two points on the sphere,
  a ?w point representing the behavior of w as the
  left word of a bigram and a ?w point representing
  it as the right word. The two vectors for w are con-
  catenated to create a 50-dimensional representation
  at the end. These 50-dimensional vectors are clus-
  tered using an instance weighted k-means algorithm
  and the resulting groups are compared to the cor-
  rect part-of-speech tags. Maron et al(2010) report
  many-to-one scores of .6880 (.0016) for 45 clusters
  and .7150 (.0060) for 50 clusters (on the full PTB45
  tag-set). If only ?w vectors are clustered without
  concatenation we found the performance drops sig-
  nificantly to about .62.
  To make a meaningful comparison we re-ran the
  bigram experiments using our default settings and
  obtained a many-to-one score of .7314 (.0096) and
  the V-measure is .6558 (.0052) for 45 clusters. The
  following default settings were used: (i) each word
  945
  Distributional Models MTO VM
  (Lamar et al 2010a) .708 -
  (Brown et al 1992)* .678 .630
  (Goldwater et al 2007) .632 .562
  (Ganchev et al 2010)* .625 .548
  (Maron et al 2010) .688 (.0016) -
  Bigrams (Sec. 5.1) .7314 (.0096) .6558 (.0052)
  Partitions (Sec. 5.2) .7554 (.0055) .6703 (.0037)
  Substitutes (Sec. 5.3) .7680 (.0038) .6822 (.0029)
  Models with Additional Features MTO VM
  (Clark, 2003)* .712 .655
  (Christodoulopoulos et al 2011) .728 .661
  (Berg-Kirkpatrick and Klein, 2010) .755 -
  (Christodoulopoulos et al 2010) .761 .688
  (Blunsom and Cohn, 2011) .775 .697
  Substitutes and Features (Sec. 5.4) .8023 (.0070) .7207 (.0041)
  Table 1: Summary of results in terms of the MTO and VM scores. Standard errors are given in parentheses when
  available. Starred entries have been reported in the review paper (Christodoulopoulos et al 2010). Distributional
  models use only the identity of the target word and its context. The models on the right incorporate orthographic and
  morphological features.
  was kept with its original capitalization, (ii) the
  learning rate parameters were adjusted to ?0 =
  50, ?0 = 0.2 for faster convergence in log likeli-
  hood, (iii) the number of s-code iterations were in-
  creased from 12 to 50 million, (iv) k-means initial-
  ization was improved using (Arthur and Vassilvit-
  skii, 2007), and (v) the number of k-means restarts
  were increased to 128 to improve clustering and re-
  duce variance.
  5.2 Random partitions
  Instead of using left-word ? right-word pairs as in-
  puts to S-CODE we wanted to pair each word with a
  paradigmatic representation of its context to get a di-
  rect comparison of the two context representations.
  To obtain a discrete representation of the context,
  the random?partitions algorithm first designates a
  random subset of substitute vectors as centroids to
  partition the space, and then associates each context
  with the partition defined by the closest centroid in
  cosine distance. Each partition thus defined gets a
  unique id, and word (X) ? partition-id (Y ) pairs are
  given to S-CODE as input. The algorithm cycles
  through the data until we get approximately 50 mil-
  lion updates. The resulting ?x vectors are clustered
  using the k-means algorithm (no vector concatena-
  tion is necessary). Using default settings (64K ran-
  dom partitions, 25 s-code dimensions, Z = 0.166)
  the many-to-one accuracy is .7554 (.0055) and the
  V-measure is .6703 (.0037).
  To analyze the sensitivity of this result to our spe-
  cific parameter settings we ran a number of experi-
  ments where each parameter was varied over a range
  of values.
  Figure 2 gives results where the number of initial
   0.7
   0.71
   0.72
   0.73
   0.74
   0.75
   0.76
   0.77
   0.78
   0.79
   0.8
   10000  100000
  number of random partitions
  m2o
  Figure 2: MTO is not sensitive to the number of partitions
  used to discretize the substitute vector space within our
  experimental range.
  random partitions is varied over a large range and
  shows the results to be fairly stable across two orders
  of magnitude.
  Figure 3 shows that at least 10 embedding dimen-
  sions are necessary to get within 1% of the best re-
  sult, but there is no significant gain from using more
  than 25 dimensions.
  Figure 4 shows that the constant Z? approximation
  can be varied within two orders of magnitude with-
  out a significant performance drop in the many-to-
  one score. For uniformly distributed points on a 25
  dimensional sphere, the expected Z ? 0.146. In the
  experiments where we tested we found the real Z al-
  ways to be in the 0.140-0.170 range. When the con-
  stant Z? estimate is too small the attraction in Eq. 6
  dominates the repulsion in Eq. 7 and all points tend
  to converge to the same location. When Z? is too
  high, it prevents meaningful clusters from coalesc-
  946
   0.71
   0.2
   0.21
   0.1
   0.11
   0.3
   0.31
   0.4
   0.41
   0.5
   6  60  600
  89numb er ofaedm dpnm8ope8o
  nte
  Figure 3: MTO falls sharply for less than 10 S-CODE
  dimensions, but more than 25 do not help.
   0.7
   0.71
   0.72
   0.73
   0.74
   0.75
   0.76
   0.77
   0.78
   0.79
   0.8
   0.01  0.1  1
  number o faadbptifs tb
  i2b
  Figure 4: MTO is fairly stable as long as the Z? constant
  is within an order of magnitude of the real Z value.
  ing.
  We find the random partition algorithm to be
  fairly robust to different parameter settings and the
  resulting many-to-one score significantly better than
  the bigram baseline.
  5.3 Random substitutes
  Another way to use substitute vectors in a dis-
  crete setting is simply to sample individual substi-
  tute words from them. The random-substitutes al-
  gorithm cycles through the test data and pairs each
  word with a random substitute picked from the pre-
  computed substitute vectors (see Section 3). We ran
  the random-substitutes algorithm to generate 14 mil-
  lion word (X) ? random-substitute (Y ) pairs (12
  substitutes for each token) as input to S-CODE.
  Clustering the resulting ?x vectors yields a many-
  to-one score of .7680 (.0038) and a V-measure of
  .6822 (.0029).
  This result is close to the previous result by the
  random-partition algorithm, .7554 (.0055), demon-
  strating that two very different discrete represen-
  tations of context based on paradigmatic features
  give consistent results. Both results are significantly
  above the bigram baseline, .7314 (.0096). Figure 5
  illustrates that the random-substitute result is fairly
  robust as long as the training algorithm can observe
  more than a few random substitutes per word.
   0.7
   0.71
   0.72
   0.73
   0.74
   0.75
   0.76
   0.77
   0.78
   0.79
   0.8
   1  10  100
  number of random pubptitutep ser ord
  m2o
  Figure 5: MTO is not sensitive to the number of random
  substitutes sampled per word token.
  5.4 Morphological and orthographic features
  Clark (2003) demonstrates that using morpholog-
  ical and orthographic features significantly im-
  proves part-of-speech induction with an HMM
  based model. Section 2 describes a number other ap-
  proaches that show similar improvements. This sec-
  tion describes one way to integrate additional fea-
  tures to the random-substitute model.
  The orthographic features we used are similar to
  the ones in (Berg-Kirkpatrick et al 2010) with small
  modifications:
  ? Initial-Capital: this feature is generated for cap-
  italized words with the exception of sentence
  initial words.
  ? Number: this feature is generated when the to-
  ken starts with a digit.
  ? Contains-Hyphen: this feature is generated for
  lowercase words with an internal hyphen.
  947
  ? Initial-Apostrophe: this feature is generated for
  tokens that start with an apostrophe.
  We generated morphological features using the
  unsupervised algorithm Morfessor (Creutz and La-
  gus, 2005). Morfessor was trained on the WSJ sec-
  tion of the Penn Treebank using default settings, and
  a perplexity threshold of 300. The program induced
  5 suffix types that are present in a total of 10,484
  word types. These suffixes were input to S-CODE
  as morphological features whenever the associated
  word types were sampled.
  In order to incorporate morphological and ortho-
  graphic features into S-CODE we modified its in-
  put. For each word ? random-substitute pair gen-
  erated as in the previous section, we added word ?
  feature pairs to the input for each morphological and
  orthographic feature of the word. Words on average
  have 0.25 features associated with them. This in-
  creased the number of pairs input to S-CODE from
  14.1 million (12 substitutes per word) to 17.7 mil-
  lion (additional 0.25 features on average for each of
  the 14.1 million words).
  Using similar training settings as the previous
  section, the addition of morphological and ortho-
  graphic features increased the many-to-one score of
  the random-substitute model to .8023 (.0070) and
  V-measure to .7207 (.0041). Both these results im-
  prove the state-of-the-art in part-of-speech induction
  significantly as seen in Table 1.
  6 Error Analysis
  Figure 6 is the Hinton diagram showing the rela-
  tionship between the most frequent tags and clusters
  from the experiment in Section 5.4. In general the
  errors seem to be the lack of completeness (multi-
  ple large entries in a row), rather than lack of ho-
  mogeneity (multiple large entries in a column). The
  algorithm tends to split large word classes into sev-
  eral clusters. Some examples are:
  ? Titles like Mr., Mrs., and Dr. are split from the
  rest of the proper nouns in cluster (39).
  ? Auxiliary verbs (10) and the verb ?say? (22)
  have been split from the general verb clusters
  (12) and (7).
  ? Determiners ?the? (40), ?a? (15), and capital-
  ized ?The?, ?A? (6) have been split into their
  own clusters.
  ? Prepositions ?of? (19), and ?by?, ?at? (17) have
  been split from the general preposition cluster
  (8).
  Nevertheless there are some homogeneity errors as
  well:
  ? The adjective cluster (5) also has some noun
  members probably due to the difficulty of sep-
  arating noun-noun compounds from adjective
  modification.
  ? Cluster (6) contains capitalized words that span
  a number of categories.
  Most closed-class items are cleanly separated into
  their own clusters as seen in the lower right hand
  corner of the diagram. The completeness errors are
  not surprising given that the words that have been
  split are not generally substitutable with the other
  members of their Penn Treebank category. Thus it
  can be argued that metrics that emphasize homo-
  geneity such as MTO are more appropriate in this
  context than metrics that average homogeneity and
  completeness such as VM as long as the number of
  clusters is controlled.
  7 Contributions
  Our main contributions can be summarized as fol-
  lows:
  ? We introduced substitute vectors as paradig-
  matic representations of word context and
  demonstrated their use in syntactic category ac-
  quisition.
  ? We demonstrated that using paradigmatic rep-
  resentations of word context and modeling co-
  occurrences of word and context types with
  the S-CODE learning framework give superior
  results when compared to a baseline bigram
  model.
  ? We extended the S-CODE framework to in-
  corporate morphological and orthographic fea-
  tures and improved the state-of-the-art in un-
  supervised part-of-speech induction to 80%
  many-to-one accuracy.
  948
  Figure 6: Hinton diagram comparing most frequent tags and clusters.
  ? All our code and data, including the sub-
  stitute vectors for the one million word
  Penn Treebank Wall Street Journal dataset,
  is available at the authors? website at
  http://goo.gl/RoqEh.
  References
  B. Ambridge and E.V.M. Lieven, 2011. Child Language
  Acquisition: Contrasting Theoretical Approaches,
  chapter 6.1. Cambridge University Press.
  D. Arthur and S. Vassilvitskii. 2007. k-means++: The
  advantages of careful seeding. In Proceedings of the
  eighteenth annual ACM-SIAM symposium on Discrete
  algorithms, pages 1027?1035. Society for Industrial
  and Applied Mathematics.
  Taylor Berg-Kirkpatrick and Dan Klein. 2010. Phyloge-
  netic grammar induction. In Proceedings of the 48th
  Annual Meeting of the Association for Computational
  Linguistics, pages 1288?1297, Uppsala, Sweden, July.
  Association for Computational Linguistics.
  Taylor Berg-Kirkpatrick, Alexandre Bouchard-Co?te?,
  John DeNero, and Dan Klein. 2010. Painless unsu-
  pervised learning with features. In Human Language
  Technologies: The 2010 Annual Conference of the
  North American Chapter of the Association for Com-
  putational Linguistics, pages 582?590, Los Angeles,
  California, June. Association for Computational Lin-
  guistics.
  C. Biemann. 2006. Unsupervised part-of-speech tagging
  employing efficient graph clustering. In Proceedings
  of the 21st International Conference on computational
  Linguistics and 44th Annual Meeting of the Associa-
  tion for Computational Linguistics: Student Research
  Workshop, pages 7?12. Association for Computational
  Linguistics.
  Phil Blunsom and Trevor Cohn. 2011. A hierarchi-
  cal pitman-yor process hmm for unsupervised part of
  speech induction. In Proceedings of the 49th Annual
  Meeting of the Association for Computational Linguis-
  tics: Human Language Technologies, pages 865?874,
  Portland, Oregon, USA, June. Association for Compu-
  tational Linguistics.
  Peter F. Brown, Peter V. deSouza, Robert L. Mercer, Vin-
  cent J. Della Pietra, and Jenifer C. Lai. 1992. Class-
  based n-gram models of natural language. Comput.
  Linguist., 18:467?479, December.
  D. Chandler. 2007. Semiotics: the basics. The Basics
  Series. Routledge.
  Christos Christodoulopoulos, Sharon Goldwater, and
  Mark Steedman. 2010. Two decades of unsupervised
  pos induction: how far have we come? In Proceedings
  of the 2010 Conference on Empirical Methods in Nat-
  ural Language Processing, EMNLP ?10, pages 575?
  584, Stroudsburg, PA, USA. Association for Compu-
  tational Linguistics.
  Christos Christodoulopoulos, Sharon Goldwater, and
  Mark Steedman. 2011. A bayesian mixture model
  for pos induction using multiple features. In Proceed-
  ings of the 2011 Conference on Empirical Methods in
  Natural Language Processing, pages 638?647, Edin-
  burgh, Scotland, UK., July. Association for Computa-
  tional Linguistics.
  949
  Kenneth Ward Church. 1988. A stochastic parts pro-
  gram and noun phrase parser for unrestricted text. In
  Proceedings of the second conference on Applied nat-
  ural language processing, ANLC ?88, pages 136?143,
  Stroudsburg, PA, USA. Association for Computational
  Linguistics.
  Alexander Clark. 2003. Combining distributional and
  morphological information for part of speech induc-
  tion. In Proceedings of the tenth conference on Eu-
  ropean chapter of the Association for Computational
  Linguistics - Volume 1, EACL ?03, pages 59?66,
  Stroudsburg, PA, USA. Association for Computational
  Linguistics.
  Mathias Creutz and Krista Lagus. 2005. Inducing
  the morphological lexicon of a natural language from
  unannotated text. In Proceedings of AKRR?05, Inter-
  national and Interdisciplinary Conference on Adap-
  tive Knowledge Representation and Reasoning, pages
  106?113, Espoo, Finland, June.
  D. Freudenthal, J.M. Pine, and F. Gobet. 2005. On the
  resolution of ambiguities in the extraction of syntactic
  categories through chunking. Cognitive Systems Re-
  search, 6(1):17?25.
  Kuzman Ganchev, Joa?o Grac?a, Jennifer Gillenwater, and
  Ben Taskar. 2010. Posterior regularization for struc-
  tured latent variable models. J. Mach. Learn. Res.,
  99:2001?2049, August.
  Jianfeng Gao and Mark Johnson. 2008. A comparison of
  bayesian estimators for unsupervised hidden markov
  model pos taggers. In Proceedings of the Conference
  on Empirical Methods in Natural Language Process-
  ing, EMNLP ?08, pages 344?352, Stroudsburg, PA,
  USA. Association for Computational Linguistics.
  Amir Globerson, Gal Chechik, Fernando Pereira, and
  Naftali Tishby. 2007. Euclidean embedding of co-
  occurrence data. J. Mach. Learn. Res., 8:2265?2295,
  December.
  Sharon Goldwater and Tom Griffiths. 2007. A fully
  bayesian approach to unsupervised part-of-speech tag-
  ging. In Proceedings of the 45th Annual Meeting of
  the Association of Computational Linguistics, pages
  744?751, Prague, Czech Republic, June. Association
  for Computational Linguistics.
  David Graff, Roni Rosenfeld, and Doug Paul. 1995. Csr-
  iii text. Linguistic Data Consortium, Philadelphia.
  Aria Haghighi and Dan Klein. 2006. Prototype-driven
  learning for sequence models. In Proceedings of
  the main conference on Human Language Technology
  Conference of the North American Chapter of the As-
  sociation of Computational Linguistics, HLT-NAACL
  ?06, pages 320?327, Stroudsburg, PA, USA. Associa-
  tion for Computational Linguistics.
  Mark Johnson. 2007. Why doesn?t EM find good
  HMM POS-taggers? In Proceedings of the 2007 Joint
  Conference on Empirical Methods in Natural Lan-
  guage Processing and Computational Natural Lan-
  guage Learning (EMNLP-CoNLL), pages 296?305,
  Prague, Czech Republic, June. Association for Com-
  putational Linguistics.
  Michael Lamar, Yariv Maron, and Elie Bienenstock.
  2010a. Latent-descriptor clustering for unsupervised
  pos induction. In Proceedings of the 2010 Conference
  on Empirical Methods in Natural Language Process-
  ing, EMNLP ?10, pages 799?809, Stroudsburg, PA,
  USA. Association for Computational Linguistics.
  Michael Lamar, Yariv Maron, Mark Johnson, and Elie
  Bienenstock. 2010b. Svd and clustering for unsuper-
  vised pos tagging. In Proceedings of the ACL 2010
  Conference Short Papers, pages 215?219, Uppsala,
  Sweden, July. Association for Computational Linguis-
  tics.
  Yoong Keok Lee, Aria Haghighi, and Regina Barzilay.
  2010. Simple type-level unsupervised pos tagging.
  In Proceedings of the 2010 Conference on Empirical
  Methods in Natural Language Processing, EMNLP
  ?10, pages 853?861, Stroudsburg, PA, USA. Associ-
  ation for Computational Linguistics.
  Mitchell P. Marcus, Beatrice Santorini, Mary Ann
  Marcinkiewicz, and Ann Taylor. 1999. Treebank-3.
  Linguistic Data Consortium, Philadelphia.
  Yariv Maron, Michael Lamar, and Elie Bienenstock.
  2010. Sphere embedding: An application to part-of-
  speech induction. In J. Lafferty, C. K. I. Williams,
  J. Shawe-Taylor, R.S. Zemel, and A. Culotta, editors,
  Advances in Neural Information Processing Systems
  23, pages 1567?1575.
  Bernard Merialdo. 1994. Tagging english text with a
  probabilistic model. Comput. Linguist., 20:155?171,
  June.
  T.H. Mintz. 2003. Frequent frames as a cue for gram-
  matical categories in child directed speech. Cognition,
  90(1):91?117.
  M. Redington, N. Crater, and S. Finch. 1998. Distribu-
  tional information: A powerful cue for acquiring syn-
  tactic categories. Cognitive Science, 22(4):425?469.
  A. Rosenberg and J. Hirschberg. 2007. V-measure: A
  conditional entropy-based external cluster evaluation
  measure. In Proceedings of the 2007 Joint Conference
  on Empirical Methods in Natural Language Process-
  ing and Computational Natural Language Learning,
  pages 410?420.
  Magnus Sahlgren. 2006. The Word-Space Model: Us-
  ing distributional analysis to represent syntagmatic
  and paradigmatic relations between words in high-
  dimensional vector spaces. Ph.D. thesis, Stockholm
  University.
  Hinrich Schu?tze. 1995. Distributional part-of-speech
  tagging. In Proceedings of the seventh conference
  950
  on European chapter of the Association for Compu-
  tational Linguistics, EACL ?95, pages 141?148, San
  Francisco, CA, USA. Morgan Kaufmann Publishers
  Inc.
  Andreas Stolcke. 2002. Srilm-an extensible language
  modeling toolkit. In Proceedings International Con-
  ference on Spoken Language Processing, pages 257?
  286, November.
  951
  