二次計画法を解決するために Quadprog を実装する適切な方法は何だろうと思っていました。
次の質問があります（インターネットから取得）、次のhttp://cbio.ensmp.fr/~thocking/mines-course/2011-04-01-svm/svm-qp.pdfも見ていました
この問題を解決する適切な方法は何でしょうか? 上記のような質問を受けた場合、このチュートリアルは解決に役立ちますか? http://www.r-bloggers.com/solving-quadratic-progams-with-rs-quadprog-package/
主な最適化問題に基づく線形 C-SVM の実装を次に示します。
min_{beta_0, beta, zeta} 1/2 w^T w + C sum_{i = 1}^N zeta_i
subject to:
y_i (w^T x_i + b) >= 1 - zeta_i, for all i = 1, 2, ..., N
zeta_i >= 0, for all i = 1, 2, ..., N
はNデータ ポイントの数です。
を使用してこれを解決することは、内点アルゴリズムに依存するquadprogため、ある程度教育的な演習であることに注意してください。実際には、SVM の特定のプロパティを利用する Platt の SMO などの特殊なアルゴリズムが使用されます。quadprog最適化問題。
を使用するにはquadprog、上記の方程式を考えると、最適化問題を指定する行列とベクトルを設定する必要があります。
ただし、1 つの問題はquadprog、二次関数に現れる行列が正定値である必要があることです (たとえば、http://www.r-bloggers.com/more-on-quadratic-progamming-in-r/を参照) 。ただし、ここで使用される実装では、切片beta_0とzeta_iが二次関数に現れないため、正の半正定値になります。この問題を回避するために、マトリックス内のこれらの値に対応する対角要素を非常に小さな値に設定しました。
サンプル コードをセットアップするには、spamデータセット、バイナリ分類問題を使用します。
library(kernlab) # for the spam data
# Load the input data to be used
data(spam)
# Use only a subset of the data (20%)
spam <- spam[sample(nrow(spam), round(0.2 * nrow(spam)), replace = FALSE), ]
# Retrieve the features and data
X <- spam[, 1:(ncol(spam) - 1)]
Y_f <- spam[, ncol(spam)]
Y <- 2 * (as.numeric(Y_f) - 1.5) # {-1, 1}
# Sample size
N <- nrow(X)
# Number of dimensions
n_d <- ncol(X)
# Value of the regularization parameter
C <- 1
最適化問題を設定するには、 package で採用されている形式に注意してquadprogください。
#
# Formulation: min(−d^T * b + 0.5 * b^T * D * b) with the constraints A^T * b >= b_0
#
# solve.QP(Dmat, dvec, Amat, bvec, meq=0, factorized=FALSE)
#
# Arguments
# Dmat: matrix appearing in the quadratic function to be minimized.
# dvec: vector appearing in the quadratic function to be minimized.
# Amat: matrix defining the constraints under which we want to minimize the quadratic function.
# bvec: vector holding the values of b0 (defaults to zero).
# meq: the first meq constraints are treated as equality constraints, all further as inequality
# constraints (defaults to 0).
# factorized logical flag: if TRUE, then we are passing R−1 (where D = RT R) instead of the
# matrix D in the argument Dmat.
#
次に、パラメーター ベクトルを次のように整理します。
# b = (beta_0, beta, zeta),
# where: beta_0 in R, beta in Re^n_d, zeta in Re^N
そのような：
d <- c(0, rep(0, n_d), rep(-C, N)) # -C * sum(zeta)
# Need a work-around for the matrix D, which must be positive definite (being
# positive semi-definite is not enough...)
# See http://www.r-bloggers.com/more-on-quadratic-progamming-in-r/
eps <- 1e-10 # this will ultimately be the lowest eigenvalue of matrix D (with multiplicity N + 1)
D <- diag(c(eps, rep(1, n_d), rep(eps, N))) # beta^T * beta
#
# Matrix specifying the constraints
# For zeta_i > 0:
# beta_0 | beta | zeta
# A_1 = [ 0, 0, 0, ..., 0, 1, 0, 0, ..., 0]
# [ 0, 0, 0, ..., 0, 0, 1, 0, ..., 0]
# [ 0, 0, 0, ..., 0, 0, 0, 1, ..., 0]
# ...
# [ 0, 0, 0, ..., 0, 0, 0, 0, ..., 1]
# where matrix A_1 has N rows, and N + n_d + 1 columns
#
# For beta_0 * y_i + beta^T * x_i * y_i + zeta_i >= 1:
# beta_0 | beta | zeta
# A_2 = [ y_1, y_1 * x_{1, 1}, y_1 * x_{2, 2}, ..., y_1 * x{i, n_d}, 1, 0, 0, ..., 0]
# [ y_2, y_2 * x_{2, 1}, y_2 * x_{2, 2}, ..., y_2 * x{i, n_d}, 0, 1, 0, ..., 0]
# ...
# [ y_N, y_N * x_{N, 1}, y_2 * x_{N, 2}, ..., y_N * x{N, n_d}, 0, 0, 0, ..., 1]
#
I_N <- diag(N) # N x N identity matrix
A_1 <- cbind(matrix(0, ncol = n_d + 1, nrow = N), I_N) # zeta_i > 0, for all i; N rows
A_2 <- as.matrix(cbind(as.matrix(Y), X * as.matrix(Y)[, rep(1, n_d)], I_N)) # zeta_i + beta_0 * y_i + beta^T * x_i * y_i >= 1, for all i; N rows
rownames(A_1) <- NULL; rownames(A_2) <- NULL
colnames(A_1) <- NULL; colnames(A_2) <- NULL
A <- t(rbind(A_1, A_2))
b_0 <- c(rep(0, N), rep(1, N))
最後に、最適化問題を解き、パラメーター値を取得します。
library(quadprog)
results <- solve.QP(D, d, A, b_0)
# Retrieve the results
b_optim <- results$solution
beta_0 <- b_optim[1]
beta <- b_optim[1 + (1:n_d)]
zeta <- b_optim[(n_d + 1) + (1:N)]
その後、行列が与えられるX_testと、モデルを使用して次のように予測できます。
Y_pred <- sign(apply(X_test, 1, function(x) beta_0 + sum(beta * as.vector(x))))