- \n\t\t\t\t\t\t\t\t
- \n\t\t\n\t\t\t\n\t\t\t\t
Computer-aided Education can help revolutionize the pedagogy inside\/outside traditional classrooms, as well as enrich the experience offered by online classrooms [talk video<\/a>].\u00a0This project focusses\u00a0on one key aspect of computer-aided education, namely automatic problem generation. We have developed tools that can help teachers generate hundreds of problems that are similar to a given problem for use in exams (to prevent plagiarism). These tools can also help students by generating personalized workflows with a dynamic progression of problems of increasing difficulty. We believe that this technology will become an integral part of traditional\/online classrooms, replace expensive books containing practice problems, and offer unique value with personalized instruction leading to better and quick learning.<\/p>\n
We have developed automatic problem generation tools for a variety of subject domains including algebraic proof problems, procedural math problems, sentence completion SAT problems, logic problems, automata construction problems, and board-game problems. These tools build over state-of-the-art advances in multiple computer science disciplines including logical reasoning and natural language understanding, and also\u00a0leverage\u00a0domain-specific knowledge associated with a given subject domain.<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t
- \n\t\t
\n\t\t\t\n\t\t\t\tGiven an algebraic identity (like the red\u00a0problem below), our tool [AAAI 2012<\/a>] is able to generate fresh algebraic identities (shown\u00a0as green problems below) that are similar to the input identity. In addition, the teacher can also enter\u00a0a sample solution to the red problem, and our tool can generate sample solutions to the new green problems. This technology (which generates fresh problems and solutions to those problems\u00a0from an\u00a0example problem and its sample solution)\u00a0can be likened to the Flash Fill<\/a> feature in Excel 2013 that can perform string transformations by examples.<\/p>\n
The tool works for a variety of algebraic domains such as trigonometry, calculus, determinant, and combinatorics.<\/p>\n
![](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/problem-generation-algebra.gif\")
<\/span><\/span><\/p>\nThe tool\u00a0has an interactive setting.\u00a0It generalizes the input (red) identity into a template (shown in orange), which replaces each operator in the input identity by a hole that can be instantiated with another operator of the same type, and some additional constraints (also shown in orange on the right side) that restrict the instantiation choices for the holes. The teacher can modify the constraints to control the variants that get generated. A more restrictive set of constraints will lead to fewer problems being generated, but those that might be more similar to the original one. A less restrictive set of constraints may lead to a generation of a larger number of problems, but the search process might take up more time.<\/p>\n
The tool performs a brute force search over all possible instantiations of the holes in the template and validates the correctness of each instantiation by doing random testing on free variables of the problem. The correctness of this procedure follows from an extension of the classical randomized polynomial identity testing theorem.<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t
- \n\t\t
\n\t\t\t\n\t\t\t\tProcedural problems,\u00a0such as\u00a0addition, multiplication, and computation\u00a0of least common multiple,\u00a0are those\u00a0whose solution entails following a\u00a0step-by-step procedure. These\u00a0are unlike conceptual problems, such as proof problems, whose solution requires creative thinking as opposed to memorizing and executing a procedure.<\/p>\n
Procedural problems are common in middle school mathematics curriculum. The standard pedagogy in teaching procedural skills involves presenting\u00a0a student with a progression of problems of increasing difficulty. For example, an effective progression for addition procedure may first include problems that involve adding single digits, then problems that involve adding multiple digit numbers without any carry, then problems that involve single carry, double carry, and so on.<\/p>\n
Our tool [CHI 2013<\/a>] generates problems for a given procedural concept by using off-the-shelf test\u00a0input generation\u00a0tools (a classic technology from software engineering literature)\u00a0that achieve various forms of coverage over the underlying procedure written as code, as shown in the following figure.<\/p>\n
![](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/problem-generation-arith-1.gif\")
<\/span><\/span><\/p>\n<\/span><\/span>
![](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/problem-generation-arrow.gif\")
<\/span><\/span><\/p>\n![](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/problem-generation-arith-2.gif\")
<\/span><\/span><\/p>\nA partial order over program traces yields a partial order over corresponding test inputs or problems, which can be used to arrange problems into a progression. Our methodology, which characterizes a problem using its trace characteristics, can be used for various interesting applications such as filling holes in a given progression, comparing different progressions from different textbooks, and generating personalized progressions as part of interactive tutoring.<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t
- \n\t\t
\n\t\t\t\n\t\t\t\tOur sentence completion demo illustrates the way in which we can use natural language processing\u00a0technology to generate candidate vocabulary questions, which a teacher can choose to accept or reject for use in the classroom. In this demo, we take a list of vocabulary words to test on, and then generate sentence completion questions that each use a desired vocabulary word. For example, for the vocabulary word \u201cflouted<\/span>,\u201d it might generate:<\/p>\n
But there were rules, and purists irritably noted when they were __________.<\/span><\/pre>\na) installed<\/span><\/pre>\nb) trapped<\/span><\/pre>\nc) broached<\/span><\/pre>\nd) flouted<\/span><\/pre>\ne) fortified<\/span><\/pre>\nTo do this, the program first selects a vocabulary word, and then selects a sentence that uses the word from a database of over 2 million newspaper sentences. Since these sentences are chosen from published newspaper text, they illustrate a correct usage of the target word. To generate alternates or decoys, we analyze the sentence to determine the way in which the target word has been used. For example, in the sentence \u201cHe cleans his room every day, and it is always very orderly,\u201d the word \u201corderly\u201d is used as an adjective. But in the sentence \u201cThe general asked his orderly for coffee,\u201d it is used as a noun. Once the specific linguistic usage of a word has been determined, the program selects alternates from amongst other words that are commonly used in the same way, and presents the question for a teacher to accept or reject.<\/p>\n
In the past, generating sentence completion questions was a time consuming process requiring a great deal of thought to construct a good carrier sentence, and then to think up the alternates. With our technology, it takes just a few seconds to judge whether a question is acceptable, and a very large variety of questions can be generated.<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t
- \n\t\t
\n\t\t\t\n\t\t\t\tNatural deduction, which is a method for establishing validity of propositional type arguments, helps develop important reasoning skills and is thus a key ingredient in a course on introductory logic. A natural deduction problem consists of a set of premises and a conclusion, and the goal is to derive the conclusion starting from the premises using a given set of inference rules.<\/p>\n
Our tool (opens in new tab)<\/span><\/a> can help generate new variants of a given problem by generating valid replacement for one of the premises or the conclusion, as shown in the following figure.<\/p>\n
![](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/problem-generation-logic.gif\")
<\/span><\/span><\/p>\nOur tool also supports two other interfaces for problem generation (paper<\/a>). These include: (i) generation of problems whose proof\/solution structure is similar to that of a given input problem, (ii) generation of problems with given structural and solution characteristics that include number of variables, number of premises, size of each premise, size of solution, and the set of inference rules used in the solution.<\/p>\n
The tool views problem generation as reverse of solution generation. It operates by searching for appropriate premises starting from a conclusion.<\/p>\n
Our tool can also generate sample solutions to any given problem. It leverages the fact that the problem instances have small size, and hence it performs some offline computation and makes use of bitvector data-structures to alleviate the cost associated with symbolic reasoning.<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t
- \n\t\t
\n\t\t\t\n\t\t\t\tBoard games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. Our tool (opens in new tab)<\/span><\/a> can generate starting positions for a given game (specified as a set of rules) and a given expertise level of two players. Generating these starting positions allows for leveling the playing field between two players who may have different expertise levels. It may make certain game variants interesting (such as Tic-Tac-Toe 4*4, which when started from the empty board is heavily biased towards player 1). It also provides other benefits such as educational value in teaching certain strategies, prevents against memorization of moves, and enables faster finish time. The following figure shows starting positions of various difficulty level generated for a beginner player playing against an expert opponent for the game of Tic-Tac-Toe over a 4*4 board that involves making row and column matches of size 3.<\/p>\n
![](\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/02\/problem-generation-boardgames.gif\")
<\/span><\/span><\/p>\nOur tool for generating fresh starting positions can be likened to the above tools for generating fresh problems. Our tool operates by performing backward reachability on winning states (paper<\/a>). Hence, it is very similar to the tool for logic problem generation in that it also views problem generation as reverse of solution generation.<\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t\t\t\t\t<\/ul>\n\t<\/div>\n\t\n","protected":false},"excerpt":{"rendered":"
Intelligent Tutoring Systems (ITS) can significantly enhance the educational experience, both in the classroom and online. A key aspect of ITS is the ability to automatically generate problems of a certain difficulty level and that exercise use of certain concepts. This can help avoid copyright or plagiarism issues and help generate personalized workflows. This project […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"research-area":[13556,13545,13560],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-171112","msr-project","type-msr-project","status-publish","hentry","msr-research-area-artificial-intelligence","msr-research-area-human-language-technologies","msr-research-area-programming-languages-software-engineering","msr-locale-en_us","msr-archive-status-active"],"msr_project_start":"2013-02-25","related-publications":[162576,334454,335471,335552],"related-downloads":[],"related-videos":[189776],"related-groups":[],"related-events":[],"related-opportunities":[],"related-posts":[],"related-articles":[],"tab-content":[],"slides":[],"related-researchers":[{"type":"user_nicename","value":"sriram","display_name":"Sriram Rajamani","author_link":"Sriram Rajamani<\/a>","is_active":false,"user_id":33711,"last_first":"Rajamani, Sriram","people_section":0,"alias":"sriram"},{"type":"user_nicename","value":"sumitg","display_name":"Sumit Gulwani","author_link":"Sumit Gulwani<\/a>","is_active":false,"user_id":33755,"last_first":"Gulwani, Sumit","people_section":0,"alias":"sumitg"},{"type":"user_nicename","value":"zorn","display_name":"Ben Zorn","author_link":"Ben Zorn<\/a>","is_active":false,"user_id":35154,"last_first":"Zorn, Ben","people_section":0,"alias":"zorn"}],"msr_research_lab":[199562,199565],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/171112","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-project"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/171112\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=171112"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=171112"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=171112"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=171112"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=171112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- \n\t\t