Wide-Coverage Semantic Representations from a CCG Parser

This paper shows how to construct semantic representations from the derivations produced by a wide-coverage CCG parser. Unlike the dependency structures returned by the parser itself, these can be used directly for semantic interpretation. We demonstrate that well-formed semantic representations can be produced for over 97% of the sentences in unseen WSJ text. We believe this is a major step towards widecoverage semantic interpretation, one of the key objectives of the field of NLP.

Introduction
The levels of accuracy and robustness recently achieved by statistical parsers (e.g. Collins (1999), Charniak (2000)) have led to their use in a number of NLP applications, such as question-answering (Pasca and Harabagiu, 2001), machine translation (Charniak et al., 2003), sentence simplification (Carroll et al., 1999), and a linguist's search engine (Resnik and Elkiss, 2003). Such parsers typically return phrase-structure trees in the style of the Penn Treebank, but without traces and coindexation. However, the usefulness of this output is limited, since the underlying meaning (as represented in a predicate-argument structure or logical form) is difficult to reconstruct from such skeletal parse trees.
In this paper we demonstrate how a widecoverage statistical parser using Combinatory Categorial Grammar (CCG) can be used to generate semantic representations. There are a number of advantages to using CCG for this task. First, CCG provides "surface compositional" analysis of certain syntactic phenomena such as coordination and extraction, allowing the logical form to be obtained for such cases in a straightforward way. Second, CCG is a lexicalised grammar, and only uses a small number of semantically transparent combinatory rules to combine CCG categories. Hence providing a compositional semantics for CCG simply amounts to assigning semantic representations to the lexical entries and interpreting the combinatory rules. And third, there exist highly accurate, efficient and robust CCG parsers which can be used directly for this task (Clark and Curran, 2004b;Hockenmaier, 2003).
The existing CCG parsers deliver predicate argument structures, but not semantic representations that can be used for inference. The present paper seeks to extend one of these wide coverage parsers by using it to build logical forms suitable for use in various NLP applications that require semantic interpretation.
We show how to construct first-order representations from CCG derivations using the λ-calculus, and demonstrate that semantic representations can be produced for over 97% of the sentences in unseen WSJ text. The only other deep parser we are aware of to achieve such levels of robustness for the WSJ is Kaplan et al. (2004). The use of the λ-calculus is integral to our method. However, first-order representations are simply used as a proof-of-concept; we could have used DRSs (Kamp and Reyle, 1993) or some other representation more tailored to the application in hand.
There is some existing work with a similar motivation to ours. Briscoe and Carroll (2002) generate underspecified semantic representations from their robust parser. Toutanova et al. (2002) and Kaplan et al. (2004) combine statistical methods with a linguistically motivated grammar formalism (HPSG and LFG respectively) in an attempt to achieve levels of robustness and accuracy comparable to the Penn Treebank parsers (which Kaplan et al. do achieve). However, there is a key difference between these approaches and ours. In our approach the creation of the semantic representations forms a completely  Figure 1: An example CCG derivation with a provisional semantics using predicate-argument structures separate module to the syntax, whereas in the LFG and HPSG approaches the semantic representation forms an integral part of the grammar. This means that, in order for us to work with another semantic formalism, we simply have to modify the lexical entries with respect to the semantic component.

Combinatory Categorial Grammar
We assume familiarity with CCG (Steedman, 2000), an entirely type-driven lexicalized theory of grammar based on categorial grammar. CCG lexical entries pair a syntactic category (defining syntactic valency and directionality) with a semantic interpretation. For example, one of the categories for the verb cost can be written as follows, with a provisional Montague-style semantics expressed in terms of predicate-argument structure: 1 VP VP NP NP NP : λxλyλpλz cost p zx yxz Combinatory rules project such lexical categoryinterpretation pairs onto derived categoryinterpretation pairs.
The specific involvement in CCG of rules of functional composition (indexed B and B in derivations) and type-raising (indexed T and T) allows very free derivation of non-standard constituents. This results in semantic interpretations that support the "surface compositional" analysis of relativization and coordination, as in Figure 1 for the sentence It could cost taxpayers £15 million to install and BPC residents 1 million a year to maintain. 2 1 This semantic notation uses x y z and p q r s as variables, identifies constants with primes and uses concatenation a b to indicate application of a to b. Application is "left-associative," so abc is equivalent to ! ab" c. The order of arguments in the predication is "wrapped", consistent with the facts of reflexive binding.
2 Some details of the derivation and of the semantics of noun phrases are suppressed, since these are developed be-While the proliferation of surface constituents allowed by CCG adds to derivational ambiguity (since the constituent taxpayers £15 million to install is also allowed in the non-coordinate sentence It could cost taxpayers £15 million to install), previous work has shown that standard techniques from the statistical parsing literature can be used for practical widecoverage parsing with state-of-the-art performance.

The Parser
A number of statistical parsers have recently been developed for CCG (Clark et al., 2002;Hockenmaier and Steedman, 2002b;Clark and Curran, 2004b). All of these parsers use a grammar derived from CCGbank (Hockenmaier and Steedman, 2002a;Hockenmaier, 2003), a treebank of normalform CCG derivations derived semi-automatically from the Penn Treebank. In this paper we use the Clark and Curran (2004b) parser, which uses a loglinear model of normal-form derivations to select an analysis.
The parser takes a POS tagged sentence as input with a set of lexical categories assigned to each word. A CCG supertagger (Clark and Curran, 2004a) is used to assign the categories. The supertagger uses a log-linear model of the target word's context to decide which categories to assign. Clark and Curran (2004a) shows how dynamic use of the supertagger -starting off with a small number of categories assigned to each word and gradually increasing the number until an analysis is found -can lead to a highly efficient and robust parser.
The lexical category set used by the parser consists of those category types which occur at least 10 times in sections 2-21 of CCGbank, which results in a set of 409 categories. Clark and Curran (2004a) demonstrates that this relatively small set has high coverage on unseen data and can be used to create low. Some categories and interpretations are split across lines to save space. a robust and accurate parser. The relevance of a relatively small category set is that, in order to obtain semantic representations for a particular formalism, only 409 categories have to be annotated.
The parser uses the CKY chart-parsing algorithm from Steedman (2000). The combinatory rules used by the parser are functional application (forward and backward), generalised forward composition, backward composition, generalised backwardcrossed composition, and type raising. There is also a coordination rule which conjoins categories of the same type.
The parser also uses a number of unary type-changing rules (Hockenmaier and Steedman, 2002a) and punctuation rules taken from CCGbank. An example of a type-changing rule used by the parser is the following, which takes a passive form of a verb and creates a nominal modifier: This rule is used to create NPs such as the role played by Kim Cattrall. An example of a comma rule is the following: This rule takes a sentential modifier followed by a comma and returns a sentential modifier of the same type. Type-raising is applied to the categories NP, PP and S adj¡ £ ¢ NP (adjectival phrase), and is implemented by adding the relevant set of type-raised categories to the chart whenever an NP, PP or S adj¡ £ ¢ NP is present. The sets of type-raised categories are based on the most commonly used typeraising rule instantiations in sections 2-21 of CCGbank, and currently contain 8 type-raised categories for NP and 1 each for PP and S adj¡ £ ¢

NP.
For a given sentence, the automatically extracted grammar can produce a very large number of derivations.  and Clark and Curran (2004b) describe how a packed chart can be used to efficiently represent the derivation space, and also efficient algorithms for finding the most probable derivation. The parser uses a log-linear model over normal-form derivations. 3 Features are defined in terms of the local trees in the derivation, including lexical head information and word-word dependencies. The normal-form derivations in CCGbank provide the gold standard training data.
For a given sentence, the output of the parser is a set of syntactic dependencies corresponding to the 3 A normal-form derivation is one which only uses typeraising and function composition when necessary. most probable derivation. However, for this paper the parser has been modified to simply output the derivation in the form shown in Figure 2, which is the input for the semantic component.

Semantic Formalism
Our method for constructing semantic representations can be used with many different semantic formalisms. In this paper we use formulas of first-order logic with a neo-Davidsonian analysis of events. We do not attempt to cover all semantic phenomena; for example, we do not currently deal with the resolution of pronouns and ellipsis; we do not give a proper analysis of tense and aspect; we do not distinguish between distributive and collective readings of plural noun phrases; and we do not handle quantifier scope ambiguities.
The following first-order formula for the sentence A spokesman had no comment demonstrates the representation we use: § x(spokesman(x)© y(comment(y) § e(have(e)¨agent(e,x)¨patient(e,y)))).
The tool that we use to build semantic representations is based on the lambda calculus. It can be used to mark missing semantic information from natural language expressions in a principled way using λ, an operator that binds variables ranging over various semantic types. For instance, a noun phrase like a spokesman can be given the λ-expression λp. §

x(spokesman(x)¨(p@x))
where the @ denotes functional application, and the variable p marks the missing information provided by the verb phrase. This expression can be combined with the λ-expression for lied, using functional application, yielding the following expression: λp. § x(spokesman(x)¨(p@x))@ λy. § e(lie(e)¨agent(e,y)).
β-conversion is the process of eliminating all occurrences of functional application by substituting the argument for the λ-bound variables in the functor. β-conversion turns the previous expression into a first-order translation for A spokesman lied: § x(spokesman(x)¨ § e(lie(e)¨agent(e,x))).
The resulting semantic formalism is very similar to the type-theoretic language L λ (Dowty et al., 1981). However, we merely use the lambdacalculus as a tool for constructing semantic representations, rather as a formal tool for modeltheoretic interpretation. As already mentioned, we can use the same method to obtain, for example, Discourse Representation Structures (Kuschert, 1999), or underspecified semantic representations (Bos, 2004) to deal with quantifier scope ambiguities.

Method and Algorithm
The output of the parser is a tree representing a CCG derivation, where the leaves are lexical items and the nodes correspond to one of the CCG combinatory rules, a unary type-changing rule, a typeraising rule, or one of the additional miscellaneous rules discussed earlier. Mapping the CCG derivation into a semantic representation consists of the following tasks: 1. assigning semantic representations to the lexical items; 2. reformulating the combinatory rules in terms of functional application; 3. dealing with type-raising and type-changing rules; 4. applying β-conversion to the resulting tree structure.
Lexical items are ordered pairs consisting of the CCG category and a lemmatised wordform. This information is used to assign a λ-expression to the leaf nodes in the tree. For most open-class lexical items we use the lemma to instantiate the lexical semantics, as illustrated by the following two examples (intransitive verbs and adjectives): For closed-class lexical items, the lexical semantics is spelled out for each lemma individually, as in the following two examples: The following type-changing rule applies to the lexical semantics of categories of type N and converts them to NP: Tasks 1-3 are implemented using a recursive algorithm that traverses the derivation and returns a λ-expression. Note that the punctuation rules used by the parser do not contribute to the compositional semantics and are therefore ignored.
Task 4 reduces the λ-expression to the target representation by applying β-conversion. In order to maintain correctness of this operation, the functor undergoes α-conversion (renaming all bound variables for new occurrences) before substitution takes place. β-conversion is implemented using the tools provided by Blackburn and Bos (2003).

Results
There are a number of possible ways to evaluate the semantic representations output by our system. The first is to calculate the coverage -that is, the percentage of syntactic parses which can be given some analysis by the semantic component. The second is to evaluate the accuracy of the semantic representations; the problem is that there is not yet an accepted evaluation metric which can be applied to such representations.
There is, however, an accepted way of evaluating the syntactic component of the system, namely to calculate precision and recall figures for labelled syntactic dependencies (Clark et al., 2002). Given  , lex('NP',leaf('N','students')), conj ('conj','NP','NP\NP', leaf('conj','and'), lex('NP',leaf('N','teachers')))))))). )))))))) Figure 2: Parser output and semantic representation for the example sentence: The school-board hearing at which she was dismissed was crowded with students and teachers that the CCG parser produces dependencies which are essentially predicate-argument dependencies, the accuracy of the syntactic component should be a good indication of the accuracy of the semantics, especially given the transparent interface between syntax and semantics used by our system. Hence we report coverage figures in this paper, and repeat figures for dependency recovery from an earlier paper. We do not evaluate the accuracy of the system output directly, but we do have a way of checking the well-formedness of the semantic representations. (The well-formedness of the representation does not of course guarantee the correctness of the output.) If the semantic representation fails to βconvert, we know that there are type conflicts resulting from either: incorrect semantics assigned to some lexical entries; incorrect interpretation of one of the combinatory rules; or an inconsistency in the output of the syntactic component.
We assigned lexical semantics to the 245 most frequent categories from the complete set of 409, and implemented 4 of the type-raising rules, and the 10 unary type-changing rules, used by the parser. We used section 00 from CCGbank for development purposes; section 23 (2,401 sentences) was used as the test set. The parser provides a syntactic analysis for 98.6% of the sentences in section 23. The accuracy of the parser is reported in Clark and Curran (2004b): 84.6% F-score over labelled dependencies for section 23. Of the sentences the parser analyses, 92.3% were assigned a semantic representation, all of which were well-formed. The output of the system for an example sentence is given in Figure 2. The reason for the lack of complete coverage is that we did not assign semantic representations to the complete set of lexical categories. In future work we will cover the complete set, but as a simple remedy we have implemented the following robustness strategy: we assign a semantic template to parts of the tree that could not be analysed. For example, the template for the NP category is λp. § x(p@x). This was done for the 10 most frequent categories and results in a coverage of 98.6%.
Although we expect the accuracy of the semantic representations to mirror those of the syntactic component, and therefore be useful in NLP applications, there is still a small number of errors arising from different sources. First, some constructions are incorrectly analysed in CCGbank; for example, appositives in CCGbank are represented as coordinate constructions (Hockenmaier, 2003). Second, errors are introduced by the semantic construction component; for example, the non-head nouns in a nounnoun compound are currently treated as modifiers of the head noun, in the same way as adjectives. And finally, the parser introduces errors because of incomplete coverage of the lexicon, and mistakes due to the parsing model. We expect general improvements in statistical parsing technology will further improve the accuracy of the parser, and we will further develop the semantic component.

Conclusions and Future Work
This paper has demonstrated that we can construct semantic representations using a wide-coverage CCG parser, with a coverage of over 97% on unseen WSJ sentences. We believe this is a major step towards wide-coverage semantic interpretation, one of the key objectives of the field of NLP.
The advantages of our approach derive largely from the use of CCG. The lexicalised nature of the formalism means that our system has a high degree of modularity, with separate syntactic and semantic components.
We have shown how to construct simple firstorder semantic representations from CCG derivations. We have not dealt with all semantic phenomena, such as quantifier scope ambiguities and anaphora resolution. In future work we will investigate using underspecified semantic representations. The utility of our system for NLP applications will be tested by integration with an existing opendomain Question-Answering system (Leidner et al., 2003).
We will also investigate the construction of a treebank of semantic representations derived automatically from CCGbank. Previous work, such as Liakata and Pulman (2002) and Cahill et al. (2003), has attempted to generate semantic representations from the Penn Treebank. Cahill et al. use a translation of the Treebank to LFG F-structures and quasilogical forms. An advantage of our approach is that our system for constructing semantic representations, whatever semantic formalism is used, can be applied directly to the derivations in CCGbank.


Polarity sensitivity and evaluation order in type-logical grammar

We present a novel, type-logical analysis of_polarity sensitivity_: how negative polarity items (like"any"and"ever") or positive ones (like"some") are licensed or prohibited. It takes not just scopal relations but also linear order into account, using the programming-language notions of delimited continuations and evaluation order, respectively. It thus achieves greater empirical coverage than previous proposals.

Introduction
Polarity sensitivity (Ladusaw, 1979) has been a popular linguistic phenomenon to analyze in the categorial (Dowty, 1994), lexical-functional (Fry, 1997(Fry, , 1999, and type-logical (Bernardi, 2002;Bernardi and Moot, 2001) approaches to grammar. The multitude of these analyses is in part due to the more explicit emphasis that these traditions place on the syntax-semantics interface-be it in the form of Montague-style semantic rules, the Curry-Howard isomorphism, or linear logic as glue-and the fact that polarity sensitivity is a phenomenon that spans syntax and semantics.
On one hand, which polarity items are licensed or prohibited in a given linguistic environment depends, by and large, on semantic properties of that environment (Ladusaw, 1979;Krifka, 1995, inter alia). For example, to a first approximation, negative polarity items can occur only in downward-entailing contexts, such as under the scope of a monotonically decreasing quantifier. A quantifier q, of type (e → t) → t where e is the type of individuals and t is the type of truth values, is monotonically decreasing just in case (1) ∀s 1 . ∀s 2 . ∀x. s 2 (x) ⇒ s 1 (x) ⇒ q(s 1 ) ⇒ q(s 2 ). Thus (2a) is acceptable because the scope of nobody is downward-entailing, whereas (2b-c) are unacceptable.
On the other hand, a restriction on surface syntactic form, such as that imposed by polarity sensitivity, is by definition a matter of syntax. Besides, there are syntactic restrictions on the configuration relating the licensor to the licensee. For example, (2a) above is acceptablenobody manages to license anybody-but (3) below is not. As the contrast in (4) further illustrates, the licensor usually needs to precede the licensee.
The syntactic relations allowed between licensor and licensee for polarity sensitivity purposes are similar to those allowed between antecedent and pronoun for variable binding purposes. To take one example, just as an antecedent's ability to bind a (c-commanded) pronoun percolates up to a containing phrase (such as in (5), what Büring (2001) calls "binding out of DP"), a licensor's ability to license a (c-commanded) polarity item percolates up to a containing phrase (such as in (4a)).
(5) [Every boy i 's mother] saw his i father.
Moreover, just as a bindee can precede a binder in a sentence when the bindee sits in a clause that excludes the binder (as in (6); see Williams, 1997, §2.1), a licensee can precede a licensor in a sentence when the licensee sits in a clause that excludes the licensor (as in (7); see Ladusaw, 1979, page 112).
(6) That he i would be arrested for speeding came as a surprise to every i motorist. (7) That anybody would be arrested for speeding came as a surprise to the district attorney.
This paper presents a new, type-logical account of polarity sensitivity that encompasses the semantic properties exemplified in (2) and the syntactic properties exemplified in (3-4). Taking advantage of the Curry-Howard isomorphism, it is the first account of polarity sensitivity in the grammatical frameworks mentioned above to correctly fault (3) for the failure of nobody to appear before Axiom A A For each unary mode α (blank, u, or p in this paper): For each binary mode β (blank or c in this paper): Figure 1: Natural deduction rules for multimodal categorial grammar (Bernardi, 2002, pages 9 and 50). To reduce notation, we do not distinguish structural punctuation from logical connectives. anybody. The analysis makes further correct predictions, as we will see at the end of §3.
The analysis here borrows the concepts of delimited continuations (Felleisen, 1988;Danvy and Filinski, 1990) and evaluation order from the study of programming languages. Thus this paper is about computational linguistics, in the sense of applying insights from computer science to linguistics. The basic idea transfers to other formalisms, but type-logical grammar-more precisely, multimodal categorial grammar-offers a fragment NL R − whose parsing problem is decidable using proof-net technology (Moot, 2002, §9.2), which is of great help while developing and testing the theory.
2 Delimited continuations Figure 1 shows natural deduction rules for multimodal categorial grammar, a member of the type-logical family of grammar formalisms (Moortgat, 1996a;Bernardi, 2002). Figure 2 lists our structural postulates. These two figures form the logic underlying our account.
We use two binary modes: the default mode (blank) for surface syntactic composition, and the continuation mode c. As usual, a formula of the form A • B can be read as "A followed by B". By contrast, a formula of the form A • c B can be read as "A in the context B". In programming-language terms, the formula A • c B plugs a subexpression A into a delimited continuation B. The Root rule creates a trivial continuation: it says that 1 is a right identity for the c mode, where 1 can be thought of as a nullary connective, effectively enabling empty antecedents for the c mode. The binary modes, along with the first three postulates in Figure 2, provide a new way to encode Moortgat's ternary connective q (1996b) for insitu quantification. For intuition, it may help to draw logical formulas as binary trees, distinguishing graphically between the two modes.
To further capture the interaction between scope inversion and polarity sensitivity exemplified in (3-4), we use three unary modes: the value mode (blank), the unquotation mode u, and the polarity mode p. The value mode marks when an expression is devoid of in-situ quantification, or, in programming-language terms, when it is a pure value rather than a computation with control effects. As a special case, any formula can be turned pure by embedding it under a diamond using the T postulate, analogous to quotation or staging in programming languages. Quotations can be concatenated using the K postulate. The unquotation mode u marks when a diamond can be canceled using the Unquote postulate. Unquotation is also known as eval or run in programming languages. The polarity mode p, and the empirical utility of these unary modes, are explained in §3.
A derivation is considered complete if it culminates in a sequent whose antecedent is built using the default binary mode • only, and whose conclusion is a type of the form u A. Below is a derivation of Alice saw Bob.

(8)
Alice np saw (np\ u s)/np Bob np /E saw • Bob np\ u s \E Alice • (saw • Bob) u s Note that clauses take the type u s rather than the usual s, so the Unquote rule can operate on clauses. We abbreviate u s to s • below.
To illustrate in-situ quantification, Figure 3 on the following page shows a derivation of Alice saw a man's mother. For brevity, we treat a man as a single lexical item. It is a quantificational noun phrase whose polarity is neutral in a sense that contrasts with other quantifiers considered below. The crucial part of this derivation is the use of the structural postulates Root, Left, and Right to divide the sentence into two parts: the subexpression a man and its context Alice saw 's mother. The type of a man, s • / c (np\ c s • ), can be read as "a subexpression that produces a clause when placed in a context that can enclose an np to make a clause".

Polarity sensitivity and evaluation order
The p mode mediates polarity sensitivity. For every unary mode α, we can derive A Figure 6: Linear order in polarity licensing: ruling out Anybody saw nobody using left-to-right evaluation order postulates in Figure 2, whenever two quantifiers take inverse rather than linear scope with respect to each other, the transitions must pass through a start state (that is, a clause type that can be Unquoted) in between. This constraint is an empirical advance over previous accounts, which are oblivious to linear order. The input and output polarities of quantifiers are highly mutually constrained. Take everybody for example. If we hold the polarity assignments of the other quantifiers fixed, then the existence of a linear-scope reading for A man introduced everybody to somebody forces everybody to be input-positive and output-neutral. But then our account predicts that Nobody introduced everybody to somebody has a linear-scope reading, unlike the simpler sentence Nobody introduced Alice to somebody. This prediction is borne out, as observed by Kroch (1974, pages 121-122) and discussed by Szabolcsi (2004).


"User Interfaces"and the Social Negotiation of Availability

In current presence or availability systems, the method of presenting a user's state often supposes an instantaneous notion of that state - for example, a visualization is rendered or an inference is made about the potential actions that might be consistent with a user's state. Drawing on observational research on the use of existing communication technology, we argue (as have others in the past) that determination of availability is often a joint process, and often one that takes the form of a negotiation (whether implicit or explicit). We briefly describe our current research on applying machine learning to infer degrees of conversational engagement from observed conversational behavior. Such inferences can be applied to facilitate the implicit negotiation of conversational engagement - in effect, helping users to weave together the act of contact with the act of determining availability.

INTRODUCTION
The most common application of presence and availability systems is to advise users when conditions might be suitable for making contact -e.g., facilitating communication between a user who wishes to make contact (hereafter contactor) and one or more contactees. Contact can be face-to-face, as in Ambush [8], as well as technologically-mediated, as in Awarenex [5] and BESTCOM [6]. Typically, such systems provide some kind of visible representation of the contactees' presence or availability state (past, present, and/or projected) so that the contactor can make appropriate decisions. For example, BESTCOM infers which communication channels are most appropriate for contactees given their context and presents these choices to the contactor (without revealing the context itself). Awarenex applies inference to, e.g., automate "away" status messages as an aid to contactors. Ambush provides a temporal visualization.
Clean, simple representations seem suitable for groups with well-aligned goals and practices -gelled work teams, departments, etc. They also seem valuable in complex availability scenarios, such as determining good meeting times for groups. However, different kinds of groups may present additional challenges for availability forecasting. Consider the differences between co-located work within an organizational workplace (which is likely to have considerable synchrony between individuals' activity rhythms), distributed work within an organizational workplace (in which rhythms may be offset by geographic time differences or rearranged by work practice differences between the sites), and telecommuting and nomadic work (in which rhythms are strongly influenced by constant interaction with external entities and the contingencies of travel). In situations where availability forecasting may be less reliable, or where social relationships are such that contact may be sensitive, it may be useful to conceptualize our representations of "availability" in a different way. The idea would be that such representations ought to lead to "socially" robust results in the face of system mispredictions or user misinterpretations.
In what follows, we briefly point out some challenges -"sensitivities" might be a better word -that could be considered in the design of systems that present presence and availability to contactors. We then describe our current research, which focuses on the use of machine learning to assess the progress of conversational engagement.

USER INTERFACE CHALLENGES
We argue that the most effective systems for sharing presence and availability information will reflect naturally occurring social processes. For example, they will allow information to flow back and forth between the contactee and the contactor. In this section, we discuss how availability information is part of an ongoing process of communication. The three main observations are somewhat interrelated, corresponding to "intuitive" dimensions rather than "orthogonal" dimensions. Each observation raises a number of issues, which we present as challenges rather than as prescribed solutions. In the following section, we discuss our own approach to these challenges, which is quite different from that taken in the most obviously related systems (e.g., [5,6,8]).

Expression of availability is highly contextual
Representations of a contactee's availability tend to be "one size fits all" with respect to situational context. Some systems do support, e.g., access control rules which allow contactees to control what information will be presented to what contactors.
Otherwise, contactees generally have little ability to define how they present themselves -to act out different lines [4] -to different contactors in different situations.
In the absence of computers, the manner in which contactees express availability is often highly contextual. That is, how contactees choose to express their current state and activities to others depends on their current understanding of the situations and needs of all parties. Schegloff notes that the formulations of place that are communicated in telephone conversation -where "place" actually includes broad notions of situational contextdepend on who is calling, the purpose of the call, how the callee wishes to present themselves, and so on. (A related perspective is to consider the expression of availability as an "input" to the ongoing process though which the various parties account for their own actions and for the actions of others [3].) Recent ethnomethodological analyses of mobile phone conversations, such as Laurier's study of mobile white-collar workers [7] and Weilenmann's study of Swedish youth [13], provide updated examples of this phenomenon from today's "wireless world." As Laurier observes, a particular way of communicating "I'm still on the train" that might be interpreted as a simple status update can actually be an important act of preemptive, longdistance face-work [4].
Practices of "getting the right message across" seem important in certain situations, but also seem difficult to accomplish using the simplest representations of availability; this suggests new areas for augmenting such representations.
Considering representations from these perspectives can also help to clarify certain design problems whose existence seems obvious from vague intuitions. For example, a smart availability mechanism that operates as a black-box seems intuitively undesirable because "we don't know what it is doing." Clearly, one problem with such a mechanism is that it takes away contactees' ability to explicitly control the accounts provided to others for their activities and to estimate the accounts that others have constructed. As another example, consider the white-box idea of providing multiple forms of primitive context information (e.g., location, or whether one is alone or not) so that contactors can interpret them and come up with their own formulations of availability [11]. This mechanism is much more easily understood, but we immediately see that the contactee has again lost control over the facts (i.e., context) from which others construct their accounts.

Determination of availability is a negotiation
People's willingness to make themselves available to others, and correspondingly their choice of how to represent their current availability to others, depends on a jointly evolving understanding of the current situations and needs of all parties. As a phone call proceeds, additional information typically becomes available to the various parties and each continues to assess whether the interaction should continue. An interaction might continue as planned by the contactor, but it might also close early. Closing may be initiated by the contactee, but it can also be initiated by a socially-aware contactor. For example, one can infer from prosody (e.g., tone of voice, or inordinately slow or fast speech) that a contactee is reluctant to continue. As a result, consideration needs to be made of the ways in which an availability system interacts with its associated communication systems to feed information forward from contactors as well as backward from contactees.
By "feed forward," we mean methods of pushing information to the contactee. In conventional telephony, callers with urgent business sometimes cram this fact into the start of a call [13] or, finding themselves in a potential call-screening situation, state their business "in the blind" to a hypothetical listener (i.e., without knowing whether or not the callee is actually listening). In systems where users' first conversational turns serve as the "summons," as in instant messaging (IM) [9] or Nextel push-to-talk cellular radios [14], this first turn is always "in the blind" to some degree. More complex negotiation models in this vein are supported by Quiet Calls [10] and Impromptu [12].
To understand what we mean by "feed backward," consider that communication itself provides context. This is sometimes implicit, as in the leakage of background sound through a phone call (which provides context about current surroundings) or a speaker's prosody. This can be explicit, as in the deliberate verbal sharing of otherwise hidden status [13]. Calls.calm [11] enables contactees to provide more resources to potential contactors for determining availability than a typical presence mechanism. Quiet Calls provides a discreet means for a contactee to provide "verbal" backchannel while a contactor feeds information forward through the open phone connection [10].
Since the final decision that an interaction will proceed as desired by the contactor may result after some amount of interaction has actually already occurred, systems designers can fruitfully anticipate that interactions will unfold in this way. The implication is that, in these cases, integration of "availability" tools and "communication" tools may prove useful -integration that not only goes beyond IM and "away" messages, but even beyond that in Awarenex.

Availability reflects ongoing relationships
A given interaction between people with existing relationships often forms a "conversation-in-a-series" [2]. Such interactions are often highly dependent on shared context from previous conversations and closing is often initiated with explicit reference to future contact ("See you," "I'll let you know when I find the file").
Given that this is a frequent situation, it would be useful for a tool that supports contact-making to help manage these bits of conversational context. One way to approach this is to provide separate channels for what Pedersen called "continuity information" in Calls.calm [11]. Continuity information can either feed forward from the contactor (e.g., an "urgent reply" status light can convey that the contactor is upgrading the urgency of a recent request) or backward from the contactee (e.g., a contactor-specific "away" message can convey status such as "I still haven't found the file").
This reflects the fact that new developments can arise on either side of the ongoing interaction. Again, tight integration of "availability" tools and "communication" tools can help in problematic situations.

SOCIAL, MOBILE AUDIO SPACES
We are currently working on a system that provides mobile, lightweight audio communication within small, tightly-knit social groups, such as college-age friends [1]. The design is influenced, in part, by the recognition that the attempt to engage in conversation is sometimes an integral part of the social negotiation of availability. Rather than focusing on mechanisms for determining presence or availability, we assume that such means will be partially effective, and focus instead on a complementary and less-studied problem: smoothing the processes of attempted engagement, dis-engagement and re-engagement in various phases of conversation, doing so in a way that recognizes that not all attempts succeed.
We are applying machine learning techniques to the recognition of various forms of conversational engagement, using voice activity detection and prosodic cues rather than speech recognition. For example, we detect the schisming and merging of parallel conversations in group calls by finding patterns of voice activity that correlate with active turn-taking [1]. The system responds to these patterns by enhancing the intelligibility of talk within a given parallel conversation relative to the talk outside of it. As another example, we are currently working on methods to detect prosodic cues of engaging and dis-engaging talk [14]. Based on this information, the system can choose to alter selected properties of the audio channel in a manner that is consistent with the demonstrated behavior.
As a hypothetical example, evidence of dis-engagement (e.g., slowing of speech or of turn-taking) may result in a conversion of the channel from full-duplex to half-duplex push-to-talk, further slowing down turn-taking and thereby facilitating dis-engagement.
Clearly, this work does not address the forecasting of presence and availability directly.
However, when considered in light of the discussion in the previous section, we believe that it suggests interesting directions for user interfaces for availability-enhanced communication systems. For example, it suggests that one should work to smooth the process of escalating from asynchronous mechanisms (availability status indicators, away messages) to synchronous mechanisms (voice) -that integration in the form of (e.g.) a binary "click to talk" button in IM does not reflect the more continuous process of conversational engagement. Similarly, it suggests additional areas in which tight integration of availability forecasting and communication might be fruitful. For example, in our system, one could use forecasts as prior information in the assessment of a participant's desire for highly engaged talk.

CONCLUSION
In everyday life, the expression of availability is often an element of a social negotiation which is bound to situational, temporal and relationship contexts. This implies a number of considerations for designers of availability systems. These considerations further suggest some possible directions for improving the integration of availability and presence mechanisms with the communication mechanisms they support.


extfieldsofstudy:
Computer Science
Physics
Mathematics

text:
The logic of entanglement

We expose the information flow capabilities of pure bipartite entanglement as a theorem -- which embodies the exact statement on the `seemingly acausal flow of information' in protocols such as teleportation. We use this theorem to re-design and analyze known protocols (e.g. logic gate teleportation and entanglement swapping) and show how to produce some new ones (e.g. parallel composition of logic gates). We also show how our results extend to the multipartite case and how they indicate that entanglement can be measured in terms of `information flow capabilities'. Ultimately, we propose a scheme for automated design of protocols involving measurements, local unitary transformations and classical communication.

Introduction
Entanglement has always been a primal ingredient of fundamental research in quantum theory, and more recently, quantum computing. By studying it we aim at understanding the operational/physical significance of the use of the Hilbert space tensor product for the description of compound quantum systems. Many typical quantum phenomena are indeed due to compound quantum systems being described within the tensor product H 1 ⊗ H 2 and not within a direct sum H 1 ⊕ H 2 .
In this paper we reveal a new structural ingredient of the supposedly well-understood pure bipartite entanglement, that is, we present a new theorem about the tensor product of Hilbert spaces. It identifies a 'virtual flow of information' in so-called entanglement specification networks. For example, it is exactly this flow of information which embodies teleporting [6] an unknown state from one physical carrier to another. Furthermore, our theorem (nontrivially) extends to multipartite entanglement. We also argue that it provides a new way of conceiving entanglement itself and hence of measuring entanglement: entanglement ≡ information flow capabilities Indeed, our result enables reasoning about quantum information flow without explicitly considering classical information flow -this despite the impossibility of transmitting quantum information through entanglement without the use of a classical channel.
Using our theorem we can evidently reconstruct protocols such as logic gate teleportation [10] and entanglement swapping [15]. It moreover allows smooth generation of new protocols, of which we provide an exam-ple, namely the conversion of accumulation of inaccuracies causing 'sequential composition' into fault-tolerant 'parallel composition' [13]. Indeed, when combing our new insights on the flow of information through entanglement with a model for the flow of classical information we obtain a powerful tool for designing protocols involving entanglement.
An extended version of this paper is available as a research report [9]. It contains details of proofs, other/larger pictures, other references, other applications and some indications of connections with logic, proof theory and functional programming.

Classical information flow
By the spectral theorem any non-degenerated measurement on a quantum system described in a ndimensional complex Hilbert space H has the shape M = x 1 · P 1 + . . . + x n · P n .
Since the values x 1 , . . . , x n can be conceived as merely being tokens distinguishing the projectors P 1 , . . . , P n in the above sum we can abstract over them and conceive such a measurement as a set M ≃ {P 1 , . . . , P n } of n mutually orthogonal projectors which each project on a one-dimensional subspace of H. Hence, by von Neumann's projection postulate, a measurement can be conceived as the system being subjected to an action P i and the observer being informed about which action happened (e.g. by receiving the token x i ).
In most quantum information protocols the indeterminism of measurements necessitates a flow of classical information e.g. the 2-bit classical channel required for teleportation [6]. We want to separate this classical information flow from what we aim to identify as the quantum information flow. Consider a protocol involving local unitary operations, (non-local) measurements and classical communication e.g. teleportation: We can decompose such a protocol in 1. a tree with the consecutive operations as nodes, and, in case of a measurement, the emerging branches being labeled by tokens representing the projectors; 2. the configuration of the operations in terms of the time when they are applied and the subsystem to which they apply.
Hence we abstract over spatial dynamics. The nodes in the tree are connected to the boxes in the configuration picture by their temporal coincidence. For teleportation we thus obtain Classical communication is encoded in the tree as the dependency of operations on the labels on the branches below it e.g. the dependency of the operation U xz on the variable xz stands for the 2-bit classical channel required for teleportation. We will also replace any initial state Ψ by the projector P Ψ on it, which can be conceived as its preparation e.g. P EPR is the preparation of an EPR-pair. It should be clear that for each path from the root of the tree to a leaf, by 'filling in the operations on the included nodes in the corresponding boxes of the configuration picture', we obtain a network involving only local unitary operations and (non-local) projectors e.g. one network P EPR

Pxz
Uxz for each of the four values xz takes. It will be these networks (from which we extracted the classical information flow) for which we will reveal the quantum information flow. Hence each projector in it which is not a preparation is to be conceived conditionally.

Bipartite entanglement
where (m αβ ) αβ is the matrix of the corresponding function in bases {e (1) α } α and {e We can now represent the states of H 1 ⊗ H 2 by functions in H 1 → H 2 or in H 1 H 2 , and vice versa, these functions represent states of H 1 ⊗ H 2 . Omitting normalization constants, an attitude we will abide by throughout this paper, examples of linear maps encoding states are: These four functions which encode the Bell-base states are almost the Pauli matrices plus the identity which itself encodes the EPR-state. We can also encode each projector Hence we can use these (linear or antilinear) functional labels both to denotate the states of H 1 ⊗H 2 and the projectors on elements of H 1 ⊗H 2 . We introduce a graphical notation which incarnates this. Hence the projector f acts on the multipartite state represented by and produces a pure tensor consisting of (up to a normalization constant) f and some remainder. Hence this picture portrays 'preparation of the f -labeled state'.
By an entanglement specification network we mean a collection of bipartite projectors f 'configured in space and time' e.g.
The arrows indicate which of the two Hilbert spaces in H 1 ⊗ H j is the domain and which is the codomain of the labeling function. Such a network can also contain local unitary operations -which we will represent by a grey square box U . We will refer to the lines labeled by some Hilbert space H i (≃ time-lines) as tracks. The notion of a path allows us to make certain predictions about the output Ψ out of a network, that is, the state of the whole system after all projectors have been effectuated. Before stating the theorem we illustrate it on our example. Let be its input state. This input state factors into the pure factor φ in , which we call the input of the path, and a remainder.
It should be clear that after effectuating all projectors we end up with an output which factors in the bipartite state labeled by f 1 , the bipartite state labeled by f 2 and a remaining pure factor φ out -which we call the output of the path. Our theorem (below) predicts that Be aware of the fact that the functions f 1 , . . . , f 8 are not physical operations but labels obtained via a purely mathematical isomorphism. Moreover, the order in which they appear in the composite (1) has no obvious relation to the temporal order of the corresponding projectors. Their order in the composite (1) is: the order in which the path passes through them -this despite the fact that the path goes both forward and backward in physical time. Here's the theorem.
Proof: Straightforward verification or see [9] §5.1. 2 Theorem 3.3 (i) Given are an entanglement specification network and a path. Assume that : 1. The order in which the path passes through the projectors is 2. The input of the path is a pure factor φ in .
3. Ψ out has a non-zero amplitude.
Then the output of the path is (indeed) a pure factor φ out which is explicitly given by (ii) If the path passes forwardly through U then U will be part of the composite (2) and if it passes backwardly through U then U † will be part of the composite (2).
Proof: Lemma 3.2 is the crucial lemma for the proof. For a full proof see [9] §5. 2 It might surprise the reader that in the formulation of Theorem 3.3 we didn't specify whether f 1 , . . . , f k are either linear or anti-linear, and indeed, we slightly cheated. The theorem is only valid for f 1 , . . . , f k antilinear. However, in the case that f 1 , . . . , f k are linear, in order to make the theorem hold it suffices to conjugate the matrix elements of those functional labels for which the path enters (and leaves) the corresponding projector 'from below' (see [9] §4.1): In most practical examples these matrix elements are real (see below) and hence the above theorem also holds for linear functional labels. One also verifies that if a path passes though a projector in the opposite direction of the direction of an anti-linear functional label f , then we have to use the adjoint f † of the anti-linear map f in the composite (2) -the matrix of the adjoint of an anti-linear map f † is the transposed of the matrix of f (see [9] §4.2). Finally note that we did not specify that at its input a path should be directed forwardly in physical time, and indeed, the theorem also holds for paths such as We discuss this in Section 5.
due to (id • id)(φ) = φ. When conceiving the first projector as the preparation of an EPR-pair while tilting the tracks we indeed obtain 'a' teleportation protocol. However, the other projector has to 'belong to a measurement' e.g. M Bell := {P id , P π , P id * , P π * }. Hence the above introduced protocol is a conditional one. We want to make it unconditional.
Definition 4.1 Paths are equivalent iff for each input φ in they produce the same output φ out . Proof: Intuitively, one can move the box U † along the path and permute it with projectors whose functional labels commute with U (= commute with U † ) until it gets annihilated by the U -factor of U • f . Applying Corollary 4.2 to f, g := id and U ∈ {id, π, id * , π * } , since π † = π, (id * ) † = id * and (π * ) † = −π * , we obtain four conditional teleportation protocols of which the one with U := id coincides with (3). These four together constitute an unconditional teleportation protocol since they correspond to the four paths 'from root to leaf' of the tree discussed in Section 2, from which then also the 2-bit classical channel emerges. In order to obtain the teleportation protocol as it is found in the literature, observe that π * = π •id * , hence • id id * id id id * π π π * and thus we can factor -with respect to composition of functional labels -the 2-bit Bell-base measurement in two 1-bit 'virtual' measurements (∨ stands for 'or'): id∨id * id∨π id∨π∨id * ∨π * ≃ 2 bits 1 bit 1 bit Note that such a decomposition of M Bell does not exist with respect to ⊗ nor does it exist with respect to composition of projector actions. All this results in id id∨id * id∨π id∨π id∨id * which is the standard teleportation protocol [6].
The aim of logic gate teleportation [10] is to teleport a state and at the same time subject it to the action of a gate f . By Theorem 3.3 we evidently have We make this protocol unconditional analogously as we did it for ordinary teleportation. Proof: Analogous to that of Corollary 4.3. 2 We apply the above to the case f := id ⊗ id and g := CNOT that is, the first projector is now to be conceived as the preparation of the state Proof: The first claim is verified straightforwardly.
Hence we can factor the 4-qubit measurement to which the second projector belongs in two Bell-base measurements, that is, we set The resulting protocol is the one to be found in [10] -recall that U † factors as a tensor since CNOT is a member of the Clifford group.
Our last example in this section involves the passage from sequential to parallel composition of logic gates. Due to the accumulation of inaccuracies in sequential composition [13] it would be desirable to have a fault-tolerant parallel alternative. This would for example be useful if we have a limited set of available gates from which we want to generate more general ones e.g. generating all Clifford group gates from CNOT gates, Hadamard gates and phase gates via tensor and composition. By Theorem 3.3 the network

Entanglement swapping
However, Theorem 3.3 assumes φ in to be a pure factor while it is part of the output Ψ out of the network. This fact constraints the network by requiring that for some φ in and φ out i.e. the state labeled by h • g • f has to be disentangled -which is equivalent to the range of h • g • f being one-dimensional [9] §5.3.
Using Lemma 3.2 this pathology can be overcome by conceiving the output state of the bipartite subsystem described in H 1 ⊗ H 4 not as a pair (φ in , φ out ) but as a function ϕ : H 1 H 4 which relates any input φ in ∈ H 1 to an output φ out := ϕ(φ in ) ∈ H 4 . Hence we conceive the above network as producing a function To such a function produced by a network we can provide an input via a unipartite projector. The generic example (which can be easily verified) is One can then conceive f as a λ-term λφ.f φ [5] and the process of providing it with an input via a unipartite projector embodies the β-reduction [5] (λφ.f φ)φ in β = f (φ in ) .
As we will see below we can 'feed' such a function at its turn as an input of function type in another network. This view carries over to the interpretation of multipartite entanglement where it becomes crucial.
The entanglement swapping protocol [15] can now be derived analogously as the teleportation protocol by setting f = g = h := id in the above. For this particular case Lemma 3.2 becomes Details can be found in [9] §6.2.

Multipartite entanglement
The passage from states to functions as inputs and outputs enables to extend our functional interpretation of bipartite entanglement to one for multipartite entanglement. In general this involves higher order functions and hence the use of denotational tools from modern logic and proof theory such as λ-calculus [1,5]. Whereas (due to commutativity of − ⊗ −) a bipartite tensor H 1 ⊗ H 2 admits interpretation as a function either of type H 1 H 2 or of type H 1 H 2 , a tripartite tensor (due to associativity of − ⊗ −) admits interpretation as a function of a type within the union of two (qualitatively different) families of types namely Explicitly, given we respectively obtain :: We illustrate this in an example -we will not provide an analogue to Theorem 3.3 for the multipartite case since even its formulation requires advanced denotational tools. Consider the following configuration. For 'good' types we can draw a 'compound' path.
To verify this we explicitly calculate φ out α8 . Set where Ψ 0 is the (essentially arbitrary) input of the network and Ψ τ for τ ∈ {1, 2, 3, 4} is the state at time τ + ǫ. For I ⊆ {1, . . . , 8} and I c := {1, . . . , 8} \ I let P I Φ stipulate that this projector projects on the subspace where i 1 . . . i 8 [j α /i α | α ∈ I] denotes that for α ∈ I we substitute the index i α by the index j α which ranges over the same values as i α .
Proof: Straightforward verification or see [9] §6.4. 2 Using Lemma 6.1 one verifies that the resulting state Ψ 4 i1...i8 factors into five components, one in which no index in {i 1 , . . . , i 8 } appears, three with indices in {i 1 , . . . , i 7 } and one which contains the index i 8 namely l4l5l6l7 m1m2m3 Substituting the indices m 1 , m 2 , m 3 , l 4 , l 5 , l 6 , l 7 , i 8 by α 1 , . . . , α 8 we exactly obtain our prediction for φ out α8 . It should be clear from our discussion of multipartite entanglement that, provided we have an appropriate entangled state involving a sufficient number of qubits, we can implement arbitrary (linear) λ-terms [1,5].

Discussion
For a unitary operation U : H → H there is a flow of information from the input to the output of U in the sense that for an input state φ the output U (φ) fully depends on φ.

U(φ)
How does a projector P ψ act on states? After renormalization and provided that φ | ψ = 0 the input state φ is not present anymore in the output ψ = P ψ (φ). At first sight this seems to indicate that through projectors on one-dimensional subspaces there cannot be a flow of information cfr. the 'wall' in the picture below. While there cannot be a flow from the input to the output, there is a 'virtual flow' between the two inputs and the two outputs of a bipartite projector whenever it is configured within an appropriate context. And such a bipartite projector on a state in H 1 ⊗ H 2 can act on this flow as any (anti-)linear function f with domain in H 1 and codomain in H 2 -which is definitely more general than unitary operations and also more general than actions by (completely) positive maps. This behavioral interpretation extends to multipartite entanglement, and, as is shown in [9] §6.6, it also enables interpretation of non-local unitary operations.
The wall within a projector incarnates the fact that Indeed, one verifies that disentangled states ψ⊗φ are in bijective correspondence with those linear maps which have a one-dimensional range [9] §5.3, that is, since states correspond to one-dimensional subspaces, disentangled states correspond to (partial) constant maps on states. Since constant maps incarnate the absence of information flow (cfr. 'the wall' mentioned above): Pursuing this line of thought of conceiving entanglement in terms of its information flow capabilities yields a proposal for measuring pure multipartite entanglement [9] §7.5 -given a measure for pure bipartite entanglement e.g. majorization [11].
The use of Theorem 3.3 in Sections 4 and 5 hints towards automated design of general protocols involving entanglement. We started with a simple configuration which conditionally incarnates the protocol we want to implement. Conceiving this conditional protocol as a pair consisting of (i) a single path 'from root to leaf' in a tree, and, (ii) a configuration picture, we can extend the tree and the configuration picture with unitary corrections in order to obtain an unconditional protocol. It constitutes an interesting challenge to produce an explicit algorithm which realizes this given an appropriate front-end design language.
Elaborating on the results in [2] S. Abramsky and the author have produced an axiomatic characterization of the in this paper exposed behavioral properties of quantum entanglement with respect to information flow. Remarkably, the additive feature of a vector space which gives rise to the notion of superposition and hence to that of entanglement itself seems not to be crucial with respect to the quantum-flow! In particular, we obtain a similar information-flow as the one enabled by quantum entanglement when replacing 'vector space' by 'set', 'linear map' by 'relation' and 'tensor product' by 'cartesian product' [3]. Replacing 'linear map' by 'function' in stead of 'relation' would not enable such an information flow. This is due to a different categorical status [4,12] of the cartesian product in the category of sets and relations as compared to its status in the category of sets and functions. The category of relations does fail to have a full teleportation protocol because it has no four-vector Bell-base [3].
Recent proposals for fault-tolerant quantum computers of which the architecture is manifestly different from the circuit model require a different mathematical setting for programming them and reasoning about them [8]. We are convinced that the insights obtained in this paper provide the appropriate tool for doing so.


Mining New Word Translations from Comparable Corpora

New words such as names, technical terms, etc appear frequently. As such, the bilingual lexicon of a machine translation system has to be constantly updated with these new word translations. Comparable corpora such as news documents of the same period from different news agencies are readily available. In this paper, we present a new approach to mining new word translations from comparable corpora, by using context information to complement transliteration information. We evaluated our approach on six months of Chinese and English Gigaword corpora, with encouraging results.

Introduction
New words such as person names, organization names, technical terms, etc. appear frequently. In order for a machine translation system to translate these new words correctly, its bilingual lexicon needs to be constantly updated with new word translations.
Much research has been done on using parallel corpora to learn bilingual lexicons (Melamed, 1997;Moore, 2003). But parallel corpora are scarce resources, especially for uncommon language pairs. Comparable corpora refer to texts that are not direct translation but are about the same topic. For example, various news agencies report major world events in different languages, and such news documents form a readily available source of comparable corpora. Being more readily available, comparable corpora are thus more suitable than parallel corpora for the task of acquiring new word translations, although relatively less research has been done in the past on comparable corpora. Previous research efforts on acquiring translations from comparable corpora include (Fung and Yee, 1998;Rapp, 1995;Rapp, 1999).
When translating a word w, two sources of information can be used to determine its translation: the word w itself and the surrounding words in the neighborhood (i.e., the context) of w. Most previous research only considers one of the two sources of information, but not both. For example, the work of (Al-Onaizan and Knight, 2002a;Al-Onaizan and Knight, 2002b;Knight and Graehl, 1998) used the pronunciation of w in translation. On the other hand, the work of (Cao and Li, 2002;Fung and Yee, 1998;Koehn and Knight, 2002;Rapp, 1995;Rapp, 1999) used the context of w to locate its translation in a second language.
In this paper, we propose a new approach for the task of mining new word translations from comparable corpora, by combining both context and transliteration information. Since both sources of information are complementary, the accuracy of our combined approach is better than the accuracy of using just context or transliteration information alone. We fully implemented our method and tested it on Chinese-English comparable corpora. We translated Chinese words into English. That is, Chinese is the source language and English is the target language. We achieved encouraging results.
While we have only tested our method on Chinese-English comparable corpora, our method is general and applicable to other language pairs.

Our approach
The work of (Fung and Yee, 1998;Rapp, 1995;Rapp, 1999) noted that if an English word e is the translation of a Chinese word c , then the contexts of the two words are similar. We could view this as a document retrieval problem. The context (i.e., the surrounding words) of c is viewed as a query. The context of each candidate translation ' e is viewed as a document. Since the context of the correct translation e is similar to the context of c , we are likely to retrieve the context of e when we use the context of c as the query and try to retrieve the most similar document. We employ the language modeling approach (Ng, 2000;Ponte and Croft, 1998) for this retrieval problem. More details are given in Section 3.
On the other hand, when we only look at the word w itself, we can rely on the pronunciation of w to locate its translation. We use a variant of the machine transliteration method proposed by (Knight and Graehl, 1998). More details are given in Section 4.
Each of the two individual methods provides a ranked list of candidate words, associating with each candidate a score estimated by the particular method. If a word e in English is indeed the translation of a word c in Chinese, then we would expect e to be ranked very high in both The candidate e i that is ranked the highest according to the average rank is taken to be the correct translation and is output. If no words appear within the top M positions in both lists, then no translation is output.
Since we are using comparable corpora, it is possible that the translation of a new word does not exist in the target corpus. In particular, our experiment was conducted on comparable corpora that are not very closely related and as such, most of the Chinese words have no translations in the English target corpus.

Translation by context
In a typical information retrieval (IR) problem, a query is given and a ranked list of documents most relevant to the query is returned from a document collection.
For our task, the query is Within IR, there is a new approach to document retrieval called the language modeling approach (Ponte & Croft,98). In this approach, a language model is derived from each document D . Then the probability of generating the query Q according to that language model, ) is the one that best matches the query. The language modeling approach to IR has been shown to give superior retrieval performance (Ponte & Croft, 98;Ng, 2000), compared with traditional vector space model, and we adopt this approach in our current work.
To estimate ) | ( D Q P , we use the approach of (Ng, 2000). We view the document D as a multinomial distribution of terms and assume that query Q is generated by this model: where t is a term in the corpus, t c is the number of times term t occurs in the query Q , is the total number of terms in query Q .
For ranking purpose, the first fraction can be omitted as this part depends on the query only and thus is the same for all the documents. In our translation problem, ) (c C is viewed as the query and ) (e C is viewed as a document. So our task is to compute English word e and find the e that gives the is the bag of Chinese words obtained by translating the English words in ) (e C , as determined by a bilingual dictionary. If an English word is ambiguous and has K translated Chinese words listed in the bilingual dictionary, then each of the K translated Chinese words is counted as occurring 1/K times in )) ( ( e C T c for the purpose of probability estimation.
We use backoff and linear interpolation for probability estimation: , and ) ( c ml t P is estimated similarly by counting the occurrences of c t in the Chinese translation of the whole English corpus. α is set to 0.6 in our experiments.

Translation by transliteration
For the transliteration model, we use a modified model of (Knight and Graehl, 1998) and (Al-Onaizan and Knight, 2002b). Knight and Graehl (1998) proposed a probabilistic model for machine transliteration. In this model, a word in the target language (i.e., English in our task) is written and pronounced. This pronunciation is converted to source language pronunciation and then to source language word (i.e., Chinese in our task). Al-Onaizan and Knight (2002b) suggested that pronunciation can be skipped and the target language letters can be mapped directly to source language letters.
Pinyin is the standard Romanization system of Chinese characters. It is phonetic-based. For transliteration, we estimate ) | ( c e P as follows: First, each Chinese character in a Chinese word c is converted to pinyin form. Then we sum over all the alignments that this pinyin form of c can map to an English word e. For each possible alignment, we calculate the probability by taking the product of each mapping. i p is the ith syllable of pinyin, a i l is the English letter sequence that the ith pinyin syllable maps to in the particular alignment a. Since most Chinese characters have only one pronunciation and hence one pinyin form, we assume that Chinese character-to-pinyin mapping is one-to-one to simplify the problem. We use the expectation maximization (EM) algorithm to generate mapping probabilities from pinyin syllables to English letter sequences. To reduce the search space, we limit the number of English letters that each pinyin syllable can map to as 0, 1, or 2. Also we do not allow cross mappings. That is, if an English letter sequence 1 e precedes another English letter sequence 2 e in an English word, then the pinyin syllable mapped to 1 e must precede the pinyin syllable mapped to 2 e .
Our method differs from (Knight and Graehl, 1998) and (Al-Onaizan and Knight, 2002b)  We used a Chinese-English dictionary which contained about 10,000 entries for translating the words in the context. For the training of transliteration probability, we required a Chinese-English name list. We used a list of 1,580 Chinese-English name pairs as training data for the EM algorithm.

Preprocessing
Unlike English, Chinese text is composed of Chinese characters with no demarcation for words. So we first segmented Chinese text with a Chinese word segmenter that was based on maximum entropy modeling (Ng and Low, 2004). We then divided the Chinese corpus from Jul to Dec 1995 into 12 periods, each containing text from a half-month period. Then we determined the new Chinese words in each half-month period p. By new Chinese words, we refer to those words that appeared in this period p but not from Jan to Jun 1995 or any other periods that preceded p. Among all these new words, we selected those occurring at least 5 times. These words made up our test set. We call these words Chinese source words. They were the words that we were supposed to find translations from the English corpus.
For the English corpus, we performed sentence segmentation and converted each word to its morphological root form and to lower case.
We also divided the English corpus into 12 periods, each containing text from a half-month period. For each period, we selected those English words occurring at least 10 times and were not present in the 10,000-word Chinese-English dictionary we used and were not stop words. We considered these English words as potential translations of the Chinese source words. We call them English translation candidate words. For a Chinese source word occurring within a halfmonth period p, we looked for its English translation candidate words occurring in news documents in the same period p.

Translation candidates
The context ) (c C of a Chinese word c was collected as follows: For each occurrence of c, we set a window of size 50 characters centered at c. We discarded all the Chinese words in the context that were not in the dictionary we used. The contexts of all occurrences of a word c were then concatenated together to form ) (c C . The context of an English translation candidate word e, ) (e C , was similarly collected. The window size of English context was 100 words.
After all the counts were collected, we estimated )) ( | ) ( ( e C c C P as described in Section 3, for each pair of Chinese source word and English translation candidate word. For each Chinese source word, we ranked all its English translation candidate words according to the estimated For each Chinese source word c and an English translation candidate word e , we also calculated the probability ) | ( c e P (as described in Section 4), which was used to rank the English candidate words based on transliteration.
Finally, the English candidate word with the smallest average rank position and that appears within the top M positions of both ranked lists is the chosen English translation (as described in Section 2). If no words appear within the top M positions in both ranked lists, then no translation is output.
Note that for many Chinese words, only one In Table 1, period 1 is Jul 01 -Jul 15, period 2 is Jul 16 -Jul 31, …, period 12 is Dec 16 -Dec 31. #c is the total number of new Chinese source words in the period. #e is the total number of English translation candidates in the period. #o is the total number of output English translations. #Cor is the number of correct English translations output. Prec. is the precision. The correctness of the English translations was manually checked.
Recall is somewhat difficult to estimate because we do not know whether the English translation of a Chinese word appears in the English part of the corpus. We attempted to estimate recall by manually finding the English translations for all the Chinese source words for the two periods Dec 01 -Dec 15 and Dec 16 -Dec 31 in the English part of the corpus. During the whole December period, we only managed to find English translations which were present in the English side of the comparable corpora for 43 Chinese words. = .
We also investigated the effect of varying M .
The results are shown in Table 2.

M
The past research of (Fung and Yee, 1998;Rapp, 1995;Rapp, 1999) utilized context information alone and was evaluated on different corpora from ours, so it is difficult to directly compare our current results with theirs. Similarly, Al-Onaizan and Knight (2002a;2002b) only made use of transliteration information alone and so was not directly comparable.
To investigate the effect of the two individual sources of information (context and transliteration), we checked how many translations could be found using only one source of information (i.e., context alone or transliteration alone), on those Chinese words that have translations in the English part of the comparable corpus. As mentioned earlier, for the month of Dec 1995, there are altogether 43 Chinese words that have their translations in the English part of the corpus. This list of 43 words is shown in Table 3. 8 of the 43 words are translated to English multi-word phrases (denoted as "phrase" in Table 3). Since our method currently only considers unigram English words, we are not able to find translations for these words. But it is not difficult to extend our method to handle this problem. We can first use a named entity recognizer and noun phrase chunker to extract English names and noun phrases.
The translations of 6 of the 43 words are words in the dictionary (denoted as "comm." in Table 3) and 4 of the 43 words appear less than 10 times in the English part of the corpus (denoted as "insuff"). Our method is not able to find these translations. But this is due to search space pruning. If we are willing to spend more time on searching, then in principle we can find these translations. 'NA' means the word cannot be transliterated. 'insuff' means the correct translation appears less than 10 times in the English part of the comparable corpus. 'comm' means the correct translation is a word appearing in the dictionary we used or is a stop word. 'phrase' means the correct translation contains multiple English words.
As shown in Table 3, using just context information alone, 10 Chinese words (the first 10) have their correct English translations at rank one position. And using just transliteration information alone, 9 Chinese words have their correct English translations at rank one position.
On the other hand, using our method of combining both sources of information and setting M = ∞, 19 Chinese words (i.e., the first 22 Chinese words in Table 3 except 巴佐亚,坩埚,普利法) have their correct English translations at rank one position. If M = 10, 15 Chinese words (i.e., the first 19 Chinese words in Table 3 except 叶玛斯,巴佐亚,坩埚,普利法) have their correct English translations at rank one position. Hence, our method of using both sources of information outperforms using either information source alone.

Related work
As pointed out earlier, most previous research only considers either transliteration or context information in determining the translation of a source language word w, but not both sources of information. For example, the work of (Al-Onaizan and Knight, 2002a;Al-Onaizan and Knight, 2002b;Knight and Graehl, 1998) used only the pronunciation or spelling of w in translation. On the other hand, the work of (Cao and Li, 2002;Fung and Yee, 1998;Rapp, 1995;Rapp, 1999) used only the context of w to locate its translation in a second language. In contrast, our current work attempts to combine both complementary sources of information, yielding higher accuracy than using either source of information alone. Koehn and Knight (2002) attempted to combine multiple clues, including similar context and spelling. But their similar spelling clue uses the longest common subsequence ratio and works only for cognates (words with a very similar spelling).
The work that is most similar to ours is the recent research of (Huang et al., 2004). They attempted to improve named entity translation by combining phonetic and semantic information. Their contextual semantic similarity model is different from our language modeling approach to measuring context similarity. It also made use of part-of-speech tag information, whereas our method is simpler and does not require part-ofspeech tagging. They combined the two sources of information by weighting the two individual scores, whereas we made use of the average rank for combination.

Conclusion
In this paper, we proposed a new method to mine new word translations from comparable corpora, by combining context and transliteration information, which are complementary sources of information. We evaluated our approach on six months of Chinese and English Gigaword corpora, with encouraging results.