Partial Or Complete, That’s The Question

Proceedings of NAACL-HLT 2019, pages 2190–2200 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 2190 Partial Or Complete, That Is The Question Qiang Ning,1 Hangfeng He,2 Chuchu Fan,1 Dan Roth1,2 1Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign 2Department of Computer and Information Science, University of Pennsylvania {qning2,cfan10}@illinois.edu, {hangfeng,danroth}@seas.upenn.edu Abstract For many structured learning tasks, the data annotation process is complex and costly. Ex- isting annotation schemes usually aim at ac- quiring completely annotated structures, under the common perception that partial structures are of low quality and could hurt the learn- ing process. This paper questions this common perception, motivated by the fact that struc- tures consist of interdependent sets of vari- ables. Thus, given a fixed budget, partly an- notating each structure may provide the same level of supervision, while allowing for more structures to be annotated. We provide an in- formation theoretic formulation for this per- spective and use it, in the context of three di- verse structured learning tasks, to show that learning from partial structures can sometimes outperform learning from complete ones. Our findings may provide important insights into structured data annotation schemes and could support progress in learning protocols for structured tasks. 1 Introduction Many machine learning tasks require structured outputs, and the goal is to assign values to a set of variables coherently. Specifically, the variables in a structure need to satisfy some global properties required by the task. An important implication is that once some variables are determined, the val- ues taken by other variables are constrained. For instance, in the temporal relation extraction prob- lem in Fig. 1a, if met happened before leaving and leaving happened on Thursday, then we know that met must either be before Thursday (“met (1)”) or has to happen on Thursday, too (“met (2)”) (Ning et al., 2018a). Similarly, in the semantic frame of the predicate gave (Kingsbury and Palmer, 2002) in Fig. 1b, if the boy is ARG0 (short for argu- ment 0), then it rules out the possibility of a frog met (2) leaving met (1) Thursday Time I met with him before leaving for Paris on Thursday. (a) The boy gave a frog to the girl. Arg0 Arg0 Arg0 PREDICATE (b) ! FOREHEAD ! LEFT_EYE ! TORSO ! (c) NECK Before Be_Included Figure 1: Due to the inherent structural constraints of each task, individual instances therein put restric- tions on others. (a) The temporal relation between met and Thursday has to be BEFORE (“met (1)”) or BE INCLUDED (“met (2)”). (b) The argument roles of a frog and to the girl cannot be ARG0 anymore. (c) Given the position of the cat’s FOREHEAD and LEFT EYE, a rough estimate of its NECK can be the red solid box rather than the blue dashed box. or to the girl taking the same role. Figure 1c fur- ther shows an example of part-labeling of images (Choi et al., 2018); given the position of FORE- HEAD and LEFT EYE …

Content truncated to 500 words