Solving Combinatorial and Probabilistic Problems in Natural Language

This project aims to build a system capable of solving probabilistic and combinatorial problems from questions formulated in natural language. We are working on a dataset composed of common textbook problems that cover a wide range of situations and structures. An example:

In a classroom there are 14 boys and 12 girls. 6 students are randomly selected for a school project: what is the probability that at least half of them are girls?

A sample of the data can be downloaded from the project page on Problog’s website.

This project was born from the IJCAI paper Solving Probability Problems in Natural Language. The work on probability problems has been further developed in the natural language processing part in collaboration with the CLiPS research center. The results of this collaboration are published in the paper Mapping Probability Word Problems to Executable Representations. The project on combinatorial math word problems resulted in the publication Lifted Reasoning for Combinatorial Counting, where the language CoLa and the solver CoSo are presented.

CoLa and CoSo

CoLa and CoSo provide a framework for solving combinatorial counting problems. CoLa is a language to declare simple combinatorics problems, CoSo is a solver for CoLa and provides an explanation of the solution. The technical details and the scientific contributions are described in the publication:

Pietro Totis, Jesse Davis, Luc De Raedt, Angelika Kimmig:
Lifted Reasoning for Combinatorial Counting. J. Artif. Intell. Res. 76: 1-58 (2023)

CoLa and CoSo can be used as a python package and they can be tested with a jupyter notebook. More details about the installation and the code can be found in the Github repository.

With this package combinatorics math word problem can be solved and the solving process can be visualized in its reasoning steps. For example:

A kit of toy shapes contains five triangles and two squares. One triangle and one square are red. Another triangle and the other square are blue, and the remaining triangles are green. In how many different rows of four objects can the shapes be arranged if the two squares are included and the second object is green?

CoSo can produce a visual representation of the problem solving strategy used to solve the problem, for example the resolution of the problem is represented as follows.

universe (squares) ∨ (triangles) = {r2, b2, r1, b1, green, green, green}; 
property squares = {r2, b2}; 
property (triangles) ∧ (¬green) = {r1, b1}; 
property green = {green, green, green}; 

permutation (size == 4) of entity universe (perm)

Position 2: green; 
Nr. squares = 2; 

universe (squares) ∨ (triangles) = {r2, b2, r1, b1, green, green, green}; 
property (triangles) ∧ (¬green) = {r1, b1}; 
property squares = {r2, b2}; 
property green = {green, green, green}; 

Obj 1:  (squares) ∨ (triangles); 
Obj 2:  (squares) ∨ (triangles); 
Obj 3:  (squares) ∨ (triangles); 
Obj 4:  (squares) ∨ (triangles); 

Position 2: green; 
Nr. squares = 2; 

universe green = {green, green, green}; 
property squares = {r2, b2}; 
property (triangles) ∧ (¬green) = {r1, b1}; 

Obj 1:  green; 

Nr. squares = 0; 
Nr. green = 1; 
Nr. ¬green = 0; 

universe (squares) ∨ (triangles) = {r2, b2, r1, b1, green, green}; 
property squares = {r2, b2}; 
property triangles = {r1, b1, green, green, green}; 

Obj 1:  (squares) ∨ (triangles); 
Obj 2:  (squares) ∨ (triangles); 
Obj 3:  (squares) ∨ (triangles); 

Nr. squares in [2, 3]; 

universe squares = {r2, b2}; 
property triangles = {r1, b1, green, green, green}; 

Obj 1:  squares; 
Obj 2:  squares; 

Nr. squares = 2; 

universe (squares) ∨ (triangles) = {r1, b1, green, green}; 

Obj 1:  (squares) ∨ (triangles);