Reviews: Question Asking as Program Generation

The authors examine human question asking where answers are K-ary. They define by hand a PCFG for a "battleship" domain, where there are hidden colored shapes in a partially observable grid (i.e., some tiles are revealed as containing part of a ship of a specific color or being empty). The task of the agent is to ask a question with a single word answer that provides as much information about the state of the board. The PCFG served as a prior over questions, which were defined as statements in lambda calculus. Question goodness was defined as a linear function of its informativeness (expected information gain), its complexity (in terms of its length or negative log probability under of it being generated by the PCFG with a uniform distribution over rewrite rules), and "answer type" (e.g., whether it provides a true/false or color as an answer).