Issue #35 resolved

Make training set creation deterministic

tkeller
repo owner created an issue

The training set creation currently depends on a timeout and is hence not deterministic. Switch it to use a fixed number of randeom walks instead.

Comments (5)

  1. tkeller reporter

    I just made the following comment in the pull request (I am posting it here to access these numbers in the future):

    geisserf I want to get some issues closed, and this is one of them. So I started to make some experiments with this, and it turns out that it is impossible to find a number of simulations that is such that a (approximately) constant runtime is achieved. The actual numbers are:

    Instance                            : new non-prefix / new prefix / old non-prefix
    academic_advising_inst_mdp__1   : [0.352112, '319']  / [0.34881, '319']  / [2.2903, '5129']
    academic_advising_inst_mdp__10  : [12.9981, '707']  / [12.7089, '707']  / [2.11435, '118']
    academic_advising_inst_mdp__2   : [0.433937, '213']  / [0.43496, '213']  / [2.04452, '1012']
    academic_advising_inst_mdp__3   : [0.26309, '499']  / [0.262839, '499']  / [2.02051, '4113']
    academic_advising_inst_mdp__4   : [1.53271, '354']  / [1.52571, '354']  / [2.45945, '471']
    academic_advising_inst_mdp__5   : [0.456564, '651']  / [0.433264, '651']  / [2.05011, '3015']
    academic_advising_inst_mdp__6   : [3.60672, '458']  / [3.52804, '458']  / [2.08557, '261']
    academic_advising_inst_mdp__7   : [0.89449, '709']  / [0.704176, '709']  / [2.02403, '2145']
    academic_advising_inst_mdp__8   : [7.21006, '596']  / [7.19357, '596']  / [2.08738, '175']
    academic_advising_inst_mdp__9   : [1.08629, '725']  / [1.00816, '725']  / [2.02836, '1485']
    crossing_traffic_inst_mdp__1    : [0.709955, '60']  / [0.124124, '60']  / [2.47292, '80']
    crossing_traffic_inst_mdp__10   : [1.76848, '972']  / [1.20739, '972']  / [3.25825, '3184']
    crossing_traffic_inst_mdp__2    : [0.125729, '53']  / [0.129328, '53']  / [2.05942, '80']
    crossing_traffic_inst_mdp__3    : [0.266356, '409']  / [0.238884, '409']  / [2.07127, '1325']
    crossing_traffic_inst_mdp__4    : [0.28116, '330']  / [0.288954, '330']  / [2.10168, '1079']
    crossing_traffic_inst_mdp__5    : [0.520172, '753']  / [0.511209, '753']  / [2.2322, '3709']
    crossing_traffic_inst_mdp__6    : [0.509909, '942']  / [0.509603, '942']  / [2.2369, '5889']
    crossing_traffic_inst_mdp__7    : [1.67524, '932']  / [0.819517, '932']  / [2.38742, '4151']
    crossing_traffic_inst_mdp__8    : [0.764629, '972']  / [0.816926, '972']  / [2.38397, '4452']
    crossing_traffic_inst_mdp__9    : [1.25999, '911']  / [1.27737, '911']  / [2.57495, '2868']
    elevators_inst_mdp__1           : [0.0758049, '112']  / [0.0739319, '112']  / [2.32096, '144']
    elevators_inst_mdp__10          : [0.253304, '433']  / [0.145986, '433']  / [2.096, '5302']
    elevators_inst_mdp__2           : [0.304135, '562']  / [0.337788, '562']  / [2.04535, '1829']
    elevators_inst_mdp__3           : [0.947293, '472']  / [0.342174, '472']  / [2.04438, '1614']
    elevators_inst_mdp__4           : [0.0871582, '249']  / [0.060308, '249']  / [3.06333, '801']
    elevators_inst_mdp__5           : [0.470158, '686']  / [0.472755, '686']  / [2.30966, '2790']
    elevators_inst_mdp__6           : [0.453381, '706']  / [0.434224, '706']  / [3.18405, '2599']
    elevators_inst_mdp__7           : [0.106107, '425']  / [0.467959, '425']  / [2.06216, '3200']
    elevators_inst_mdp__8           : [0.637295, '788']  / [0.630466, '788']  / [2.12468, '2568']
    elevators_inst_mdp__9           : [0.628128, '802']  / [0.644907, '802']  / [2.07653, '2571']
    game_of_life_inst_mdp__1        : [0.277053, '245']  / [0.283711, '245']  / [2.06251, '458']
    game_of_life_inst_mdp__10       : [2.62478, '705']  / [2.62852, '705']  / [2.49443, '589']
    game_of_life_inst_mdp__2        : [0.246842, '317']  / [0.278178, '317']  / [2.06234, '508']
    game_of_life_inst_mdp__3        : [0.275019, '379']  / [0.250328, '379']  / [2.06208, '512']
    game_of_life_inst_mdp__4        : [1.53766, '800']  / [0.80289, '800']  / [2.13119, '2023']
    game_of_life_inst_mdp__5        : [0.793341, '895']  / [0.805137, '895']  / [2.25114, '2344']
    game_of_life_inst_mdp__6        : [1.79914, '957']  / [0.835251, '957']  / [3.92821, '2584']
    game_of_life_inst_mdp__7        : [1.94282, '891']  / [1.95656, '891']  / [2.14049, '941']
    game_of_life_inst_mdp__8        : [2.00889, '937']  / [1.96616, '937']  / [2.15509, '994']
    game_of_life_inst_mdp__9        : [2.02007, '972']  / [1.97484, '972']  / [2.15428, '1024']
    navigation_inst_mdp__1          : [0.16802, '10']  / [0.138562, '10']  / [2.58268, '13']
    navigation_inst_mdp__10         : [1.45584, '6']  / [1.44054, '6']  / [2.21605, '7']
    navigation_inst_mdp__2          : [0.206803, '13']  / [0.227918, '13']  / [2.02784, '16']
    navigation_inst_mdp__3          : [0.28782, '13']  / [0.278903, '13']  / [2.05342, '21']
    navigation_inst_mdp__4          : [0.464192, '19']  / [0.430189, '19']  / [2.07083, '20']
    navigation_inst_mdp__5          : [0.416194, '14']  / [0.41107, '14']  / [2.06413, '17']
    navigation_inst_mdp__6          : [0.561379, '13']  / [0.563586, '13']  / [2.08312, '14']
    navigation_inst_mdp__7          : [0.715604, '13']  / [0.730425, '13']  / [2.6267, '14']
    navigation_inst_mdp__8          : [0.847696, '6']  / [0.824248, '6']  / [2.1413, '8']
    navigation_inst_mdp__9          : [1.1666, '6']  / [1.13887, '6']  / [2.16545, '7']
    recon_inst_mdp__1               : [1.07664, '609']  / [0.489422, '609']  / [2.08156, '2564']
    recon_inst_mdp__10              : [1.73634, '411']  / [1.69269, '411']  / [2.10988, '525']
    recon_inst_mdp__2               : [0.515538, '598']  / [0.488215, '598']  / [2.08196, '2489']
    recon_inst_mdp__3               : [1.28569, '524']  / [1.29142, '524']  / [2.59811, '1425']
    recon_inst_mdp__4               : [1.24874, '541']  / [1.26025, '541']  / [2.55406, '1357']
    recon_inst_mdp__5               : [1.16794, '373']  / [1.16828, '373']  / [2.08501, '632']
    recon_inst_mdp__6               : [1.83644, '431']  / [1.11737, '431']  / [2.08228, '731']
    recon_inst_mdp__7               : [1.16277, '498']  / [1.14863, '498']  / [2.08455, '842']
    recon_inst_mdp__8               : [1.73267, '364']  / [1.73646, '364']  / [2.12689, '420']
    recon_inst_mdp__9               : [1.68849, '312']  / [1.80297, '312']  / [2.66594, '382']
    skill_teaching_inst_mdp__1      : [0.105383, '59']  / [0.108046, '59']  / [2.03583, '63']
    skill_teaching_inst_mdp__10     : [3.18756, '539']  / [3.26049, '539']  / [3.55803, '411']
    skill_teaching_inst_mdp__2      : [0.107439, '59']  / [0.109405, '59']  / [2.01865, '63']
    skill_teaching_inst_mdp__3      : [0.477474, '350']  / [0.43696, '350']  / [2.10214, '709']
    skill_teaching_inst_mdp__4      : [0.429778, '299']  / [0.436242, '299']  / [2.09423, '668']
    skill_teaching_inst_mdp__5      : [1.18994, '436']  / [1.20923, '436']  / [2.18993, '607']
    skill_teaching_inst_mdp__6      : [1.19691, '477']  / [1.20727, '477']  / [2.32347, '659']
    skill_teaching_inst_mdp__7      : [1.85014, '481']  / [1.85, '481']  / [2.34905, '503']
    skill_teaching_inst_mdp__8      : [1.99816, '443']  / [2.07474, '443']  / [2.40996, '389']
    skill_teaching_inst_mdp__9      : [3.5874, '547']  / [3.03869, '547']  / [3.04744, '410']
    sysadmin_inst_mdp__1            : [0.240663, '407']  / [0.236597, '407']  / [2.17332, '961']
    sysadmin_inst_mdp__10           : [4.59334, '945']  / [4.29557, '945']  / [2.06935, '440']
    sysadmin_inst_mdp__2            : [0.260798, '495']  / [0.253393, '495']  / [2.06771, '999']
    sysadmin_inst_mdp__3            : [0.719976, '829']  / [0.725323, '829']  / [2.04763, '2466']
    sysadmin_inst_mdp__4            : [0.752608, '868']  / [0.789294, '868']  / [2.06916, '2438']
    sysadmin_inst_mdp__5            : [1.5903, '925']  / [2.20511, '925']  / [2.03696, '1229']
    sysadmin_inst_mdp__6            : [1.62421, '929']  / [1.63535, '929']  / [2.17059, '1157']
    sysadmin_inst_mdp__7            : [2.72769, '951']  / [2.68964, '951']  / [2.07597, '720']
    sysadmin_inst_mdp__8            : [2.84216, '951']  / [2.92161, '951']  / [2.10199, '681']
    sysadmin_inst_mdp__9            : [4.03349, '947']  / [4.10932, '947']  / [2.08998, '457']
    tamarisk_inst_mdp__1            : [3.00397, '568']  / [2.60746, '568']  / [4.29626, '2376']
    tamarisk_inst_mdp__10           : [2.56557, '957']  / [2.65571, '957']  / [2.70456, '1003']
    tamarisk_inst_mdp__2            : [0.670815, '764']  / [0.683008, '764']  / [2.14741, '2603']
    tamarisk_inst_mdp__3            : [0.579805, '721']  / [0.566594, '721']  / [2.09841, '2579']
    tamarisk_inst_mdp__4            : [1.01163, '845']  / [1.06754, '845']  / [2.24716, '1951']
    tamarisk_inst_mdp__5            : [0.856827, '800']  / [0.830322, '800']  / [2.40741, '1969']
    tamarisk_inst_mdp__6            : [1.43588, '908']  / [1.42036, '908']  / [3.32177, '1605']
    tamarisk_inst_mdp__7            : [1.22556, '831']  / [1.14672, '831']  / [2.16602, '1672']
    tamarisk_inst_mdp__8            : [1.97484, '938']  / [1.94444, '938']  / [2.57557, '1260']
    tamarisk_inst_mdp__9            : [1.59211, '889']  / [1.49324, '889']  / [2.24556, '1387']
    traffic_inst_mdp__1             : [0.569167, '955']  / [0.563246, '955']  / [2.06026, '3878']
    traffic_inst_mdp__10            : [1.42313, '954']  / [1.68761, '954']  / [2.48429, '2711']
    traffic_inst_mdp__2             : [1.49171, '956']  / [0.532984, '956']  / [2.09078, '4155']
    traffic_inst_mdp__3             : [0.63307, '957']  / [0.657065, '957']  / [2.11626, '3616']
    traffic_inst_mdp__4             : [0.676136, '963']  / [1.15899, '963']  / [2.16295, '3692']
    traffic_inst_mdp__5             : [0.803788, '949']  / [0.843691, '949']  / [2.36906, '3288']
    traffic_inst_mdp__6             : [0.801845, '957']  / [0.803543, '957']  / [2.24129, '3330']
    traffic_inst_mdp__7             : [0.98119, '949']  / [0.978272, '949']  / [2.33507, '2941']
    traffic_inst_mdp__8             : [1.74601, '956']  / [0.980464, '956']  / [2.38979, '2983']
    traffic_inst_mdp__9             : [1.20806, '958']  / [1.20275, '958']  / [2.47478, '2606']
    triangle_tireworld_inst_mdp__1  : [0.197004, '56']  / [0.199655, '56']  / [2.0167, '95']
    triangle_tireworld_inst_mdp__10 : [24.5975, '43']  / [24.3218, '43']  / [2.34446, '9']
    triangle_tireworld_inst_mdp__2  : [0.19736, '52']  / [0.200927, '52']  / [2.06331, '95']
    triangle_tireworld_inst_mdp__3  : [1.16262, '42']  / [1.36772, '42']  / [2.04983, '71']
    triangle_tireworld_inst_mdp__4  : [1.1662, '62']  / [1.16894, '62']  / [2.07211, '116']
    triangle_tireworld_inst_mdp__5  : [4.16543, '43']  / [4.22262, '43']  / [2.08373, '20']
    triangle_tireworld_inst_mdp__6  : [4.23861, '77']  / [4.27839, '77']  / [2.24992, '35']
    triangle_tireworld_inst_mdp__7  : [11.1291, '44']  / [10.9898, '44']  / [2.39969, '15']
    triangle_tireworld_inst_mdp__8  : [11.4438, '39']  / [10.9338, '39']  / [2.16671, '15']
    triangle_tireworld_inst_mdp__9  : [24.1399, '40']  / [23.5958, '40']  / [2.31851, '6']
    wildfire_inst_mdp__1            : [0.634363, '154']  / [1.5724, '154']  / [2.24914, '494']
    wildfire_inst_mdp__10           : [6.89599, '839']  / [6.50759, '839']  / [2.27036, '274']
    wildfire_inst_mdp__2            : [1.22012, '153']  / [1.22845, '153']  / [2.9826, '805']
    wildfire_inst_mdp__3            : [1.09641, '411']  / [2.66059, '411']  / [2.09732, '808']
    wildfire_inst_mdp__4            : [1.10883, '423']  / [1.05302, '423']  / [2.13095, '787']
    wildfire_inst_mdp__5            : [3.23567, '624']  / [3.25763, '624']  / [2.35526, '400']
    wildfire_inst_mdp__6            : [2.93655, '675']  / [2.93258, '675']  / [2.13785, '491']
    wildfire_inst_mdp__7            : [3.98634, '833']  / [3.96148, '833']  / [2.18506, '450']
    wildfire_inst_mdp__8            : [5.12308, '751']  / [4.16051, '751']  / [2.15162, '386']
    wildfire_inst_mdp__9            : [5.33959, '895']  / [5.38224, '895']  / [2.33686, '346']
    

    As you can see, sometimes it takes a lot less time, and sometimes a lot more. It should be possible to improve this, as the difference in runtime - it's not the number of evaluated states, they are the same - could probably be diminished by a more efficient implementation of the state transitions, which should be added with issue #34. My proposal for this is therefore:

    • I am currently experiments with the same code that lead to the numbers above.
    • If the results are comparable, we ignore the fact that parsing takes sometimes quite long
    • Once issue #34 is merged, we re-evaluate the used parameters to see if we find good numbers such that most instances take approximately 2 seconds.

    Any objections?

  2. geisserf

    I don't have any objections, but I think we should create a separate issue which considers aspects of a new implementation of state transitions and representation of logical formulae, since this is a very large topic at hand.

    I'm currently investigating possible implementations for another project; if you want I can create this issue and write a comment with regard to the problems of the current implementation (the fact that we always create raw pointers and do not have any memory management often leads to problems when we transformed logical expressions for e.g. normal forms of CPFs), features the new implementation should support and consider some possible implementations/concepts which already exist in other work.

  3. tkeller reporter

    These are the results based on the deterministic parser. The only relevant change is the training set, which is used by IDS to learn a reasonable depth, and it seems as if it didn't affect the results much. I'll close the issue later and merge the changes into the master repository.

  4. tkeller reporter

    geisserf, please go ahead and start the issue. If it is a large task, I'd suggest you create one "super-issue" with reference to multiple smaller ones. That way, we can track the progress of the larger problem in the super-issue, but can merge sub tasks once they have been adressed.

  5. Log in to comment