example_6.md 20.7 KB

使用过程提示

Tips:

  • 您可点击右下角“下一步”,查看后续的建模讲解和源代码。
  • 本教程文档是 .md 格式,此讲解窗口采用阿里云 CloudShell 的teachme指令打开,如命令行输入 teachme doc/fileName.md 命令打开。
  • CloudShell 默认模式是登录失效后线上机器内信息删除,建议您在本地机器上编辑和保存自己的代码,然后通过 CloudShell 左上角上传文件的方式上传,也可进行下载。CloudShell 窗口关闭后原登录信息会清除,建议同时开两个窗口,防止误操作关闭;同时不建议离开窗口太久导致登录失效。
  • 如果想体验运行MindOpt求解器代码,请①在天池-决策优化MindOpt网址申请免费的授权Token,并替换掉示例代码里的Token;②并安装MindOpt优化求解器的SDK:安装指导。如已安装,可跳过。

^___^ 还没体验过安装和运行求解器的同学,可以直接点击链接:一键安装MindOpt求解器,并一键用令行求解.mps或.lp文件~~

案例问题背景

分类

分类是机器学习领域中最基本的任务之一。其目的是建立输入向量x与分类变量y之间的映射关系。例如:

  • 在计算机视觉中,我们需要把一张张图片根据其内容分类为"动物","轮船", "植物"等类别,供下游的任务使用。在这个应用中,x就是图片像素组成的向量,而分类变量y则是指向其具体类别的标量。
  • 我们会把收到的电子邮件根据其标题,发件人,内容,附带图片或链接等分类为"重要邮件", "推销邮件", "垃圾邮件"等。在这个应用中,x就是电子邮件的向量化输入,y则是指向具体类别的标量。

支持向量机(Support Vector Machine, SVM)

SVM是一类按监督学习方式对数据进行分类的线性分类器。其核心思想是在特征空间内找到使不同类别的样本间距最大的决策边界。SVM模型中经常会引入正则化项(regularization term)来提高模型鲁棒性或者引入先验知识。L1 - regularized SVM就是在模型中加入L1正则化项(也即 ||x||1 ),将特征向量的稀疏性这个先验知识引入到模型中,进而提高分类效率。

问题模型

image.png

建模为线性规划问题

image.png image.pngimage.png

Tips:案例内容可能参考自互联网,如有侵权,请联系我们删除。

准备案例数据

选择1. 示例数据

① 示例数据存储在了本文档git仓库的data文件夹里,无需上传。示例数据:data/mnist.scale100_tianchi.zip

②或者自己生产数据,根据后文介绍的步骤下载mnist.scale数据集、libSVM和示例代码来产生数据。可通过CloudShell左上角的上传图标来上传。 上传文件图标截图: image.png

已有的示例数据数据后解压缩数据:

cd ~
cp mindopt-open-examples/data/mnist.scale100_tianchi.zip ~
unzip mnist.scale100_tianchi.zip
cd mnist.scale100_tianchi
ls

压缩包文件如图所示 image.png

选择2. 通过mnist.scale数据集和libSVM生成数据(含代码)

基本信息:

  • 数据数量: 60,000(其中10,000是测试集)
  • 特征向量维度: 780
  • 类别数量: 10

线性规划建模

在本节中,我们从mnist.scale数据集中抽取部分子集来作为 L1- regularized SVM问题的输入数据。然后我们从这些数据中构造线性规划问题中的A,b,c 并将这些变量写入文件中留待后面使用。我们令SVM的超参数.

以下代码会将 L1 - regularized SVM建模为线性规划问题,并保存变量. ​

运行以下代码后,我们会得到一个文件夹mnist.scale1000_tianchi(注意这个是1000)。其中包含4个文件,分别是meta, A, b, c. LP问题就由这几个文件来确定。 ​

代码示例如下,代码的前面注释讲解了使用的步骤:

'''
L1SVM2LP.py -- transform L1 regularzied SVM to an LP problem

Prerequisite:
1. mnist_scale dataset, and 
2. the libsvm library to help load data.

To prepare mnist_scale and libsvm library:
1. download mnist_scale using the folowing command:
wget https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass/mnist.scale.bz2. 
Use 'bzip2 -d mnist.scale.bz2' to unzip the data.
2. put dataset mnist_scale to the same path as L1SVM2LP.py
3. download libsvm from https://github.com/cjlin1/libsvm
4. put the filefolder libsvm to the same path as L1SVM2LP.py
5. install libsvm and its python interface as illustrated in https://github.com/cjlin1/libsvm

After all the above steps, run the code as follows:
python L1SVM2LP.py --data ./mnist.scale --sample_size 1000

When the code finishes, the following filefolder containing LP models is achieved:
./mnist.scale1000_tianchi
    - meta 
    - A
    - b
    - c
'''

import sys
sys.path.append('./libsvm/python')

import argparse
import numpy as np
import scipy.sparse as sps
from svmutil import *

import time
import os
import shutil

parser = argparse.ArgumentParser()
parser.add_argument("--data", help="the path of dataset", default="")
parser.add_argument("--sample_size", help="the size of data to be sampled", type=int, default=1000)
args = parser.parse_args()

# Read dataset
file_name = args.data
y, X = svm_read_problem(file_name, return_scipy = True)

print('Loaded Data statistics: Sample size:{}, Feature size:{}'.format(X.shape[0], X.shape[1]))

sample_size = args.sample_size
X = X[:sample_size,:]

# Hyper-parameter
lmd = 1

# Basic data stats
M, D = X.shape
K = int(y.max())+1
print('Sampled Data statistics: Sample size:{}, Feature size:{}, Number of classes:{}'.format(M, D, K))

# Construct c
n = 2*K*D + M
c = np.ones(n)
c[:2*K*D] = lmd/2

# Construct A and b
ROW, COL, DATA = [], [], []
cnt = 0
b = np.zeros(K*M)

for i in range(M):

    if i%1000 == 0:
        print('{}/{}'.format(i,M), end='\r')

    yi = int(y[i])
    xi = X[i,:]

    for k in range(K):

        if k == yi:
            b[cnt] = -1.0

            data = np.concatenate([-xi.data, xi.data, np.array([-1])])
            row = np.ones(len(data))*cnt

            pyi_col = yi*D+xi.indices
            qyi_col = K*D+pyi_col
            xi_col = np.array([2*K*D+i])
            col = np.concatenate([pyi_col,qyi_col,xi_col])

        else:
            data = np.concatenate([-xi.data/2, xi.data/2, -xi.data/2, xi.data/2, np.array([-1])])
            row = np.ones(len(data))*cnt

            pyi_col = yi*D+xi.indices
            qyi_col = K*D+pyi_col
            pk_col = k*D+xi.indices
            qk_col = K*D+pk_col
            xi_col = np.array([2*K*D+i])
            col = np.concatenate([pyi_col,qyi_col,pk_col,qk_col,xi_col])

        ROW.append(row)
        COL.append(col)
        DATA.append(data)

        cnt+=1

ROW_np = np.concatenate(ROW)
COL_np = np.concatenate(COL)
DATA_np = np.concatenate(DATA)
m = int(ROW_np[-1]) + 1

# Write data info files
output_path = file_name + str(sample_size) + '_tianchi'
if os.path.exists(output_path):
    print('file exists')
    shutil.rmtree(output_path)  
    print('file removed')
os.mkdir(output_path)
print('Empty file created')

# write meta
meta = open(output_path+"/meta", "w")  
L = ["n {}\n".format(n), "m {}\n".format(m)]
meta.writelines(L)

# write A
A_file = open(output_path+"/A", "w")
for i in range(len(ROW_np)):
    if i%10000 == 0:
        print('{}/{}'.format(i,len(ROW_np)), end='\r')
    A_file.write("{}\t{}\t{}\n".format(int(ROW_np[i]), COL_np[i], DATA_np[i]))

# write b
b_file = open(output_path+"/b", "w")
L = ["{}\n".format(b[i]) for i in range(len(b))]
b_file.writelines(L)

# write c
c_file = open(output_path+"/c", "w")
L = ["{}\n".format(c[i]) for i in range(len(c))]
c_file.writelines(L)

print('Data has been written into files.\n')

求解线性规划-Python代码

在本节中,我们先用mindopt的python接口来从mnist.scale1000_tianchi读入A, b, c,建立LP模型。然后,我们调用mindopt的client/server结构来进行求解。后一个步骤又将分成两个步骤完成:

  1. 在client端读入A,b,c,建立LP模型,并发送至server端供server求解
  2. 将LP的solution从server端取回client端。

可以cd进数据文件夹目录内来运行程序,如提供的示例数据:

cd mnist.scale100_tianchi

步骤一: Submit Task​

创建py文件和运行代码

复制后文的的Python代码,代码框的有上方有复制按钮,然后创建一个文件复制入,并修改代码里面的 line 92 的Token为你自己的Token。

创建一个.py文件如下。(除示例nano指令外,编辑文件可使用vi、vim、nano、emacs等不同编辑器指令,或touch创建文件,也可采用CloudShell右上角的“笔”的编辑图标来选择对应的文档进行新增和修改。)

nano mindopt_example6_submit.py

然后复制后文的代码拷入。根据提示来修改和保存文件,如ctrl+o保存,然后看到对应名字OK后摁enter即可,如ctrl+x退出,如有修改保存按Y,再看到对应名字OK后摁enter即可退出。

也可采用CloudShell右上角的“笔”的编辑图标来选择对应的文档进行修改。

运行如:

python mindopt_example6_submit.py

注:问题提交远端计算Server后,会需要求解时间,请耐心等待。由于计算资源限制,同一Token同时间只能求解一个问题,请勿同时段提交太多次。如果代码运行失败,可能是mindopt环境变量链接失败,可重新走一遍安装步骤(安装指导)。

运行以上代码后,我们会得到如下结果。该结果会返回提交任务的Job ID. 我们将会使用该ID来从server中拉取求解LP的solution. Screen Shot 2020-12-29 at 8.04.13 PM.png

mindopt_example6_submit.py 代码:

Tips:  如果想体验运行MindOpt求解器代码,请先在天池-决策优化MindOpt-免费使用上申请授权Token,并替换掉示例代码里的Token。

# mindopt_example6_submit.py is to submit LP model to the remote server
# put mindopt_example6_submit.py *inside* mnist.scale1000_tianchi, and run
# python mindopt_example6_submit.py

from mindoptpy import *

# parameters
file_path = "./tmp/"
job_id = ""
MDO_INFINITY = MdoModel.get_infinity()

# -------- Step 1. Establish LP model -----------

model = MdoModel()
model.set_int_attr("MinSense", 1)

# read the size of A
f = open("meta", "r")

A_size = []
for line in f:
    num = int(line.split(' ')[-1][:-1])
    A_size.append(num)

m, n = A_size[1], A_size[0]
print('Number of constraint is:', m)
print('Number of variables  is:', n)

f.close()

# read c
c = []
f = open("c", "r")

for line in f:
    c_element = float(line[:-1])
    c.append(c_element)

f.close()

# read b
b = []
f = open("b", "r")

for line in f:
    b_element = float(line[:-1])
    b.append(b_element)

f.close()

# Add empty constraints.
print('Adding constraints...')
cons = []
for j in range(m):
    cons_name = "c" + str(j)
    cons.append(model.add_cons(-MDO_INFINITY, b[j], None, cons_name))

# Input columns. 
f = open("A", "r")

col = []
for j in range(n):
    col.append(MdoCol())

for idx, line in enumerate(f):

    line_lst = line.split('\t')
    row_id, col_id, val = int(line_lst[0]), int(line_lst[1]), float(line_lst[2][:-1])
    col[col_id].add_term(cons[row_id], val)

# Add variables.
# Note that the nonzero elements are inputted in a column-wise order here.
print('Adding variables...')
x = []

for j in range(n):
    x_name = "x" + str(j)
    x.append(model.add_var(0.0, MDO_INFINITY, c[j], col[j], x_name, False))

# Specify parameters.
model.set_int_param("NumThreads", 4)
model.set_real_param("MaxTime", 3600.0)

print('LP model is established.\n')


# -------- Step 2. Input parameters related to the remote computing server. -------
model.set_str_param("Remote/Token", "xxxxxxxxxxxxTokenxxxxxxxx")# change to your token 
model.set_str_param("Remote/Desc", "tianchi example6 L1SVM")
model.set_str_param("Remote/Server", "mindopt.tianchi.aliyun.com") # change to your server ip address
model.set_str_param("Remote/File/Path", file_path)

# -------- Step 3. Upload the serialized model and parameters to server, and then optimize the model.  ---- 
job_id = model.submit_task()
if job_id == "":
    print("ERROR: Empty job ID.")
else:
    print("Job was submitted to server successfully.")
    print("User may query the optimization result with the following job ID: {}".format(job_id))

步骤二: Retrieve Task

创建py文件和运行代码

复制后文的的Python代码,代码框的有上方有复制按钮,然后创建一个文件复制入,然后修改两处:

①修改代码里面的 line 39 的Token为你自己的Token

②Submit的代码运行成功会给出一个job ID,请复制此ID,替换 line 26 的jobID为你提交后获取的ID。

操作如下: 创建一个.py文件如下。(除示例nano指令外,编辑文件可使用vi、vim、nano、emacs等不同编辑器指令,或touch创建文件,也可采用CloudShell右上角的“笔”的编辑图标来选择对应的文档进行新增和修改。)

nano mindopt_example6_retrieve.py

然后复制后文的代码拷入。根据提示来修改token和jobID和保存文件,如ctrl+o保存,然后看到对应名字OK后摁enter即可,如ctrl+x退出,如有修改保存按Y,再看到对应名字OK后摁enter即可退出。

也可采用CloudShell右上角的“笔”的编辑图标来选择对应的文档进行修改。

运行如:

python mindopt_example6_retrieve.py

注:问题提交远端计算Server后,会需要求解时间,请耐心等待。由于计算资源限制,同一Token同时间只能求解一个问题,请勿同时段提交太多次。如果代码运行失败,可能是mindopt环境变量链接失败,可重新走一遍安装步骤(安装指导)。

mindopt_example6_retrieve.py 代码:

Tips:  如果想体验运行MindOpt求解器代码,请先在天池-决策优化MindOpt-免费使用上申请授权Token,并替换掉示例代码里的Token。

注意修改line 39、26的Token和jobID。

"""
/**
 *  Description
 *  -----------
 *
 *  Check the solution status, download the solution, and populate the result.
 */
"""

# mindopt_example6_retrieve.py is to retrieve LP solution from the remote server
# put mindopt_example6_retrieve.py *inside* mnist.scale1000_tianchi, and run
# python mindopt_example6_retrieve.py

from mindoptpy import *
import time


if __name__ == "__main__":

    # Serialized files, must be the same in the submission code
    file_path = "./tmp/"
    # Output solution file
    soln_file = "./svm.sol"
    job_id = "xxxxxxxxxYour jodIDxxxxxxxxxx" # job_id is achieved from the above submit result
    val = 0.0
    status = "Submitted"

    # Step 1. Create a model and change the parameters.
    model = MdoModel()

    try:        

        # Step 2. Input parameters related to remote computing. 
        model.set_str_param("Remote/Token", "xxxxxxxxxxxxTokenxxxxxxxx")# change to your token
        model.set_str_param("Remote/Server", "mindopt.tianchi.aliyun.com")
        model.set_str_param("Remote/File/Path", file_path)

        # Step 3. Upload serialize model and parameter to server, and then optimize the model.
        while status == 'Submitted' or status == 'Solving': 
            status, model_status, result, has_soln = model.retrieve_task(job_id)

            # Sleep for 10 seconds.
            time.sleep(10)

        # model_status_details = model.explain_status(model, model_status, model_status_details);
        result_details = model.explain_result(result)
        print(" - Job status             : {}".format(status))
        # print(" - Model status           : {0} ({1})".format(model_status_details, model_status))
        print(" - Optimization status    : {0} ({1})".format(result_details, result))
        print(" - Solution availability  : {0}".format("available" if has_soln else "not available"))

        if has_soln:
            print("\nPopulating solution.")

            model.display_results()
            print(" - Primal objective value : {}".format(model.get_real_attr("PrimalObjVal")))
            print(" - Dual objective value   : {}".format(model.get_real_attr("DualObjVal")))
            print(" - Solution time          : {} sec.".format(model.get_real_attr("SolutionTime")))
            model.write_soln(soln_file)

    except MdoError as e:
        print("Received Mindopt exception.")
        print(" - Code          : {}".format(e.code))
        print(" - Reason        : {}".format(e.message))
    except Exception as e:
        print("Received exception.")
        print(" - Reason        : {}".format(e))
    finally:
        # Step 5. Free the model.
        model.free_mdl()

运行结果

运行Submit的代码后,结果示意如下: image.png

运行Retrieve代码后,结果示意如下: image.png 上图显示了求解的经过和时间。而LP问题的解则在新生成的文件svm.sol中。