Feature step dependencies are a pain to work with

[larskotthoff]

The way feature steps are currently implicitly encoded is a pain. First, you have to read the spec very carefully to understand the semantics (which are the opposite of what at least I would intuitively expect), and modifying the features/feature steps (e.g. for feature filtering) is a complex and error-prone operation.

In particular, to remove a feature step, you have to check all the other feature steps if they contain features that are also provided by the feature step that was removed and if so remove those.

Another (albeit minor niggle) is that the format of description.txt is unnecessarily hard to parse and write because the key-value convention is broken for the feature steps (the key is not a primitive value but constructed from other things).

I propose two changes. First, use YAML for description.txt, which will introduce only minor changes but allow us to use off-the-shelf libraries for parsing and writing rather than having to write custom code. Second, encode feature step dependencies explicitly through requires and provide keys.

Example:

scenario_id: SAT11-HAND
performance_measures: runtime
maximize: false
performance_type: runtime
algorithm_cutoff_time: 5000
algorithm_cutoff_memory: ?
features_cutoff_time: 5000
features_cutoff_memory: ?
features_deterministic: nvarsOrig,nclausesOrig,nvars,nclauses,reducedVars,reducedClauses,vars_clauses_ratio,POSNEG_RATIO_CLAUSE_mean,POSNEG_RATIO_CLAUSE_coeff_variation,POSNEG_RATIO_CLAUSE_min,POSNEG_RATIO_CLAUSE_max,POSNEG_RATIO_CLAUSE_entropy,VCG_CLAUSE_mean,VCG_CLAUSE_coeff_variation,VCG_CLAUSE_min,VCG_CLAUSE_max,VCG_CLAUSE_entropy,UNARY,BINARYp,TRINARYp,VCG_VAR_mean,VCG_VAR_coeff_variation,VCG_VAR_min,VCG_VAR_max,VCG_VAR_entropy,POSNEG_RATIO_VAR_mean,POSNEG_RATIO_VAR_stdev,POSNEG_RATIO_VAR_min,POSNEG_RATIO_VAR_max,POSNEG_RATIO_VAR_entropy,HORNY_VAR_mean,HORNY_VAR_coeff_variation,HORNY_VAR_min,HORNY_VAR_max,HORNY_VAR_entropy,horn_clauses_fraction,VG_mean,VG_coeff_variation,VG_min,VG_max,CG_mean,CG_coeff_variation,CG_min,CG_max,CG_entropy,cluster_coeff_mean,cluster_coeff_coeff_variation,cluster_coeff_min,cluster_coeff_max,cluster_coeff_entropy,DIAMETER_mean,DIAMETER_coeff_variation,DIAMETER_min,DIAMETER_max,DIAMETER_entropy,cl_num_mean,cl_num_coeff_variation,cl_num_min,cl_num_max,cl_num_q90,cl_num_q10,cl_num_q75,cl_num_q25,cl_num_q50,cl_size_mean,cl_size_coeff_variation,cl_size_min,cl_size_max,cl_size_q90,cl_size_q10,cl_size_q75,cl_size_q25,cl_size_q50,SP_bias_mean,SP_bias_coeff_variation,SP_bias_min,SP_bias_max,SP_bias_q90,SP_bias_q10,SP_bias_q75,SP_bias_q25,SP_bias_q50,SP_unconstraint_mean,SP_unconstraint_coeff_variation,SP_unconstraint_min,SP_unconstraint_max,SP_unconstraint_q90,SP_unconstraint_q10,SP_unconstraint_q75,SP_unconstraint_q25,SP_unconstraint_q50,saps_BestSolution_Mean,saps_BestSolution_CoeffVariance,saps_FirstLocalMinStep_Mean,saps_FirstLocalMinStep_CoeffVariance,saps_FirstLocalMinStep_Median,saps_FirstLocalMinStep_Q10,saps_FirstLocalMinStep_Q90,saps_BestAvgImprovement_Mean,saps_BestAvgImprovement_CoeffVariance,saps_FirstLocalMinRatio_Mean,saps_FirstLocalMinRatio_CoeffVariance,gsat_BestSolution_Mean,gsat_BestSolution_CoeffVariance,gsat_FirstLocalMinStep_Mean,gsat_FirstLocalMinStep_CoeffVariance,gsat_FirstLocalMinStep_Median,gsat_FirstLocalMinStep_Q10,gsat_FirstLocalMinStep_Q90,gsat_BestAvgImprovement_Mean,gsat_BestAvgImprovement_CoeffVariance,gsat_FirstLocalMinRatio_Mean,gsat_FirstLocalMinRatio_CoeffVariance,lobjois_mean_depth_over_vars,lobjois_log_num_nodes_over_vars
features_stochastic: 
algorithms_deterministic: MPhaseSAT_2011-02-15,Sol_2011-04-04,QuteRSat_2011-05-12_fixed_,CryptoMiniSat_Strange-Night2-st_fixed_,PicoSAT_941,glucose_2,clasp_2.0-R4092-crafted,SAT07referencesolverminisat_SAT2007,jMiniSat_2011,RestartSAT_B95,SAT09referencesolverclasp_1.2.0-SAT09-32,sathys_2011-04-01,SApperloT2010_2011-05-15_fixed_,sattime+_2011-03-02,sattime_2011-03-02 
algorithms_stochastic: 
number_of_feature_steps: 10
default_steps: Pre, Basic, KLB, CG
feature_steps:
  - name: Pre

  - name: Basic
    provides: vars_clauses_ratio,POSNEG_RATIO_CLAUSE_mean,POSNEG_RATIO_CLAUSE_coeff_variation,POSNEG_RATIO_CLAUSE_min,POSNEG_RATIO_CLAUSE_max,POSNEG_RATIO_CLAUSE_entropy,VCG_CLAUSE_mean,VCG_CLAUSE_coeff_variation,VCG_CLAUSE_min,VCG_CLAUSE_max,VCG_CLAUSE_entropy,UNARY,BINARYp,TRINARYp
    requires: Pre

  - name: KLB
    provides: VCG_VAR_mean,VCG_VAR_coeff_variation,VCG_VAR_min,VCG_VAR_max,VCG_VAR_entropy,POSNEG_RATIO_VAR_mean,POSNEG_RATIO_VAR_stdev,POSNEG_RATIO_VAR_min,POSNEG_RATIO_VAR_max,POSNEG_RATIO_VAR_entropy,HORNY_VAR_mean,HORNY_VAR_coeff_variation,HORNY_VAR_min,HORNY_VAR_max,HORNY_VAR_entropy,horn_clauses_fraction,VG_mean,VG_coeff_variation,VG_min,VG_max
    requires: Pre

  - name: CG
    provides: CG_mean,CG_coeff_variation,CG_min,CG_max,CG_entropy,cluster_coeff_mean,cluster_coeff_coeff_variation,cluster_coeff_min,cluster_coeff_max,cluster_coeff_entropy
    requires: Pre

  - name: DIAMETER
    provides: DIAMETER_mean,DIAMETER_coeff_variation,DIAMETER_min,DIAMETER_max,DIAMETER_entropy
    requires: Pre

  - name: cl
    provides: cl_num_mean,cl_num_coeff_variation,cl_num_min,cl_num_max,cl_num_q90,cl_num_q10,cl_num_q75,cl_num_q25,cl_num_q50,cl_size_mean,cl_size_coeff_variation,cl_size_min,cl_size_max,cl_size_q90,cl_size_q10,cl_size_q75,cl_size_q25,cl_size_q50
    requires: Pre

  - name: sp
    provides: SP_bias_mean,SP_bias_coeff_variation,SP_bias_min,SP_bias_max,SP_bias_q90,SP_bias_q10,SP_bias_q75,SP_bias_q25,SP_bias_q50,SP_unconstraint_mean,SP_unconstraint_coeff_variation,SP_unconstraint_min,SP_unconstraint_max,SP_unconstraint_q90,SP_unconstraint_q10,SP_unconstraint_q75,SP_unconstraint_q25,SP_unconstraint_q50
    requires: Pre

  - name: ls_saps
    provides: saps_BestSolution_Mean,saps_BestSolution_CoeffVariance,saps_FirstLocalMinStep_Mean,saps_FirstLocalMinStep_CoeffVariance,saps_FirstLocalMinStep_Median,saps_FirstLocalMinStep_Q10,saps_FirstLocalMinStep_Q90,saps_BestAvgImprovement_Mean,saps_BestAvgImprovement_CoeffVariance,saps_FirstLocalMinRatio_Mean,saps_FirstLocalMinRatio_CoeffVariance
    requires: Pre

 - name: ls_gsat
   provides: gsat_BestSolution_Mean,gsat_BestSolution_CoeffVariance,gsat_FirstLocalMinStep_Mean,gsat_FirstLocalMinStep_CoeffVariance,gsat_FirstLocalMinStep_Median,gsat_FirstLocalMinStep_Q10,gsat_FirstLocalMinStep_Q90,gsat_BestAvgImprovement_Mean,gsat_BestAvgImprovement_CoeffVariance,gsat_FirstLocalMinRatio_Mean,gsat_FirstLocalMinRatio_CoeffVariance
   requires: Pre

  - name: lobjois
    provides: lobjois_mean_depth_over_vars,lobjois_log_num_nodes_over_vars
    requires: Pre

This makes it intuitively clear what Pre does and that it doesn't actually provide any features on its own. It also makes the number_of_feature_steps attribute redundant and it could be removed.

@mlindauer @berndbischl

[berndbischl]

i guees i agrree. how do we parse yaml in r?

[larskotthoff]

https://cran.r-project.org/web/packages/yaml/index.html

[berndbischl]

ok sorry :)

[larskotthoff]

No worries :)
As far as I can see at the moment this would give us exactly the same data structure as we have at the moment (apart from the feature steps of course), so any changes should be minimal.

[mlindauer]

Hi Lars,

I agree that the current format of the feature groups is an issue.
I also like the idea of "provide" and "requires".

However, please note first of all,
that your example is wrong.
Pre provides the following features: "reducedVars,nvars,nclausesOrig,nvarsOrig,nclauses,reducedClauses".

Furthermore, I don't like YAML so much.
We use it for one of our homepages and it is always a pain to edit the yaml files.
Aren't there any better alternatives?

Cheers,
Marius

[larskotthoff]

Ok, that the example is wrong would have been much clearer in the new format :)

I don't see how editing YAML is more painful than editing a non-standard format.

[mlindauer]

In the end, I can live with YAML.
however, there is no way to specify this with arff, or?
If possible, I would like to prevent to use two different standard formats.

[larskotthoff]

Again, I don't see how using two different standard formats is worse than using a standard and a non-standard format. In principle I don't have a problem with using YAML for everything.

[mlindauer]

How would one of the other files look like in YAML?
I read in wikipedia that each JSON file is also valid YAML (>=1.2) file.
I like JSON but I don't know whether this is really user-friendly.

[larskotthoff]

Hmm, I guess something like

- instance_id: bla
  repetition: 1
  feature_x: foo

I don't really see a problem with being user friendly -- you're not supposed to edit/write those files manually.

[mlindauer]

such a format would blow up our files by more than factor 2 I guess.

The description.txt is a file I always write manually.

[berndbischl]

you can forget arff for such files immediatly

[larskotthoff]

Yes, everything would be much larger. But as I said, I'm not opposed to keeping everything but description.txt in arff. We also have citation.bib which is in yet another standard format.

[mlindauer]

OK.

I also asked Matthias whether he likes this new format. and he agreed.
so, please go on and make the changes.

Cheers,
Marius

[larskotthoff]

Ok, what's your feeling on making the lists proper YAML lists as well? I.e. instead of comma-separated they would be

provides:
  - CG_mean
  - CG_coeff_variation
  - etc.