libsvm代码阅读：关于Solver类分析（二）

如果你看完了上篇博文的伪代码，那么我们就可以开始谈谈它的源代码了。

// An SMO algorithm in Fan et al., JMLR 6(2005), p. 1889--1918
// Solves:
//
//	min 0.5(\alpha^T Q \alpha) + p^T \alpha
//
//		y^T \alpha = \delta
//		y_i = +1 or -1
//		0 <= alpha_i <= Cp for y_i = 1
//		0 <= alpha_i <= Cn for y_i = -1
//
// Given:
//
//	Q, p, y, Cp, Cn, and an initial feasible point \alpha
//	l is the size of vectors and matrices
//	eps is the stopping tolerance
//
// solution will be put in \alpha, objective value will be put in obj
//
class Solver {
public:
	Solver() {};
	virtual ~Solver() {};//用虚析构函数的原因是：保证根据实际运行适当的析构函数

	struct SolutionInfo {
		double obj;
		double rho;
		double upper_bound_p;
		double upper_bound_n;
		double r;	// for Solver_NU
	};

	void Solve(int l, const QMatrix& Q, const double *p_, const schar *y_,
		   double *alpha_, double Cp, double Cn, double eps,
		   SolutionInfo* si, int shrinking);
protected:
	int active_size;//计算时实际参加运算的样本数目，经过shrink处理后，该数目小于全部样本数
	schar *y;	    //样本所属类别，该值只能取-1或+1。
	double *G;		// gradient of objective function = （Q alpha + p）
	enum { LOWER_BOUND, UPPER_BOUND, FREE };
	char *alpha_status;	// LOWER_BOUND, UPPER_BOUND, FREE 
	double *alpha;		//
	const QMatrix *Q;	
	const double *QD;
	double eps;		//误差限
	double Cp,Cn;
	double *p;
	int *active_set;
	double *G_bar;		// gradient, if we treat free variables as 0
	int l;
	bool unshrink;	// XXX
	//返回对应于样本的C。设置不同的Cp和Cn是为了处理数据的不平衡
	double get_C(int i)
	{
		return (y[i] > 0)? Cp : Cn;
	}

	void update_alpha_status(int i)
	{
		if(alpha[i] >= get_C(i))
			alpha_status[i] = UPPER_BOUND;
		else if(alpha[i] <= 0)
			alpha_status[i] = LOWER_BOUND;
		else alpha_status[i] = FREE;
	}
	bool is_upper_bound(int i) { return alpha_status[i] == UPPER_BOUND; }
	bool is_lower_bound(int i) { return alpha_status[i] == LOWER_BOUND; }
	bool is_free(int i) { return alpha_status[i] == FREE; }
	void swap_index(int i, int j);//交换样本i和j的内容，包括申请的内存的地址
	void reconstruct_gradient();  //重新计算梯度。
	virtual int select_working_set(int &i, int &j);//选择工作集
	virtual double calculate_rho();
	virtual void do_shrinking();//对样本集做缩减。
private:
	bool be_shrunk(int i, double Gmax1, double Gmax2);	
};

libsvm代码阅读：关于Solver类分析（二）

原文：http://blog.csdn.net/linj_m/article/details/19705911