We propose a general method to watermark and probabilistically identify the structured outputs of machine learning algorithms. Our method is robust to local editing operations and provides well defined trade-offs between the ability to identify algorithm outputs and the quality of the watermarked output. Unlike previous work in the field, our approach does not rely on controlling the inputs to the algorithm and provides probabilistic guarantees on the ability to identify collections of results from one's own algorithm. We present an application in statistical machine translation, where machine translated output is watermarked at minimal loss in translation quality and detected with high recall. Machine learning algorithms provide structured results to input queries by simulating human behavior. Examples include automatic machine translation (Brown et al., 1993) or automatic text and rich media summarization (Goldstein et al., 1999) . These algorithms often estimate some portion of their models from publicly available human generated data. As new services that output structured results are made available to the public and the results disseminated on the web, we face a daunting new challenge: Machine generated structured results contaminate the pool of naturally generated human data. For example, machine translated output and human generated translations are currently both found extensively on the web, with no automatic way of distinguishing between them. Algorithms that mine data from the web (Uszkoreit et al., 2010), with the goal of learning to simulate human behavior, will now learn models from this contaminated and potentially selfgenerated data, reinforcing the errors committed by earlier versions of the algorithm. It is beneficial to be able to identify a set of encountered structured results as having been generated by one's own algorithm, with the purpose of filtering such results when building new models. Problem Statement: We define a structured result of a query q as r = {z 1 · · · z L } where the order and identity of elements z i are important to the quality of the result r. The structural aspect of the result implies the existence of alternative results (across both the order of elements and the elements themselves) that might vary in their quality. Given a collection of N results, C N = r 1 · · · r N , where each result r i has k ranked alternatives D k (q i ) of relatively similar quality and queries q 1 · · · q N are arbitrary and not controlled by the watermarking algorithm, we define the watermarking task as: Task. Replace r i with r i ∈ D k (q i ) for some subset of results in C N to produce a watermarked collection C N such that: • C N is probabilistically identifiable as having been generated by one's own algorithm. 1363
REF propose a method to watermark the output of machine translation systems to aid this distinction.
Watermarking the Outputs of Structured Prediction with an application in Statistical Machine Translation.
EMNLP
Computer Science