README.md 9.63 KB
Newer Older
Amélie Royer's avatar
Amélie Royer committed
1 2 3
![license](https://img.shields.io/github/license/ameroyer/ReCA.svg)
![GitHub repo size in bytes](https://img.shields.io/github/repo-size/ameroyer/ReCA.svg)
![GitHub top language](https://img.shields.io/github/languages/top/ameroyer/ReCA.svg)
Amélie Royer's avatar
Amélie Royer committed
4 5
![Maintenance](https://img.shields.io/maintenance/no/2017.svg)

Amélie Royer's avatar
Amélie Royer committed
6

Amélie Royer's avatar
Amélie Royer committed
7
# [ R e C A ]  r e a d   m e
Amélie Royer's avatar
Amélie Royer committed
8

Amélie Royer's avatar
Amélie Royer committed
9
# Installation
Amelie Royer's avatar
Amelie Royer committed
10

Amélie Royer's avatar
Amélie Royer committed
11 12
#### requirements
   * python (the scripts were tested with versions 2.7 and 3.2)
Amelie Royer's avatar
Amelie Royer committed
13 14
   * GCC 4.9 +
   * cmake [``cmake`` package]
15
   * Boost version 1.53+ [``libboost-dev`` package]
Amelie Royer's avatar
Amelie Royer committed
16 17 18
   * [Eigen 3.2+](http://eigen.tuxfamily.org/index.php?title=Main_Page) library
   * [lp_solve](http://lpsolve.sourceforge.net/5.5/) library [``lp-solve`` package]

Amélie Royer's avatar
Amélie Royer committed
19
#### installing AIToolbox
Amelie Royer's avatar
Amelie Royer committed
20 21 22
Clone the [AIToolbox repository](https://github.com/Svalorzen/AI-Toolbox), then build and test the installation with the following commands.

**Note** this project was done in mid-year 2016, more recent AiToolbox versiones might have a different organization
Amelie Royer's avatar
Amelie Royer committed
23

Amélie Royer's avatar
Amélie Royer committed
24 25
**NOTE**: This was implemented with AIToolox in mid-year 2016. It is possile that more recent versions have different structures and import path mayb need to be changed.

Amelie Royer's avatar
Amelie Royer committed
26
```bash
27
cd AIToolbox_root
Amelie Royer's avatar
Amelie Royer committed
28 29 30 31 32 33
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j
ctest -V
```

Amélie Royer's avatar
Amélie Royer committed
34
# Dataset generation
Amelie Royer's avatar
Amelie Royer committed
35

Amélie Royer's avatar
Amélie Royer committed
36 37
#### synthetic recommandation dataset
Generate synthetic POMDP parameters to highlight the impact of using multiple environments. The model comprises as many environments as possible recommandations. The *i*-th environment corresponds to users choosing item *i* with a high probability (``p=0.8``) and uniform preference towards other recommandations.  The reward is 0 if the recommendation does not match the user's choice, and 1 otherwise.
Amelie Royer's avatar
Amelie Royer committed
38

Amélie Royer's avatar
Amélie Royer committed
39 40 41 42
  ```bash
  cd Data/
  ./prepare_synth.py -n [1] -k [2] -a [3] -t [4] -o [5] --norm --help
  ```
Amelie Royer's avatar
Amelie Royer committed
43

Amélie Royer's avatar
Amélie Royer committed
44 45 46 47 48 49 50 51
  * ``[1]`` Number of items (Defaults to 3).
  * ``[2]`` History length (Defaults to 2). Must be strictly greater than 1.
  * ``[3]`` Positive scaling parameter for correct recommandation. Must be greater than 1. Defaults to 1.1.
  * ``[4]`` Number of test sessions to generate following the generated distribution. Defaults to 2000.
  * ``[5]`` Path to the output directory (Defaults to ``../Code/Models``).
  * ``[--norm]`` If present, normalize the output transition probabilities.
  * ``[--zip]`` If present, transitions are stored in an archive. Recommended for large state spaces.
  * ``[--help]`` displays help about the script.
Amelie Royer's avatar
Amelie Royer committed
52

Amélie Royer's avatar
Amélie Royer committed
53 54
#### Foodmart dataset
 Estimate a POMDP model parameters and test sequences from the [Foodmart](https://github.com/neo4j-examples/neo4j-foodmart-dataset) dataset (.csv dataset files are included in the ``Data/`` directory).
Amelie Royer's avatar
Amelie Royer committed
55

Amélie Royer's avatar
Amélie Royer committed
56 57
 ```bash
  cd Data/
Amelie Royer's avatar
Amelie Royer committed
58
  ./prepare_foodmart.py -p [1] -k [2] -u [3] -a [4] -t [5] -d [6] -o [7] -D [8] --norm --help
Amélie Royer's avatar
Amélie Royer committed
59
```
Amelie Royer's avatar
Amelie Royer committed
60

Amélie Royer's avatar
Amélie Royer committed
61 62
  * ``[1]`` Items discretization level. Must be between 0 (*1561 fine-grained products*)  and 4 (*3 high-level categories*). Defaults to 4.
  * ``[2]`` History length, > 1. Defaults to 2.
Amelie Royer's avatar
Amelie Royer committed
63 64 65
  * ``[3]`` Number of profiles to generate. Defaults to 5.
  * ``[4]`` Positive scaling parameter for correct recommandation. Must be greater than 1. Defaults to 1.1.
  * ``[5]`` Number of test sequences to generate. Defaults to 2000.
Amélie Royer's avatar
Amélie Royer committed
66 67
  * ``[6]`` Path to the Foodmart dataset. Defaults to ``Data/Foodmart.gz``.
  * ``[7]`` Path to the output directory. Defaults to ``../Code/Models``.
Amelie Royer's avatar
Amelie Royer committed
68
  * ``[8]`` Number of sequences to isolate to estimate each environment's transition probabilities.
Amélie Royer's avatar
Amélie Royer committed
69 70 71
  * ``[--norm]`` If present, output transition probabilities are normalized.
  * ``[--zip]`` If present, transitions are stored in an archive. Recommended for large state spaces.
  * ``[--help]`` displays help about the script.
Amelie Royer's avatar
Amelie Royer committed
72

Amélie Royer's avatar
Amélie Royer committed
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
#### maze dataset
Generating POMDP parameters for a typical maze/path finding problem with multiple environments.

  ```bash
  cd Data/
  ./prepare_maze.py -i [1] -n [2] -s [3] -t [4] -w [5] -g [6] -e [7] -wf [8] -o [9] --rdf --help
  ```

  * ``[1]`` If given, load the maze structure from a file (see toy examples in the ``Mazes`` subdirectory). if not, the mazes are generated randomly with the following parameters.
  * ``[2]`` Maze width and height.
  * ``[3]`` Number of initial states in each maze. Defaults to 1.
  * ``[4]`` Number of trap states in each maze (non-rewarding absorbing states). Defaults to 0.
  * ``[5]`` Number of obstacles in each maze. Defaults to 0.
  * ``[6]`` Number of goal states in each maze. Defaults to 1.
  * ``[7]`` Number of mazes (environments) to generate. Defaults to 1.
  * ``[8]`` Failure rate (equivalent to falling in a trap state) when going forward in the direction of an obstacle. Defaults to 0.05.
  * ``[9]`` Path to the output directory (Defaults to ``../Code/Models``).
  * ``[--norm]`` If present, normalize the output transition probabilities.
  * ``[--rdf]`` If present, the failure rates (probability of staying put instead of realizing the intended action) for each environment are sampled uniformly over [0; 0.5[
  * ``[--help]`` displays help about the script.

Amélie Royer's avatar
Amélie Royer committed
94
# Building and evaluating the MEMDP-based models
Amélie Royer's avatar
Amélie Royer committed
95 96 97 98 99 100 101 102 103 104 105 106 107 108

#### set-up
The following variables can be configured at the beginning of the ``run.sh`` script (e.g. if some libaries are installed locally and not globally)
  * ``AIROOT``: path to the AIToolbox installation directory.
  * ``EIGEN``: path to the Eigen library installation directory.
  * ``LPSOLVE``: path to the lpsolve library installation directory.
  * ``GCC``: path to the g++ binary.
  * ``STDLIB``: path to the stdlib matching the given gcc compiler.

#### run
```bash
  cd Code/
./run.sh -m [1] -d [2] -n [3] -k [4] -u [5] -g [6] -s [7] -h [8] -e [9] -x [10] -b [11] -c -p -v
```
Amelie Royer's avatar
Amelie Royer committed
109

Amelie Royer's avatar
Amelie Royer committed
110 111
   * ``[1]`` Model to use. Defaults to mdp. Available options are
      * *mdp*. MDP model obtained by a weighted average of all the environments' transition probabilities and solved by Value iteration. The solver can be configured with
Amelie Royer's avatar
Amelie Royer committed
112
        * ``[7]`` Number of iterations. Defaults to 1000.
Amélie Royer's avatar
Amélie Royer committed
113 114
      * *pbvi*. point-based value iteration optimized for the MEMDP structure with options
        * ``[8]`` Horizon parameter. Must be greater than 1. Defaults to 2.
Amelie Royer's avatar
Amelie Royer committed
115
        * ``[11]`` Belief size. Defaults to  500.
Amélie Royer's avatar
Amélie Royer committed
116
      * *pomcp*, *pomcpex*, *pamcpex*, *pamcp*. Monte-carlo solvers. *pamcp* and *pamcpex* implement the past-aware graph initialization. *pomcpex* and *pamcpex* implement the exact belief computation. *pomcp* is the vanilla POMCP with MEMDP-optimized sampling (POMCP\*)
Amelie Royer's avatar
Amelie Royer committed
117
        * ``[7]`` Number of simulation steps. Defaults to 1000.
Amélie Royer's avatar
Amélie Royer committed
118 119
        * ``[8]`` Horizon parameter. Must be greater than 1. Defaults to 2.
        * ``[10]`` Exploration parameter. Defaults to 10000 (high exploration).
Amelie Royer's avatar
Amelie Royer committed
120
        * ``[11]`` Number of particles for the belief approximation. Defaults to  500.
Amélie Royer's avatar
Amélie Royer committed
121 122 123 124
   * ``[2]`` Dataset to use. Defaults to rd. Available options are
     * *fm* (foodmart recommandations) with following options
       * ``[3]`` Product discretization level. Defaults to 4.
       * ``[4]`` History length. Must be strictly greater than 1. Defaults to 2.
Amelie Royer's avatar
Amelie Royer committed
125
       * ``[5]`` User discretization level. Defaults to 0.
Amelie Royer's avatar
Amelie Royer committed
126
     * *mz* (maze solving problem) with following options
Amélie Royer's avatar
Amélie Royer committed
127
       * ``[3]`` Base name for the directory containing the corresponding MEMDP model parameters.
Amelie Royer's avatar
Amelie Royer committed
128
     * *rd* (synthetic data recommandations) with following options
Amélie Royer's avatar
Amélie Royer committed
129 130 131 132
       * ``[3]`` Number of actions. Defaults to 4.
       * ``[4]`` History length. Must be strictly greater than 1. Defaults to 2.
   * ``[6]`` Discount Parameter. Must be strictly between 0 and 1. Defaults to 0.95.
   * ``[9]`` Convergence criterion. Defaults to 0.01.
Amelie Royer's avatar
Amelie Royer committed
133
   * ``[-c]`` If present, recompile the code before running (*Note*: this should be used whenever using a dataset with different parameters as the number of items, environments etc are determined at compilation time).
Amélie Royer's avatar
Amélie Royer committed
134
   * ``[-p]`` If present, normalize the transition and use Kahan summation for more precision while handling small probabilities. Use this option if AIToolbox throws an ``Input transition table does not contain valid probabilities`` error.
Amelie Royer's avatar
Amelie Royer committed
135
   * ``[-v]`` If present, enables verbose output. In verbose mode, evaluation results per environments are displayed, and the std::cerr stream is eanbled during evaluation.
Amelie Royer's avatar
Amelie Royer committed
136

Amélie Royer's avatar
Amélie Royer committed
137 138
# examples

Amélie Royer's avatar
Amélie Royer committed
139
#### maze solving, 60 environments, 3 actions, ~100 states
Amélie Royer's avatar
Amélie Royer committed
140 141 142 143 144 145 146 147 148 149 150 151 152 153
  * if needed, generate the data (already available on the repository)
  ```bash
   cd Data/
   python prepare_maze.py --norm --zip -n 5 -s 1 -g 1 -w 0 -t 0 -e 60 --rdf
  ```

  * run the code (assuming the output directory is the default ``ROOT/Code/Models/``)
  ```bash
  cd ../Code/
  ./run.sh -m pbvi -d mz -n gen_5x5_101_60 -h 20 -b 100 -c
  ./run.sh -m pamcp -d mz -n gen_5x5_101_60 -h 10 -c	
  ```

#### synthetic recommandations, 10 environments, 10 actions, ~100 states
Amelie Royer's avatar
Amelie Royer committed
154 155 156 157 158 159 160

  * if needed, generate the data (already available on the repository)
  ```bash
   cd Data/
   python prepare_synth.py --norm --zip -n 10 -k 2
  ```

Amélie Royer's avatar
Amélie Royer committed
161
  * run the code (assuming the output directory is the default ``ROOT/Code/Models/``)
Amelie Royer's avatar
Amelie Royer committed
162 163 164 165
  ```bash
  cd ../Code/
  ./run.sh -m mdp -d rd -n 10 -k 2 -c
  ./run.sh -m pamcp -d rd -n 10 -k 2 -c	
Amelie Royer's avatar
Amelie Royer committed
166
  ./run.sh -m pomcpex -d rd -n 10 -k 2 -c	
Amelie Royer's avatar
Amelie Royer committed
167 168
  ```

Amélie Royer's avatar
Amélie Royer committed
169
#### Foodmart recommandations, 5 environments, 22 actions, ~500 states
Amelie Royer's avatar
Amelie Royer committed
170 171 172 173 174 175 176

  * if needed, generate the data (already available on the repository)
  ```bash
   cd Data/
   python prepare_foodmart.py --norm --zip -u 5 -p 3 -k 2
  ```

Amélie Royer's avatar
Amélie Royer committed
177
  * run the code (assuming the output directory is the default ``ROOT/Code/Models/``)
Amelie Royer's avatar
Amelie Royer committed
178 179 180 181 182 183 184
  ```bash
  cd ../Code/
  ./run.sh -m mdp -d fm -n 3 -k 2 -u 5 -c
  ./run.sh -m pamcp -d rd -n 3 -k 2 -u 5 -c
  ./run.sh -m pbvi -d rd -n 3 -k 2 -u 5 -c	
  ```

Amelie Royer's avatar
Amelie Royer committed
185

Amélie Royer's avatar
Amélie Royer committed
186
# Known issues
Amélie Royer's avatar
Amélie Royer committed
187
  * When using the ``--zip`` option for data generation, it might be necessary to run the script with ``python3`` due to an [issue](https://bugs.python.org/issue23306) with the gzip library in python < 3.