Bias reformulation for one-shot function induction
In recent years predicate invention has been underexplored as a bias reformulation mechanism within Inductive Logic Programming due to difficulties in formulating efficient search mechanisms. However, recent papers on a new approach called Meta-Interpretive Learning have demonstrated that both predi...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
IOS Press
2016
|
| Online Access: | http://hdl.handle.net/1721.1/102524 https://orcid.org/0000-0003-4926-6275 https://orcid.org/0000-0002-1925-2035 https://orcid.org/0000-0001-5814-3264 |
| _version_ | 1811081831182761984 |
|---|---|
| author | Lin, Dianhuan Dechter, Eyal Ellis, Kevin M. Tenenbaum, Joshua B. Muggleton, Stephen H. |
| author2 | Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences |
| author_facet | Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences Lin, Dianhuan Dechter, Eyal Ellis, Kevin M. Tenenbaum, Joshua B. Muggleton, Stephen H. |
| author_sort | Lin, Dianhuan |
| collection | MIT |
| description | In recent years predicate invention has been underexplored as a bias reformulation mechanism within Inductive Logic Programming due to difficulties in formulating efficient search mechanisms. However, recent papers on a new approach called Meta-Interpretive Learning have demonstrated that both predicate invention and learning recursive predicates can be efficiently implemented for various fragments of definite clause logic using a form of abduction within a meta-interpreter. This paper explores the effect of bias reformulation produced by Meta-Interpretive Learning on a series of Program Induction tasks involving string transformations. These tasks have real-world applications in the use of spreadsheet technology. The existing implementation of program induction in Microsoft's FlashFill (part of Excel 2013) already has strong performance on this problem, and performs one-shot learning, in which a simple transformation program is generated from a single example instance and applied to the remainder of the column in a spreadsheet. However, no existing technique has been demonstrated to improve learning performance over a series of tasks in the way humans do. In this paper we show how a functional variant of the recently developed MetagolD system can be applied to this task. In experiments we study a regime of layered bias reformulation in which size-bounds of hypotheses are successively relaxed in each layer and learned programs re-use invented predicates from previous layers. Results indicate that this approach leads to consistent speed increases in learning, more compact definitions and consistently higher predictive accuracy over successive layers. Comparison to both FlashFill and human performance indicates that the new system, MetagolDF, has performance approaching the skill level of both an existing commercial system and that of humans on one-shot learning over the same tasks. The induced programs are relatively easily read and understood by a human programmer. |
| first_indexed | 2024-09-23T11:53:09Z |
| format | Article |
| id | mit-1721.1/102524 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:53:09Z |
| publishDate | 2016 |
| publisher | IOS Press |
| record_format | dspace |
| spelling | mit-1721.1/1025242022-10-01T06:42:39Z Bias reformulation for one-shot function induction Lin, Dianhuan Dechter, Eyal Ellis, Kevin M. Tenenbaum, Joshua B. Muggleton, Stephen H. Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences Lin, Dianhuan Dechter, Eyal Ellis, Kevin M. Tenenbaum, Joshua B. In recent years predicate invention has been underexplored as a bias reformulation mechanism within Inductive Logic Programming due to difficulties in formulating efficient search mechanisms. However, recent papers on a new approach called Meta-Interpretive Learning have demonstrated that both predicate invention and learning recursive predicates can be efficiently implemented for various fragments of definite clause logic using a form of abduction within a meta-interpreter. This paper explores the effect of bias reformulation produced by Meta-Interpretive Learning on a series of Program Induction tasks involving string transformations. These tasks have real-world applications in the use of spreadsheet technology. The existing implementation of program induction in Microsoft's FlashFill (part of Excel 2013) already has strong performance on this problem, and performs one-shot learning, in which a simple transformation program is generated from a single example instance and applied to the remainder of the column in a spreadsheet. However, no existing technique has been demonstrated to improve learning performance over a series of tasks in the way humans do. In this paper we show how a functional variant of the recently developed MetagolD system can be applied to this task. In experiments we study a regime of layered bias reformulation in which size-bounds of hypotheses are successively relaxed in each layer and learned programs re-use invented predicates from previous layers. Results indicate that this approach leads to consistent speed increases in learning, more compact definitions and consistently higher predictive accuracy over successive layers. Comparison to both FlashFill and human performance indicates that the new system, MetagolDF, has performance approaching the skill level of both an existing commercial system and that of humans on one-shot learning over the same tasks. The induced programs are relatively easily read and understood by a human programmer. National Science Foundation (U.S.) (STC Center for Brains, Minds and Machines Award CCF-1231216) 2016-05-18T14:56:09Z 2016-05-18T14:56:09Z 2014 Article http://purl.org/eprint/type/ConferencePaper 978-1-61499-419-0-525 http://hdl.handle.net/1721.1/102524 Dianhuan, Lin, Dechter Eyal, Ellis Kevin, Tenenbaum Joshua, and Muggleton Stephen. “Bias Reformulation for One-Shot Function Induction.” Frontiers in Artificial Intelligence and Applications, 2014, 525–530. https://orcid.org/0000-0003-4926-6275 https://orcid.org/0000-0002-1925-2035 https://orcid.org/0000-0001-5814-3264 en_US http://dx.doi.org/10.3233/978-1-61499-419-0-525 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf IOS Press Other univ. web domain |
| spellingShingle | Lin, Dianhuan Dechter, Eyal Ellis, Kevin M. Tenenbaum, Joshua B. Muggleton, Stephen H. Bias reformulation for one-shot function induction |
| title | Bias reformulation for one-shot function induction |
| title_full | Bias reformulation for one-shot function induction |
| title_fullStr | Bias reformulation for one-shot function induction |
| title_full_unstemmed | Bias reformulation for one-shot function induction |
| title_short | Bias reformulation for one-shot function induction |
| title_sort | bias reformulation for one shot function induction |
| url | http://hdl.handle.net/1721.1/102524 https://orcid.org/0000-0003-4926-6275 https://orcid.org/0000-0002-1925-2035 https://orcid.org/0000-0001-5814-3264 |
| work_keys_str_mv | AT lindianhuan biasreformulationforoneshotfunctioninduction AT dechtereyal biasreformulationforoneshotfunctioninduction AT elliskevinm biasreformulationforoneshotfunctioninduction AT tenenbaumjoshuab biasreformulationforoneshotfunctioninduction AT muggletonstephenh biasreformulationforoneshotfunctioninduction |