use murmurhash
merge from master
Merge branch 'master' into recommend-mh
murmurhash used + testcases
-O3
Merge branch 'master' of https://github.com/JohnLangford/vowpal_wabbit into recommend-mh
bug fixes related to per-feature regularization
Merge pull request #186 from hal3/master

added ability to compute spelling features
several bug fixing of bfgs per-feature regularization
several bug fixing related to bfgs per-feature regulatization

The following bugs have been fixed w.r.t. bfgs per-feature regularization functionality:

1.  Bug: The '--input_feature_regularizer’ command doesn’t read the input regularizer file (unless it is specified with –i command): 

Cause: parse_regressor_args() function in 'parse_regressor.cc' only looks for the “initial_regressor” or “i" input commands. 

Fix: The following code has been added to the parse_regressor_args() function to fix this bug:
if (vm.count("input_feature_regularizer"))
    regs.push_back(vm["input_feature_regularizer"].as<string>());

This makes the '--input_feature_regularizer’ command working correctly. 

2. Bug: Sometimes we may want to do develop a model using per-feature regularization and get a standard VW model file as the output. However, VW always outputs the per-feature regularization output file (which cannot be directly used for testing/prediction) whenever we specify the per-feature regularization input. 

Cause: bfgs.cc:912: 
bool reg_vector = b->output_regularizer || all->per_feature_regularizer_input.length() > 0;  

When the ‘--input_feature_regularizer’ command is specified, the above code makes the execution of save_load_regularizer(*all, *b, model_file, read, text) function [instead of GD::save_load_regressor()], which outputs per-feature regularizer output file, even though the ‘–f’ or ‘–-readab_model’ commands are specified. 

Fix: this bug has been fixed by changing the bfgs.cc:912 as follows:
bool reg_vector = (b->output_regularizer && !read) || (all->per_feature_regularizer_input.length() > 0 && read);
This would make VW only to output the per-feature regularizer output file when we only specify either          ‘--output_feature_regularizer_binary’ or  ‘--output_feature_regularizer_text’ commands.

3. Bug: The per-features regularization functionality doesn’t work correctly:

Cause: In bfgs.cc file, 'preconditioner_to_regularizer()' function is called at the end of each pass ('process_pass()') (bfgs.cc:715), in which following code get executed:
 ...
'b.regularizers[2*i+1] = weights[stride*i]' 
'b.regularizers[2*i] = weights[stride*i+W_COND] + b.regularizers[2*i]
...

The operation 'b.regularizers[2*i+1] = weights[stride*i]' incorrectly resets the input regularizer weights to the weights we learned from that pass, and this would make the magnitude of the total regularization term (calculated in the add_regularization()) zero in the next pass, which should NOT happen. Also, we should not change the values of b.regularizers[2*i] until BFGS terminates. 


Fix: 1. Commented out the call to preconditioner_to_regularizer() in the process_pass().
       2. The bfgs.end_pass() function has been modified.

These modifications in end_pass() function execute the per_feature regularization functionality correctly w.r.t. the following 3 different situations where the learning process can terminate. However, the generation of output regularizer file with both correct weights and regularizer values would be different w.r.t. each of these situation:

1.	Termination due to reaching the convergence (with --holdout_set_off): In the modified function, at the very next call to end_pass() after reaching the convergence, preconditioner_to_regularizer(*all, *b, (*all).l2_lambda) function is called. Before this execution of end_pass(), the curvature/preconditioner terms (w[3]) have been correctly updated w.r.t. the final weights on which the algorithm has converged. In this case, the generated output regularizer file would contain the correct weights and curvature values. 

2.	Termination due to teaching the max number of passes: As soon as the maximum number of passes reached before convergence, while(true) loop in learner.generic_driver() terminates due to parser.cc making the ‘all->p->done = true’. Therefore, in this case, the preconditioner terms are not updated w.r.t. the final weight vector (as there is no further execution of process_example() calls). Therefore, in this case, it is not correct to output the output regularizer file if the ‘--output_feature_regularizer_binary’ or  ‘--output_feature_regularizer_text’ commands is specified. Hence, in the modified version of the end_pass(), when the max number of iterations reached, we set the b->output_regularizer = false to make VW to output the standard VW model file.

3.	Reaching the early termination with the holdout set: When the holdout set is on, after each good pass (in which the holdout set error decreases), the output model file in created (overwritten) by calling finalize_regressor() function. Then the algorithm terminates when we continuously observe 3 bad passes, during which the output model file is not updated. Therefore, with the current execution flow of VW, it is impossible to generate an output regularizer file containing the weights obtained at the final good pass together with the preconditioner terms calculated w.r.t. those weights. Therefore, it is better to switch off the holdout set option, whenever the ‘--output_feature_regularizer_binary’ or  ‘--output_feature_regularizer_text’ commands are specified. The following code has been added to parser_args.cc to enable that:  

       if(!all->holdout_set_off && (vm.count("output_feature_regularizer_binary") ||            vm.count("output_feature_regularizer_text")))
  {
      all->holdout_set_off = true;
      cout<<"Making holdout_set_off=true since output regularizer specified\n";
  }
fix windows compile warnings
catch up with master
Fixing failed tests
topk impl v1
replacing cout with cerr
fix --binary
Merge pull request #187 from rukshanb/master

Several bug fixing related to bfgs per-feature regularization functionality
changed tuple name to avoid confusions
fixed misleading error message
topk testcases