exit_optimizer();  examples->set_initialised_alpha();  parameters->working_set_size = param_wss;  return the_result;};void svm_c::shrink(){  // move shrinked examples to back  if(to_shrink>examples_total/10){    SVMINT i;    SVMINT last_pos=examples_total;    if(last_pos > working_set_size){	for(i=0;i<last_pos;i++){	    if(at_bound[i] >= shrink_const){		// shrinxk i		sum_alpha += all_alphas[i];		last_pos--;		examples->swap(i,last_pos);		kernel->overwrite(i,last_pos);		sum[i] = sum[last_pos];		at_bound[i] = at_bound[last_pos];		if(last_pos <= working_set_size){		    break;		};	    };	};	to_shrink=0;	examples_total = last_pos;	kernel->set_examples_size(examples_total);    };    if(parameters->verbosity>=4){      cout<<"shrinked to "<<examples_total<<" variables"<<endl;    };  };};int svm_c::convergence(){  long time_start = get_time();  SVMFLOAT the_lambda_eq = 0;  SVMINT total = 0;  SVMFLOAT alpha_sum=0;  SVMFLOAT alpha=0;  SVMINT i;  int result=1;  // actual convergence-test  total = 0; alpha_sum=0;  if(biased){    // calc lambda_eq    for(i=0;i<examples_total;i++){      alpha = all_alphas[i];      alpha_sum += alpha;      if((alpha>is_zero) && (alpha < Cneg)){ //-Cneg < -is_zero)){	// alpha^* = - nabla	the_lambda_eq += -nabla(i); //all_ys[i]-epsilon_neg-sum[i];	total++;      }      else if((alpha<-is_zero) && (alpha > -Cpos)){ //+Cpos > is_zero)){	// alpha = nabla	the_lambda_eq += nabla(i); //all_ys[i]+epsilon_pos-sum[i];	total++;      };    };        if(parameters->verbosity >= 4){      cout<<"lambda_eq = "<<(the_lambda_eq/total)<<endl;    };    if(total>0){      lambda_eq = the_lambda_eq / total;    }    else{      // keep WS lambda_eq      lambda_eq = lambda_WS; //(lambda_eq+4*lambda_WS)/5;      if(parameters->verbosity>= 4){	cout<<"*** no SVs in convergence(), lambda_eq = "<<lambda_eq<<"."<<endl;      };    };        if(target_count>2){      // estimate lambda from WS      if(target_count>20){	// desperate!	lambda_eq = ((40-target_count)*lambda_eq + (target_count-20)*lambda_WS)/20;	if(parameters->verbosity>=5){	  cout<<"Re-Re-calculated lambda from WS: "<<lambda_eq<<endl;	};	if(target_count>40){	  // really desperate, kick one example out!	  i = working_set[target_count%working_set_size];	  if(is_alpha_neg(i) > 0){	    lambda_eq = -nabla(i);	  }	  else{	    lambda_eq = nabla(i);	  };	  if(parameters->verbosity>=5){	    cout<<"set lambda_eq to nabla("<<i<<"): "<<lambda_eq<<endl;	  };	};      }      else{	lambda_eq = lambda_WS;	if(parameters->verbosity>=5){	  cout<<"Re-calculated lambda_eq from WS: "<<lambda_eq<<endl;	};      };    };    // check linear constraint    if(abs(alpha_sum+sum_alpha) > convergence_epsilon){      // equality constraint violated      project_to_constraint();      if(parameters->verbosity>= 4){	cout<<"No convergence: equality constraint violated: |"<<(alpha_sum+sum_alpha)<<"| >> 0"<<endl;      };      result = 0;      };  }  else{    // not biased    lambda_eq = 0.0;  };  i=0;  while(i<examples_total){    if(lambda(i)>=-convergence_epsilon){      i++;    }    else{      result = 0;      break;    };  };  time_convergence += get_time() - time_start;  return result;};void svm_c::minheap_heapify(SVMINT start, SVMINT size){  // build heap of array working_set[start:start+size-1]  // (i.e. "size" elements starting at "start"th element)  // minheap = 1 <=> maximal element at root   // (i.e. we build the heap of minimal elements)  // v_a[i] = w_s_v[start-1+i], count beginning at 1  SVMFLOAT* value_array = working_set_values+start-1;   SVMINT* pos_array = working_set+start-1;  int running = 1;  SVMINT pos = 1;  SVMINT left, right, largest;  SVMFLOAT dummyf;  SVMINT dummyi;  while(running){      left = 2*pos;      right = left+1;      if((left<=size) && 	 (value_array[left] > value_array[pos]))	largest = left;      else{	largest = pos;      };      if((right<=size) && 	 (value_array[right] > value_array[largest])){	largest = right;      };      if(largest == pos){	running = 0;      }      else{	//cout<<"switching "<<pos<<" and "<<largest<<endl;	dummyf = value_array[pos];	dummyi = pos_array[pos];	value_array[pos] = value_array[largest];	pos_array[pos] = pos_array[largest];	value_array[largest] = dummyf;	pos_array[largest] = dummyi;	pos = largest;      };  };};void svm_c::maxheap_heapify(SVMINT start, SVMINT size){  // build heap of array working_set[start:start+size-1]  // (i.e. "size" elements starting at "start"th element)  // minheap = 1 <=> maximal element at root   // (i.e. we build the heap of minimal elements)  // v_a[i] = w_s_v[start-1+i], count beginning at 1  SVMFLOAT* value_array = working_set_values+start-1;   SVMINT* pos_array = working_set+start-1;  int running = 1;  SVMINT pos = 1;  SVMINT left, right, largest;  SVMFLOAT dummyf;  SVMINT dummyi;  while(running){      left = 2*pos;      right = left+1;      if((left<=size) && 	 (value_array[left] < value_array[pos])){	largest = left;      }      else{	largest = pos;      };      if((right<=size) && 	 (value_array[right] < value_array[largest])){	  largest = right;      };      if(largest == pos){	running = 0;      }      else{	dummyf = value_array[pos];	dummyi = pos_array[pos];	value_array[pos] = value_array[largest];	pos_array[pos] = pos_array[largest];	value_array[largest] = dummyf;	pos_array[largest] = dummyi;	pos = largest;      };  };};SVMINT svm_c::maxheap_add(SVMINT size, const SVMINT element, const SVMFLOAT value){    if(size < (working_set_size/2+working_set_size%2)){	// add to max_heap	working_set_values[working_set_size/2+size] = value;	working_set[working_set_size/2+size] = element;	size++;	if(size == working_set_size/2+working_set_size%2){	    // build heap	    SVMINT j;	    for(j=size;j>0;j--){		maxheap_heapify(working_set_size/2+j-1,size+1-j);	    };	};    }    else if(value >= working_set_values[working_set_size/2]){	// replace min of max_heap	working_set_values[working_set_size/2] = value;	working_set[working_set_size/2] = element;	maxheap_heapify(working_set_size/2,size);    };    return size;};SVMINT svm_c::minheap_add(SVMINT size, const SVMINT element, const SVMFLOAT value){    if(size<working_set_size/2){	// add to min_heap	working_set_values[size] = value;	working_set[size] = element;	size++;	if(size == working_set_size/2){	    // build heap	    SVMINT j;	    for(j=size;j>0;j--){		minheap_heapify(j-1,size+1-j);	    };	};    }    else if(value < working_set_values[0]){	// replace max of min_heap	working_set_values[0] = value;	working_set[0] = element;	minheap_heapify(0,size);    };    return size;};void svm_c::calculate_working_set(){  /**   *   * Find top and bottom (w.r.t. in_alpha_neg*nabla) feasible    * variables for working_set   *   */  long time_start = get_time();  // reset WSS  if(working_set_size < parameters->working_set_size){    working_set_size=parameters->working_set_size;    if(working_set_size>examples_total) working_set_size = examples_total;  };  SVMINT heap_min=0;  SVMINT heap_max=0;  SVMINT i=0;  SVMFLOAT sort_value;  working_set_values[0] = infinity;  working_set_values[working_set_size/2] = -infinity;  SVMFLOAT the_lambda;  SVMFLOAT the_nabla;  int is_feasible;  int atbound;  SVMINT j;  while(i<examples_total) {    is_feasible = feasible(i,&the_nabla,&the_lambda,&atbound);    if(0 != is_feasible){      if(is_alpha_neg(i) > 0){	sort_value = -the_nabla;  // - : maximum inconsistency approach      }      else{	sort_value = the_nabla;      };      // add to heaps      heap_min = minheap_add(heap_min,i,sort_value);      heap_max = maxheap_add(heap_max,i,sort_value);    };    i++;  };  if(working_set_values[0] >= working_set_values[working_set_size/2]){    if((heap_min>0) &&       (heap_max>0)){      // there could be the same values in the min- and maxheap,      // sort them out (this is very unlikely)      j=0;      i=0;      while(i<heap_min){	// working_set[i] also in max-heap?        j=working_set_size/2;	while((j<working_set_size/2+heap_max) && 	      (working_set[j] != working_set[i])){	  j++;	};	if(j<working_set_size/2+heap_max){          // working_set[i] equals working_set[j]          if(heap_min<heap_max){            // remove j from WS	    working_set[j] = working_set[working_set_size/2-1+heap_max];	    heap_max--;	  }	  else{	    working_set[i] = working_set[heap_min-1];	    heap_min--;	  };	}	else{          i++;	};      };    };  };  if(heap_min+heap_max < working_set_size) {      // condense WS      for(i=0;i<heap_max;i++){	  working_set[heap_min+i] = working_set[working_set_size/2+i];      };      working_set_size = heap_min+heap_max;  };  //  if((working_set_size<examples_total) && (working_set_size>0)){  if(target_count>0){    // convergence error on last iteration?    // some more tests on WS    // unlikely to happen, so speed isn't so important    // are all variables at the bound?    SVMINT pos_abs;    int bounded_pos=1;    int bounded_neg=1;    SVMINT pos=0;    while((pos<working_set_size) && ((1 == bounded_pos) || (1 == bounded_neg))){      pos_abs = working_set[pos];      if(is_alpha_neg(pos_abs) > 0){	if(all_alphas[pos_abs]-Cneg < -is_zero){	  bounded_pos = 0;	};	if(all_alphas[pos_abs] > is_zero){	  bounded_neg = 0;	};      }      else{	if(all_alphas[pos_abs]+Cneg > is_zero){	  bounded_neg = 0;	};	if(all_alphas[pos_abs] < -is_zero){	  bounded_pos = 0;	};      };      pos++;    };    if(0 != bounded_pos){      // all alphas are at upper bound      // need alpha that can be moved upward      // use alpha with smallest lambda      SVMFLOAT max_lambda = infinity;      SVMINT max_pos=examples_total;      for(pos_abs=0;pos_abs<examples_total;pos_abs++){	if(is_alpha_neg(pos_abs) > 0){	  if(all_alphas[pos_abs]-Cneg < -is_zero){	    if(lambda(pos_abs) < max_lambda){	      max_lambda = lambda(pos_abs);	      max_pos = pos_abs;	    };	  };	}	else{	  if(all_alphas[pos_abs] < -is_zero){	    if(lambda(pos_abs) < max_lambda){	      max_lambda = lambda(pos_abs);	      max_pos = pos_abs;	    };	  };	};      };      if(max_pos<examples_total){	if(working_set_size<parameters->working_set_size){	  working_set_size++;	};	working_set[working_set_size-1] = max_pos;      };    }    else if(0 != bounded_neg){      // all alphas are at lower bound      // need alpha that can be moved downward      // use alpha with smallest lambda      SVMFLOAT max_lambda = infinity;      SVMINT max_pos=examples_total;      for(pos_abs=0;pos_abs<examples_total;pos_abs++){	if(is_alpha_neg(pos_abs) > 0){	  if(all_alphas[pos_abs] > is_zero){	    if(lambda(pos_abs) < max_lambda){	      max_lambda = lambda(pos_abs);	      max_pos = pos_abs;	    };	  };	}	else{	  if(all_alphas[pos_abs]+Cneg > is_zero){	    if(lambda(pos_abs) < max_lambda){	      max_lambda = lambda(pos_abs);	      max_pos = pos_abs;	    };	  };	};      };      if(max_pos<examples_total){	if(working_set_size<parameters->working_set_size){	  working_set_size++;	};	working_set[working_set_size-1] = max_pos;      };    };  };  if((working_set_size<parameters->working_set_size) &&     (working_set_size<examples_total)){    // use full working set    SVMINT pos = (SVMINT)((SVMFLOAT)examples_total*rand()/(RAND_MAX+1.0));    int ok;    while((working_set_size<parameters->working_set_size) &&	  (working_set_size<examples_total)){      // add pos into WS if it isn't already      ok = 1;      for(i=0;i<working_set_size;i++){	if(working_set[i] == pos){	  ok=0;	  i = working_set_size;	};      };      if(1 == ok){	working_set[working_set_size] = pos;	working_set_size++;      };      pos = (pos+1)%examples_total;    };  };  SVMINT ipos;  for(ipos=0;ipos<working_set_size;ipos++){    which_alpha[ipos] = is_alpha_neg(working_set[ipos]);  };  time_calc += get_time() - time_start;  return;};void svm_c::project_to_constraint(){  // project alphas to match the constraint  if(biased){    SVMFLOAT alpha_sum = sum_alpha;    SVMINT SVcount=0;    SVMFLOAT alpha;    SVMINT i;    for(i=0;i<examples_total;i++){      alpha = all_alphas[i];      alpha_sum += alpha;      if(((alpha>is_zero) && (alpha-Cneg < -is_zero)) ||	 ((alpha<-is_zero) && (alpha+Cpos > is_zero))){	SVcount++;      };    };    if(SVcount > 0){      // project      alpha_sum /= (SVMFLOAT)SVcount;      for(i=0;i<examples_total;i++){	alpha = all_alphas[i];	if(((alpha>is_zero) && (alpha-Cneg < -is_zero)) ||	   ((alpha<-is_zero) && (alpha+Cpos > is_zero))){	  all_alphas[i] -= alpha_sum;	};      };    };  };};void svm_c::init_working_set(){  // calculate sum  SVMINT i,j;  project_to_constraint();  // check bounds!  if(examples->initialised_alpha()){    if(parameters->verbosity >= 2){      cout<<"Initialising variables, this may take some time."<<endl;    };    for(i=0; i<examples_total;i++){      sum[i] = 0;      at_bound[i] = 0;      for(j=0; j<examples_total;j++){	sum[i] += all_alphas[j]*kernel->calculate_K(i,j);      };    };  }  else{    // skip kernel calculation as all alphas = 0    for(i=0; i<examples_total;i++){      sum[i] = 0;      at_bound[i] = 0;    };      };  if(examples->initialised_alpha()){    calculate_working_set();  }  else{    // first working set is random    j=0;    i=0;    while((i<working_set_size) && (j < examples_total)){      working_set[i] = j;      if(is_alpha_neg(j) > 0){	which_alpha[i] = 1;      }      else{	which_alpha[i] = -1;      };      i++;      j++;    };  };     update_working_set();};void svm_c::put_optimizer_values(){  // update nabla, sum, examples.  // sum[i] += (primal_j^*-primal_j-alpha_j^*+alpha_j)K(i,j)  // check for |nabla| < is_zero (nabla <-> nabla*)  //  cout<<"put_optimizer_values()"<<endl;  SVMINT i=0;   SVMINT j=0;  SVMINT pos_i;  SVMFLOAT the_new_alpha;  SVMFLOAT* kernel_row;  SVMFLOAT alpha_diff;  long time_start = get_time();  pos_i=working_set_size;  while(pos_i>0){    pos_i--;    if(which_alpha[pos_i]>0){      the_new_alpha = primal[pos_i];    }    else{      the_new_alpha = -primal[pos_i];    };    // next three statements: keep this order!    i = working_set[pos_i];    alpha_diff = the_new_alpha-all_alphas[i];    all_alphas[i] = the_new_alpha;    if(alpha_diff != 0){      // update sum ( => nabla)      kernel_row = kernel->get_row(i);      for(j=0;j<examples_total;j++){	sum[j] += alpha_diff*kernel_row[j];      };    };  };  time_update += get_time() - time_start;};