Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Comparisons of dumb learner with progressive and projective sampling #19

Open
vivekaxl opened this issue Nov 14, 2016 · 4 comments
Open

Comparisons of dumb learner with progressive and projective sampling #19

vivekaxl opened this issue Nov 14, 2016 · 4 comments

Comments

@vivekaxl
Copy link
Contributor

vivekaxl commented Nov 14, 2016 •
edited
Loading

Hypothesis

To find the most efficient configuration for a given workload, an accurate model of the system is not required. Rather a dumb model is 'good enough'.

How to build this 'good enough' model?

  • Split the data into 40-20-40 partitions, which are training, validation and testing dataset
  • Progressive sample the configurations and build a CART model (from Guo, 2013)
  • Use a new measure called rank difference which is mean of (actual rank - predicted rank) over the validation data. Please note that the ranks (relative ranks) of validation set is known
  • Stopping Criteria: If the mean rank difference doesn't reduce in three contiguous generations, then stop

What is minimum rank found?

  • Given a software and a representative workload, the task of a practitioner is to find the best possible configuration for the system. This can rephrased as if we sort the list of configuration based on their performance values, we need to find the configuration corresponding to the least performance score aka rank 1. Minimum rank is the lowest actual rank achieved by the models on the testing data.

Comparisions

  • Progressive Sampling:
    Progressively increase the size of the testing dataset until the prediction accuracy (mmre) doesn't reach a particular threshold (10%) in this case.
  • Projective Sampling:
    Using heuristic called feature-frequencies an initial population is generated and use to estimate the learning curve. Once the learning curve is found, the optimal size of the training set it also known. code

Summary of Results

  • Wins (15/22), Not so much wins (3/22), Loss (4/22)

Not so much wins?

Using really less number of configuration when compared with other two methods

  • BDBC - 35 < 44/203
  • rs-6d-c3-obj1 - 25 < 452/653
  • sol-6d-c2-obj2 - 26 < 323/1143
    where as the min ranks found are statistically significantly worse than competing methods. But if you look at the minimum ranks found: BDBC 2/2561 (median 2 out of 2561 possible configurations), rs-6d-c3-obj1 2/3840 and sol-6d-c2-obj2 5/2862.

Losses

The rank method uses more number of configuration. This is because all the data sets can be used to build accurate models with few number of configurations for eg SQL and hence terminates much faster. Our counter to these results would be in the real world, it is difficult to find systems which are so accurate. I don't have a reference to this statement but I am looking for one.
@vivekaxl
Copy link
Contributor Author

vivekaxl commented Nov 14, 2016 •
edited
Loading

Wins

lrzip ( 433 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    25.50  ,  18.00   (   -*          |              ), 17.00,  26.00,  35.00
   2 , random-progressive ,    89.00  ,  36.00 (           ----|*             ), 67.00,  91.00,  103.00
   3 , sarkar-projective ,    168.00  ,  0.00  (               |             *), 168.00,  168.00,  168.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00

wc-3d-c4_obj2 ( 756 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    28.50  ,  24.00   (  *            |              ), 21.00,  29.00,  45.00
   2 , sarkar-projective ,    84.00  ,  0.00   (        *      |              ), 84.00,  84.00,  84.00
   3 , random-progressive ,    301.00  ,  0.00 (               |             *), 301.00,  301.00,  301.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  1.00 (*              |              ), 0.00,  0.00,  1.00

HSMGP_num ( 3457 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    29.00  ,  41.00    (-*             |              ), 17.00,  32.00,  58.00
   2 , sarkar-projective ,    402.00  ,  0.00   (               |    *         ), 402.00,  402.00,  402.00
   3 , random-progressive ,    449.00  ,  68.00 (               |     --*      ), 423.00,  457.00,  491.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    0.00  ,  1.00    (*              |              ), 0.00,  0.00,  1.00
   1 , random-progressive ,    0.50  ,  2.00   (*              |              ), 0.00,  1.00,  2.00
   1 ,             dumb ,    1.00  ,  4.00     (*              |              ), 0.00,  1.00,  4.00

Dune ( 2305 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    36.50  ,  29.00    (    --*        |              ), 25.00,  37.00,  54.00
   2 , random-progressive ,    110.00  ,  51.00 (              -|---*          ), 91.00,  116.00,  142.00
   3 , sarkar-projective ,    132.00  ,  0.00   (               |     *        ), 132.00,  132.00,  132.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , random-progressive ,    1.00  ,  2.00  (*              |              ), 0.00,  1.00,  2.00
   1 , sarkar-projective ,    2.00  ,  9.00   (*              |              ), 1.00,  2.00,  10.00
   1 ,             dumb ,    3.50  ,  13.00   (-*             |              ), 1.00,  4.00,  14.00

wc+wc-3d-c4-obj1 ( 196 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    22.00  ,  17.00   (       -*      |              ), 18.00,  23.00,  35.00
   2 , sarkar-projective ,    74.00  ,  0.00   (               |            * ), 74.00,  74.00,  74.00
   2 , random-progressive ,    77.00  ,  12.00 (               |         ----*), 65.00,  77.00,  77.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  1.00   (*              |              ), 0.00,  0.00,  1.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00

wc+wc-3d-c4-obj2 ( 196 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    21.00  ,  17.00  (      --*      |              ), 17.00,  21.00,  34.00
   2 , sarkar-projective ,    34.00  ,  0.00  (             * |              ), 34.00,  34.00,  34.00
   3 , random-progressive ,    77.00  ,  0.00 (               |             *), 77.00,  77.00,  77.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00

wc-6d-c1-obj2 ( 2880 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    46.50  ,  30.00     ( -*            |              ), 33.00,  50.00,  63.00
   2 , sarkar-projective ,    124.00  ,  0.00    (      *        |              ), 124.00,  124.00,  124.00
   3 , random-progressive ,    344.00  ,  108.00 (               | --*          ), 323.00,  351.00,  431.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , random-progressive ,    0.00  ,  1.00 (*              |              ), 0.00,  0.00,  1.00
   1 ,             dumb ,    1.00  ,  3.00   (*              |              ), 0.00,  1.00,  3.00
   1 , sarkar-projective ,    1.00  ,  2.00  (*              |              ), 0.00,  1.00,  2.00

wc-6d-c1-obj1 ( 2880 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    32.50  ,  29.00    (-*             |              ), 21.00,  34.00,  50.00
   2 , random-progressive ,    407.00  ,  86.00 (               |-*            ), 364.00,  415.00,  450.00
   3 , sarkar-projective ,    706.00  ,  0.00   (               |             *), 706.00,  706.00,  706.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    0.00  ,  1.00   (*              |              ), 0.00,  0.00,  1.00
   1 , random-progressive ,    0.00  ,  1.00  (*              |              ), 0.00,  0.00,  1.00
   1 ,             dumb ,    2.00  ,  5.00    (*              |              ), 0.00,  2.00,  5.00

rs-6d-c3_obj2 ( 3840 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    24.00  ,  22.00     (*              |              ), 19.00,  25.00,  41.00
   2 , random-progressive ,    679.50  ,  124.00 (               |  -*          ), 635.00,  685.00,  759.00
   2 , sarkar-projective ,    808.00  ,  0.00    (               |      *       ), 808.00,  808.00,  808.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  8.00   (*              |              ), 0.00,  0.00,  8.00
   1 , sarkar-projective ,    1.00  ,  3.00  (*              |              ), 0.00,  1.00,  3.00
   1 , random-progressive ,    1.00  ,  2.00 (*              |              ), 0.00,  1.00,  2.00

wc+sol-3d-c4-obj2 ( 196 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    19.00  ,  17.00  (      -*       |              ), 17.00,  19.00,  34.00
   1 , sarkar-projective ,    33.00  ,  0.00  (            *  |              ), 33.00,  33.00,  33.00
   2 , random-progressive ,    77.00  ,  0.00 (               |             *), 77.00,  77.00,  77.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  1.00   (*              |              ), 0.00,  0.00,  1.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00

wc+sol-3d-c4-obj1 ( 196 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    23.00  ,  14.00  (       --*     |              ), 18.00,  24.00,  32.00
   2 , sarkar-projective ,    75.00  ,  0.00  (               |             *), 75.00,  75.00,  75.00
   2 , random-progressive ,    77.00  ,  8.00 (               |          ---*), 69.00,  77.00,  77.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00

wc+rs-3d-c4-obj1 ( 196 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    28.00  ,  21.00   (      ----*    |              ), 17.00,  28.00,  38.00
   2 , random-progressive ,    58.50  ,  28.00 (               | -------*     ), 45.00,  62.00,  73.00
   3 , sarkar-projective ,    76.00  ,  0.00   (               |             *), 76.00,  76.00,  76.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00

wc+rs-3d-c4-obj2 ( 196 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    20.50  ,  16.00   (     ---*      |              ), 15.00,  21.00,  31.00
   2 , sarkar-projective ,    38.00  ,  0.00   (              *|              ), 38.00,  38.00,  38.00
   3 , random-progressive ,    77.00  ,  0.00  (               |             *), 77.00,  77.00,  77.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00

sort_256_obj2 ( 206 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    25.00  ,  18.00   (         --*   |              ), 21.00,  25.00,  39.00
   1 , random-progressive ,    28.00  ,  20.00 (          ---* |              ), 22.00,  30.00,  42.00
   2 , sarkar-projective ,    45.00  ,  0.00   (               |    *         ), 45.00,  45.00,  45.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00    (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00

sol-6d-c2-obj1 ( 2866 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    31.50  ,  20.00    (*              |              ), 22.00,  33.00,  42.00
   2 , sarkar-projective ,    105.00  ,  0.00   (  *            |              ), 105.00,  105.00,  105.00
   3 , random-progressive ,    1145.00  ,  0.00 (               |             *), 1145.00,  1145.00,  1145.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    2.50  ,  12.00 (*              |              ), 1.00,  3.00,  13.00
   1 , random-progressive ,    3.00  ,  4.00 (*              |              ), 2.00,  3.00,  6.00
   1 ,             dumb ,    3.50  ,  6.00   (*              |              ), 2.00,  4.00,  8.00

@vivekaxl
Copy link
Contributor Author

vivekaxl commented Nov 14, 2016 •
edited
Loading

(Not so much) Wins

BDBC_AllMeasurements ( 2561 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    35.00  ,  37.00  (   --*         |              ), 25.00,  36.00,  62.00
   1 , random-progressive ,    44.50  ,  9.00 (      *        |              ), 42.00,  45.00,  51.00
   2 , sarkar-projective ,    203.00  ,  0.00 (               |             *), 203.00,  203.00,  203.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    0.00  ,  1.00   (*              |              ), 0.00,  0.00,  1.00
   2 ,             dumb ,    1.00  ,  6.00    (*              |              ), 0.00,  1.00,  6.00
   2 , random-progressive ,    2.00  ,  18.00 (-*             |              ), 1.00,  2.00,  19.00

rs-6d-c3_obj1 ( 3840 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    25.00  ,  26.00     (*              |              ), 16.00,  27.00,  42.00
   2 , sarkar-projective ,    452.00  ,  0.00    (        *      |              ), 452.00,  452.00,  452.00
   3 , random-progressive ,    653.50  ,  308.00 (         ----* |              ), 505.00,  680.00,  813.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    0.00  ,  1.00  (*              |              ), 0.00,  0.00,  1.00
   1 , random-progressive ,    0.00  ,  0.00 (*              |              ), 0.00,  0.00,  0.00
   2 ,             dumb ,    2.00  ,  24.00  (*              |              ), 0.00,  3.00,  24.00

sol-6d-c2-obj2 ( 2862 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    26.00  ,  20.00    (*              |              ), 21.00,  29.00,  41.00
   2 , sarkar-projective ,    323.00  ,  0.00   (        *      |              ), 323.00,  323.00,  323.00
   3 , random-progressive ,    1143.00  ,  0.00 (               |             *), 1143.00,  1143.00,  1143.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    0.00  ,  1.00  (*              |              ), 0.00,  0.00,  1.00
   1 , random-progressive ,    0.00  ,  1.00 (*              |              ), 0.00,  0.00,  1.00
   2 ,             dumb ,    5.00  ,  19.00  (-*             |              ), 1.00,  5.00,  20.00

@vivekaxl
Copy link
Contributor Author

vivekaxl commented Nov 14, 2016 •
edited
Loading

Fails

SQL_AllMeasurements ( 4654 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , random-progressive ,    10.00  ,  0.00 (    *          |              ), 10.00,  10.00,  10.00
   2 ,             dumb ,    30.00  ,  22.00  (        -----* |              ), 21.00,  33.00,  43.00
   3 , sarkar-projective ,    48.00  ,  0.00  (               |    *         ), 48.00,  48.00,  48.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , random-progressive ,    9.00  ,  17.00  (*              |              ), 1.00,  10.00,  18.00
   2 , sarkar-projective ,    14.50  ,  139.00 (*              |              ), 1.00,  15.00,  140.00
   2 ,             dumb ,    20.00  ,  40.00   (*              |              ), 3.00,  21.00,  43.00

X264_AllMeasurements ( 1153 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , random-progressive ,    12.50  ,  5.00 ( -*            |              ), 10.00,  13.00,  15.00
   2 ,             dumb ,    28.00  ,  32.00  (    -*         |              ), 23.00,  29.00,  55.00
   3 , sarkar-projective ,    159.00  ,  0.00 (               |             *), 159.00,  159.00,  159.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    0.00  ,  0.00  (*              |              ), 0.00,  0.00,  0.00
   1 , random-progressive ,    0.00  ,  1.00 (*              |              ), 0.00,  0.00,  1.00
   2 ,             dumb ,    1.50  ,  8.00   (---*           |              ), 0.00,  2.00,  8.00

Apache_AllMeasurements ( 192 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , random-progressive ,    16.00  ,  8.00 (    --*        |              ), 12.00,  17.00,  20.00
   2 ,             dumb ,    24.50  ,  9.00   (        -*     |              ), 21.00,  25.00,  30.00
   3 , sarkar-projective ,    45.00  ,  0.00  (               | *            ), 45.00,  45.00,  45.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 ,             dumb ,    0.00  ,  0.00   (*              |              ), 0.00,  0.00,  0.00
   1 , sarkar-projective ,    0.00  ,  1.00  (*              |              ), 0.00,  0.00,  1.00
   1 , random-progressive ,    0.00  ,  1.00 (*              |              ), 0.00,  0.00,  1.00

WGet ( 189 )

Training Set Size


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , random-progressive ,    13.50  ,  11.00 (    -*         |              ), 11.00,  14.00,  22.00
   1 , sarkar-projective ,    18.00  ,  0.00   (       *       |              ), 18.00,  18.00,  18.00
   2 ,             dumb ,    28.00  ,  23.00   (       ----*   |              ), 19.00,  28.00,  42.00

Minimum Rank Found


rank ,             name ,     med   ,  iqr 
----------------------------------------------------
   1 , sarkar-projective ,    1.00  ,  4.00  (-*             |              ), 0.00,  1.00,  4.00
   1 , random-progressive ,    1.00  ,  3.00 (-*             |              ), 0.00,  1.00,  3.00
   1 ,             dumb ,    2.00  ,  4.00   (---*           |              ), 0.00,  2.00,  4.00

@vivekaxl vivekaxl changed the title Comparisons with progressive and projective sampling Comparisons of dumb learner with progressive and projective sampling Nov 14, 2016
@timm
Copy link

timm commented Nov 14, 2016

Looks interesting. But can i see results in terms of the following?

image

This was referenced Nov 15, 2016
Open
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@timm @vivekaxl