2020-05-20

gcc优化

在优化之前要提醒的内容：

1.任何级别的优化都将带来代码结构的改变。例如：对分支的合并和消除，对公用子表达式的消除，对循环内load/store操作的替换和更改等，都将会使目标代码的执行顺序变得面目全非，导致调试信息严重不足。

2.内存操作顺序改变所带来的问题：在O2优化后，编译器会对影响内存操作的执行顺序。例如：-fschedule-insns允许数据处理时先完成其他的指令；-fforce-mem有可能导致内存与寄存器之间的数据产生类似脏数据的不一致等。对于某些依赖内存操作顺序而进行的逻辑，需要做严格的处理后才能进行优化。例如，采用volatile关键字限制变量的操作方式，或者利用barrier迫使cpu严格按照指令序执行的。

表示程序性能的标准：CPE（越小性能越优）延迟界限　吞吐量界限

CPE指数只是针对循环代码而言的（几乎可以说代码性能优化就是对循环的优化），它指处理数据的每个元素所消耗的周期数。之所以使用每个元素的周期数而不是每个循环的周期数来度量，是因为循环次数可能随循环展开的程度不同而变化。

延迟界限：当一系列操作必须按照严格的顺序执行时，处理每个元素所历经的关键路径（最长路径）的周期数。当数据相关问题限制了指令级并行的能力时，延迟界限能够限制程序性能。

吞吐量界限：处理器功能单元全力运行时的原始计算能力。比如处理器具有两个能同时做乘法的单元，对于只有1次乘/元素的循环而言，此时的吞吐量界限就是0.5。吞吐量界限是程序性能的终极界限。

程序转换的优化安全：

内存别名使用：

void twiddle1(long*xp,long*yp){
    *xp+=*yp;
    *xp+=*yp
}
void twiddle2(long*xp,long*yp){
    *xp+=2* *yp
}

如果*xp=*yp，则twiddle1会是增加四倍（xp翻倍的同时yp也翻倍），twidde2则是增加三倍，编译器不知道xp会不会等于yp，所以无法将代码从twiddle1优化为twiddle2

2.函数调用合并

long counter=0;
long f(){
    return counter++;
}

long func1(){
    return f()+f()+f()+f();
}

long func2(){
    return 4*f();
}

func1的结果是0+1+2+3=6，而func2的结果是4*0=0

循环展开技术（－O3）

一种牺牲程序的尺寸来加快程序的执行速度的优化方法。可以由程序员完成，也可由编译器自动优化完成。循环展开最常用来降低循环开销，为具有多个功能单元的处理器提供指令级并行。也有利于指令流水线的调度。

// 计算p[i]=a[0]+...a[i]
void psum1(float a[],float p[],long n){
    long i;
    p[0]=a[0];
    for(i=1;i<n;i++){
        p[i]=p[i-1]+a[i]
    }
}

void psum1(float a[],float p[],long n){
    long i;
    p[0]=a[0];
    for(i=1;i<n;i++){
        float mid_val=p[i-1]+a[i];
        p[i]=mid_val;
        p[i+1]=mid_val+a[i+1];
    }
    // 对奇数值的特殊处理
    if(i<n){
        p[i]=p[i-1]+a[i];  
    }
}

upload successful

gcc　参数优化

-Og 使用基本的优化
-O1 … -O3 使用更大量的优化，但是也可能增加程序的规模（主要以O1为主）

// 通过修改data_t修改数据类型
#define data_t int
// 通过修改OP来修改执行的是加还是乘
#define IDENT 0
#define OP +
void combine1(vec_ptr v,data_t *dest){
    long i;
    
    *dest=IDENT;
    for(i=0;i<vec_length(v);i++){
        data_t val;
        get_vec_element(v,i,&val);
        *dest=*dest OP val;
    }
}

upload successful

频繁使用数据缓存（针对全局变量和数组保存中间结果）

// combine1
for(i=0;i<vec_length(v);i++){
    ......
}

// combine2
void combine2(vec_ptr v,data_t *dest){
    long i;
    long length=get_vec_element(v,i,&val);
  
    *dest=IDENT;
    for(i=0;i<length;i++){
        data_t val;
        get_vec_element(v,i,&val);
        *dest=*dest OP val;
    }
}

upload successful

减少过程调用

把函数调用取消直接访问元素，性能没啥提升。

data_t* get_vec_start(vec_ptr v){
        return v->data;
}
// combine3
void combine3(vec_ptr v,data_t *dest){
    long i;
    long length = get_vec_element(v,i,&val);
    data_t *data = get_vec_start(v);

    *dest=IDENT;
    for(i=0;i<length;i++){
        data_t val;
        get_vec_element(v,i,&val);
        *dest=*dest OP data[i];
    }
}

upload successful

使用临时变量替代传入的指针变量（临时变量方便寄存器优化而不是内存地址读取数据）

void combine4(vec_ptr v,data_t *dest){
        long i;
        long length = vec_length(v);
        data_t *data=get_vec_start(v);
        data_t acc=IDENT;

        for(i=0;i<length;i++){
                acc=acc OP data[i];
        }
        *dest=acc;
}

upload successful

k*n循环展开

步长为二，一个循环（2*1）

void combine5(vec_ptr v,data_t *dest){
        long i;
        long length = vec_length(v);
        long limit = length-1;
        data_t *data=get_vec_start(v);
        data_t acc=IDENT;
        
        // combine 2 elements at a time
        for(i=0;i<limit;i+=2){
                acc=(acc OP data[i])OP data[i+1];
        }
        // Finish any remaining elements
        for(;i<length;i++){
                acc = acc OP data[i];
        }
        *dest=acc;
}

步长为二，两个循环（2*2）

void combine6(vec_ptr v,data_t *dest){
        long i;
        long length = vec_length(v);
        long limit = length-1;
        data_t *data=get_vec_start(v);
        data_t acc0=IDENT;
        data_t acc1=IDENT;        
        // combine 2 elements at a time
        for(i=0;i<limit;i+=2){
                acc0=(acc0 OP data[i]);
                acc1=(acc1 OP data[i+1]);
        }
        // Finish any remaining elements
        for(;i<length;i++){
                acc0 = acc0 OP data[i];
        }
        *dest=acc0 OP acc1;
}

重新结合变换（k*1a）

void combine7(vec_ptr v,data_t *dest){
        long i;
        long length = vec_length(v);
        long limit = length-1;
        data_t *data=get_vec_start(v);
        data_t acc=IDENT;
        
        // combine 2 elements at a time
        for(i=0;i<limit;i+=2){
                acc=acc OP (data[i] OP data[i+1]);
        }
        // Finish any remaining elements
        for(;i<length;i++){
                acc = acc OP data[i];
        }
        *dest=acc;
}

upload successful

寄存器溢出

现代ｘ８６架构拥有１６个寄存器，还有１６个ＹＭＭ寄存器可以存储浮点型数，如果需要缓存的变量超过该个数则需要将数据存放到内存，性能可能会下降。

条件控制转移（if…else）　VS　条件传送（ ? … : … ）

条件控制转移指根据代码的条件结果来选择执行的路径，条件传送指先把结果执行，在根据条件结果选择结果值。在相同的情况下，条件传送性能比条件控制转移高。

//  CPE 13.5
void minmax1(long a[],long b[],long n){
    long i;
    for(i=0;i<n;i++){
        long t=a[i];
        a[i]=b[i];
        b[i]=t;
    }
}

// CPE 4.0
void minmax2(long a[],long b[],long n){
    for(i=0;i<n;i++){
        long min=a[i]<b[i]?a[i]:b[i];
        long max=a[i]<b[i]?b[i]:a[i];
        a[i]=min;
        b[i]=max;
    }
}

2020-05-17

const

　作用域：

默认状态下，Const对象仅在文件内有效。所以不同文件的const对象不是同一个对象，即使名字相同，因为这样才能避免重复定义。

那为了使一个非常量表达式的const变量在不同文件之间可以共享，可以使用extern来解决问题。

1	extern const int temp;

两种一样的写法

const int a; int const a; 这两个写法是等同的

const int *a; int const* a;含义相同。

　常量指针和指针常量

常量指针声明：const int * p; int const * p;（指针指向常量）

具有只能够读取内存中数据，却不能够修改内存中数据的属性的指针，称为指向常量的指针。

指针常量声明：int * const p=&a;（指针指向常量地址）

指针常量是指指针所指向的位置不能改变，即指针本身是一个常量，但是指针所指向的内容可以改变。

指针常量必须在声明的同时对其初始化，不允许先声明一个指针常量随后再对其赋值，这和声明一般的常量是一样的。
1
2
3
4
5
6
7
int num=0;

int*const cur=&num;//一直指向num

const double pi=3.1415;

const double * const pip=π//指向常量的常量指针。

2020-05-15

memset与虚函数

class BaseParameters
{
public:
  virtual void reset() {}
};
class MyParameters : public BaseParameters
{
public:
  int data[3];
  int buf[3];
};
MyParameters my_pars;
memset(&my_pars, 0, sizeof(my_pars));
BaseParameters* pars = &my_pars;
//.....
MyParameters* my = dynamic_cast<MyParameters*>(pars);

初始化数据结构MyParameters里的data和buf，正常来说需要初始化的内存空间是sizeof(int) 3 2 = 24字节，但是使用memset初始化MyParameters类型的数据结构时，sizeof(my_pars)却是28字节。

因为为了实现多态机制，C++对有虚函数的对象会包含一个指向虚函数表(V-Table)的指针，当使用memset时，会把该虚函数表的指针也初始化为0，而dynamic_cast也使用RTTI技术，运行时会使用到V-Table，可此时由于与V-Table的链接已经被破坏，导致程序发生异常。

2020-05-15

归并排序为什么要用败者树？

https://www.zhihu.com/question/35144290/answer/148681658

堆排序的时间复杂度跟败者树的时间复杂度一致为什么不用堆？$O(nklog_k(n) + k) =O(nklog_kn)$

其实一开始就是用堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的左右两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。这时人们想能否简化比较过程，这时就有了胜者树。

这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。而胜者树在节点上升的时候首先需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树。

在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。所以总的来说，减少了访存的时间。（拿空间换时间）

原因：胜者树以小为胜的话，如果比较兄弟节点发现更小直接替代父节点即可，如果更大则兄弟节点胜出。
败者树比较父节点指向的点发现更大直接替换败者即可，更小则不需要替换然后接着上移。

二者都是顶点缺失，都要从底部叶节点遍历到顶点。

最后就是现在程序的主要瓶颈在于访存了，计算倒几乎可以忽略不计。

2020-05-15

置换-选择排序

http://data.biancheng.net/view/78.html

如果内存为W，则内排序算法最多只能对大小略小于W的段进行排序。置换-选择排序可以降低段的个数

置换—选择排序算法的具体操作过程为：

首先从有24个记录的初始文件中输入 6 个记录到内存工作区中；
从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录；
然后将 MINIMAX 记录输出到归并段文件中；
此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；
从内存工作区中的所有比 MINIMAX 值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录；
重复过程 3—5，直至在内存工作区中选不出新的 MINIMAX 记录为止，由此就得到了一个初始归并段；
重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段。

upload successful

具体步骤：

首先输入前 6 个记录到内存工作区，其中关键字最小的为 29，所以选其为 MINIMAX 记录，同时将其输出到归并段文件中，如下图所示：

upload successful

2.此时初始文件不为空，所以从中输入下一个记录 14 到内存工作区中，然后从内存工作区中的比 29 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到归并段文件中，如下图所示：

upload successful

3.初始文件还不为空，所以继续输入 61 到内存工作区中，从内存工作区中的所有关键字比 38 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到归并段文件中，如下图所示：

upload successful

4.如此重复性进行，直至选不出 MINIMAX 值为止，如下图所示：

upload successful

5.当选不出 MINIMAX 值时，表示一个归并段已经生成，则开始下一个归并段的创建，创建过程同第一个归并段一样，这里不再赘述。

败者树的实现：

在不断选择新的 MINIMAX 记录时，为了防止新加入的关键字值小的的影响，每个叶子结点附加一个序号位，当进行关键字的比较时，先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。

在初期创建败者树时也可以通过不断调整败者树的方式，其中所有记录的序号均设为 0 ，然后从初始文件中逐个输入记录到内存工作区中，自下而上调整败者树。过程如下：

1.首先创建一个空的败者树，如下图所示：

upload successful

2.从初始文件中读入关键字为 51 的记录，自下往上调整败者树，如下图所示：

upload successful

提示：序号 1 默认为比 0 小，为败者。

3.从初始文件中读入关键字为 49 的记录，调整败者树如下图所示：

upload successful

4.从初始文件依次读入关键字为 39、46、38、29 的记录，调整败者树如下图所示：

upload successful

5.由败者树得知，其最终胜者为 29，设为 MINIMAX 值，将其输出到初始归并文件中，同时再读入下一个记录 14，调整败者树，如下图所示：

通过不断地向败者树中读入记录，会产生多个 MINIMAX，直到最终所有叶子结点中的序号都为 2，此时产生的新的 MINIMAX 值的序号 2（循环判定胜者的段号决定是否输出新段），表明此归并段生成完成，而此新的 MINIMAX 值就是下一个归并段中的第一个记录。

注意：当读入新的记录时，如果其值比 MINIMAX 大，其序号则仍为 1；反之则为 2 ，比较时序号大的。

总结：

通过置换选择排序算法得到的初始归并段，其长度并不会受内存容量的限制，且通过证明得知使用该方法所获得的归并段的平均长度为内存工作区大小的两倍。

若不计输入输出的时间，通过置换选择排序生成初始归并段的所需时间为O(nlogw)（其中 n 为记录数，w 为内存工作区的大小）。

以下代码有问题，有时候会多生成几个数，但是可以拿来做个参考。

#include <stdio.h>
#define MAXKEY 10000
#define RUNEND_SYMBOL 10000 // 归并段结束标志
#define w 6     // 内存工作区可容纳的记录个数
#define N 24    // 设文件中含有的记录的数量
typedef int KeyType; // 定义关键字类型为整型

// 记录类型
typedef struct{
    KeyType key; // 关键字项
}RedType;

typedef int LoserTree[w];// 败者树是完全二叉树且不含叶子，可采用顺序存储结构
typedef struct
{
    RedType rec; /* 记录 */
    KeyType key; /* 从记录中抽取的关键字 */
    int rnum; /* 所属归并段的段号 */
}RedNode, WorkArea[w];

// 从wa[q]起到败者树的根比较选择MINIMAX记录，并由q指示它所在的归并段
void Select_MiniMax(LoserTree ls,WorkArea wa,int q){
    int p, s, t;
// ls[t]为q的双亲节点，p作为中介

    for(t = (w+q)/2,p = ls[t]; t > 0;t = t/2,p = ls[t]){
        // 段号小者 或者 段号相等且关键字更小的为胜者
        if(wa[p].rnum < wa[q].rnum || (wa[p].rnum == wa[q].rnum && wa[p].key < wa[q].key)){
            s=q;
            q=ls[t]; //q指示新的胜利者
            ls[t]=s;
        }
    }
    ls[0] = q; // 最后的冠军
}
//输入w个记录到内存工作区wa,建得败者树ls,选出关键字最小的记录，并由s指示其在wa中的位置。
void Construct_Loser(LoserTree ls, WorkArea wa, FILE *fi){
    int i;
    for(i = 0; i < w; ++i){
        wa[i].rnum = wa[i].key = ls[i] = 0;
    }
    for(i = w - 1; i >= 0; --i){
        fread(&wa[i].rec, sizeof(RedType), 1, fi);// 输入一个记录
        wa[i].key = wa[i].rec.key; // 提取关键字
        wa[i].rnum = 1; // 其段号为＂1＂
        Select_MiniMax(ls,wa,i); // 调整败者树
    }
}

// 求得一个初始归并段，fi为输入文件指针，fo为输出文件指针。
void get_run(LoserTree ls,WorkArea wa,int rc,int *rmax,FILE *fi,FILE *fo){
    int q;
    KeyType minimax;
    // 选得的MINIMAX记录属当前段时
    while(wa[ls[0]].rnum == rc){
        q = ls[0];// q指示MINIMAX记录在wa中的位置
        minimax = wa[q].key;
        // 将刚选得的MINIMAX记录写入输出文件
        fwrite(&wa[q].rec, sizeof(RedType), 1, fo);
        // 如果输入文件结束，则虚设一条记录（属＂rmax+1＂段）
        if(feof(fi)){
            wa[q].rnum = *rmax+1;
            wa[q].key = MAXKEY;
        }else{ // 输入文件非空时
            // 从输入文件读入下一记录
            fread(&wa[q].rec,sizeof(RedType),1,fi);
            wa[q].key = wa[q].rec.key;// 提取关键字
            if(wa[q].key < minimax){
                // 新读入的记录比上一轮的最小关键字还小，则它属下一段
                *rmax = rc+1;
                wa[q].rnum = *rmax;
            }else{
                // 新读入的记录大则属当前段
                wa[q].rnum = rc;
            }
        }
        // 选择新的MINIMAX记录
        Select_MiniMax(ls, wa, q);
    }
}

//在败者树ls和内存工作区wa上用置换－选择排序求初始归并段
void Replace_Selection(LoserTree ls, WorkArea wa, FILE *fi, FILE *fo){
    int rc, rmax;
    RedType j;
    j.key = RUNEND_SYMBOL;
    // 初建败者树
    Construct_Loser(ls, wa, fi);
    rc = rmax =1;//rc指示当前生成的初始归并段的段号，rmax指示wa中关键字所属初始归并段的最大段号

    while(rc <= rmax){// ＂rc=rmax+1＂标志输入文件的置换－选择排序已完成
        // 求得一个初始归并段
        get_run(ls, wa, rc, &rmax, fi, fo);
        fwrite(&j,sizeof(RedType),1,fo);//将段结束标志写入输出文件
        rc = wa[ls[0]].rnum;//设置下一段的段号
    }
}

void print(RedType t){
    printf("%d ",t.key);
}

int main(){
    RedType a[N]={51,49,39,46,38,29,14,61,15,30,1,48,52,3,63,27,4,13,89,24,46,58,33,76};
    RedType b;
    FILE *fi,*fo; //输入输出文件
    LoserTree ls; // 败者树
    WorkArea wa; // 内存工作区
    int i, k;
    fo = fopen("ori","wb"); //准备对 ori 文本文件进行写操作
    //将<u>[数组](http://data.biancheng.net/view/181.html)</u> a 写入大文件ori
fwrite(a, sizeof(RedType), N, fo);
    fclose(fo); //关闭指针 fo 表示的文件
    fi = fopen("ori","rb");//准备对 ori 文本文件进行读操作
    printf("文件中的待排序记录为:\n");
    for(i = 1; i <= N; i++){
        // 依次将文件ori的数据读入并赋值给b
        fread(&b,sizeof(RedType),1,fi);
        print(b);
    }
    printf("\n");
    rewind(fi);// 使fi的指针重新返回大文件ori的起始位置，以便重新读入内存，产生有序的子文件。
    fo = fopen("out","wb");
    // 用置换－选择排序求初始归并段
    Replace_Selection(ls, wa, fi, fo);
    fclose(fo);
    fclose(fi);
    fi = fopen("out","rb");
    printf("初始归并段各为:\n");
    do{
        k = fread(&b, sizeof(RedType), 1, fi); //读 fi 指针指向的文件，并将读的记录赋值给 b，整个操作成功与否的结果赋值给 k
        if(k == 1){
            if(b.key ==MAXKEY){//当其值等于最大值时，表明当前初始归并段已经完成
                printf("\n\n");
                continue;
            }
            print(b);
        }
    }while(k == 1);
    return 0;
}

2020-05-15

外部排序

http://data.biancheng.net/view/77.html

多路归并排序：

二路归并排序

五路归并排序

对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。

对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多（每次归并都要加载硬盘上的待归并文件到内存）。

最后一轮归并的时候内存不够怎么办？

在实际归并的过程中，由于内存容量的限制不能满足同时将 2 个归并段全部完整的读入内存进行归并，只能不断地取 2 个归并段中的每一小部分进行归并，通过不断地读数据和向外存写数据，直至 2 个归并段完成归并变为 1 个大的有序文件。

有关段的预处理如何提升算法效率？

对比2-路还有5-路归并排序可以看出，对于 k-路平衡归并中，增加 k 可以减少归并的次数，从而减少外存读写的次数，最终达到提高算法效率的目的。除此之外，一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为：$s=⌊log_k⁡m ⌋$（其中 s 表示归并次数）

-方法也就以下两个：
（1）增加 k-路平衡归并中的 k 值；（多路平衡归并算法）
（2）减少初始段的数量m / 增加每个归并段的容量（段太大的话内存可能不够）；（置换-选择排序算法）

2020-05-05

成员初始化的顺序

可以看出成员被初始化的顺序和成员初始化表里面的顺序是没有关系的，只和成员的声明顺序有关。

#include <iostream>
using namespace std;
int seti() {cout << "seti" << endl;return 1;}
int setj() {cout << "setj" << endl;return 1;}
class a
{
public:
    a() {cout << "a()~~~~~" << endl;}
};
class b
{
public:
    b():j(setj()),i(seti()) {cout << "b()~~~~~" << endl;}
    int i;
    a ca;
    int j;
};
int main()
{
    b ob;
    return 0;
}

构造函数执行顺序：public里面 int i 先声明，就先构造 i，然后类a ca 声明，再构造 ca，然后声明 j，就构造 j，最后执行 b() 构造函数里面的东西。

upload successful

另外举个例子：

#include <iostream>
using namespace std;
class A
{
private:
	int n1;
	int n2;
public:
	A():n2(0),n1(n2+2){}
	void Print(){
		cout << "n1:" << n1 << ", n2: " << n2 <<endl;  
	}
};
int main()
{ 
	A a;
	a.Print();
	return 1;
}

因为private里面先定义的n1再定义的n2，但是n1需要n2，n2没有初始化，所以n2是乱码，n1是0。

upload successful

2019-10-14

拉格朗日乘子法和（对偶性与KKT条件）

https://blog.csdn.net/weixin_37688445/article/details/79275526
https://www.matongxue.com/madocs/939.html
https://www.matongxue.com/madocs/987/

拉格朗日乘子法（约束条件为等式）

$\begin{cases}
min f(x) \\
\
h_i(x)=0，i=0，1，…，n
\end{cases}$

在两个图线外相切的时候达到最小值，法向量方向相反

$\begin{cases}
\nabla f(x)=-\nabla \lambda\star h_i(x) => \nabla f(x)+\nabla \lambda\star h_i(x)=0\\
\
h_i(x)=0，i=0，1，…，n
\end{cases}$

最终表达式：

$\begin{cases}
L(x,a)=min[f(x)+\sum_{i=1}^{n}a_ih_i(x)]
\\
h_i(x)=0，i=0，1，…，n
\end{cases}$

求解：$\nabla_xL(x,a)=0$还有$\nabla_aL(x,a)=0$可得最优解的x和a

upload successful

拉格朗日的KKT条件

初试条件：

$\begin{cases}
min f(x) \\
\
g(x) <= 0
\end{cases}$

推导出来的最终公式：

$\begin{cases}
式1： L(x,a)=min[f(x)+\lambda*g(x)]\\
式2： g(x) = 0 \\
式3：\lambda>0
\end{cases}$

*情况1：如果可行解直接落在约束条件范围内，即落在g(x)<0的范围内，则直接删掉约束条件即可。（但是最优点依旧满足前提：公式1即使两条线在$r_f$≈0的时候不相交）

*情况2：如果可行解落在约束条件外，则最优解在边界上去的，即在g(x)=0的曲线上取得。（此时转换为前面讲的等式条件下求最优解的问题，直接套上面的公式）

upload successful

以上两种状况要么落在约束区域内，则$\lambda_解$=0，因为直接去掉约束条件即可，要么落在约束条件边界上，则$g(x)_解=0$, 综合起来就是$\lambda*g(x)=0$

还有一个问题就是$\lambda$的取值问题，当$\lambda$不等于0的时候，即最优解在$g(x)=0$上取得时，$f(x,y)$梯度方向必须要和$g(x)=0$的梯度方向相反，即$-\nabla_xf(x)=\lambda\nabla_xg(x)$，所以$\lambda$一定大于0，要不然就恒非零了。

upload successful

拉格朗日对偶性：（$\lambda$改为a表示）

1.原始最优化问题：

$\begin{cases}
式1： \min_{x \in R^n} f(x)\\
式2： c_i(x)<=0 ， i=1，2，…，k \\
式3：h_j(x)=0 ，j=1，2，…，l
\end{cases}$

$L(x,a,\beta)=f(x)+\sum_{i=1}^{k}a_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)$

2.极小极大问题：

$令\theta_P(x)=\max_{a,\beta:a_i>=0}L(x,a,\beta)$

如果$i$和$j$当中有一个不满足式2/式3条件，那么必然存在某个$i$满足$c_i(x)>0$，可令$a_i->+\infty$，或者存在某个$j$满足$h_j(x) \ne 0$，则可令$\beta_jh_j(x)\rightarrow +\infty$，而将其余各个$a_i$，$\beta_j$均取为$0$，使得$\theta_P(x)=+\infty$

所以max化的拉格朗日函数 $\theta_P(x)=\begin{cases}
f(x) ， x满足原始问题约束\\
+\infty ，其他
\end{cases}$

接着考虑max条件下的min最优值：

$p^*=min \theta_P(x)=\min_{x} \max_{a,\beta:a_i>=0} L(x,a,\beta)$

3.极大极小问题：

$\max_{a,\beta}\theta_D(a,\beta)=\max_{a,\beta}\min_{x}L(x,a,\beta)，a_i>=0$

最优解：$d^*=\max_{a,\beta:a_i>=0}\theta_D(a,\beta)$

4.极大极小问题与极小极大问题的解什么时候相等？

maxmin和minmax的最优解有以下大小关系：

$d^*=\max_{a,\beta:a_i>=0}\min_{x}L(x,a,\beta)<=\min_{x} \max_{a,\beta:a_i>=0} L(x,a,\beta)=p^*$

如果满足$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，和KKT条件，则：

$d^*=L(x^*,a^*,\beta^*)=p^*$

KKT条件是$d^\star$ = $p^\star$的充要条件：

$\nabla_xL(x^*,a^*,\beta^*)=0$ $a_i^*c_i(x^*)=0，i=1,2,...,k$ $c_i(x^*)<=0 ，i=1,2,...,k$ $a_i^*>=0 ， i=1,2,...,k$ $h_j(x^*)=0，j=1，...，l$

2019-10-12

VC维

VC 维是衡量函数类的复杂度的一种方式，通过评估函数类中函数的弯曲程度实现。WIKI上的解释是：空间中的点在经过排列之后，能够被模型f打散(shatter)的最大数量。

通过$y=a_0+a_1^Tx$将平面分割为两部分，如果满足平面中任意N个点（无论如何取值）总能被一条直线分开，而N+1个点却不行，则称该函数情况下的VC维为N。

upload successful

举个无穷的VC维的例子：

$f(x,a)=I(sina*x)$

upload successful

从这两个例子，可以看出VC维刻画了函数的弯曲程度，越弯曲其VC维越大。

2019-10-12

常见的几种决策树

https://www.cnblogs.com/pinard/p/6053344.html
https://blog.csdn.net/a857553315/article/details/95620881

特征选择：

如果瞎猜中的概率与特征选择出来的概率相差无几，那么就可以放弃该特征了。特征选择的标准是信息增益或信息增益比。

ID3算法与信息增益：（木有剪枝，只能处理离散数据）

得知特征X的信息而使输出的分类Y的不确定性减少的程度。

条件熵：$H(Y|X)=\sum_{n}^{i=1}p_iH(Y|X=x_i)$

信息增益：$g(D,A)=H(D)-H(D|A)$，D是数据集，A是特征。

计算过程：

（1）计算数据集D的经验熵：

$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$ ，k为第一级特征{纹理，色泽，触感}

（2）计算条件熵：

$H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{D}H(D_i)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{D_i}log_2\frac{|D_{ik}|}{|D_i|}$

i为第一级特征{ 纹理 / 色泽 / 触感 }，ik为纹理中的第二级特征{ 清晰，模糊，稍糊 }

（3）$g(D,A)=H(D)-H(D|A)$，越大越好。

ID3算法就是完全依赖信息增益，但是信息增益明显对多个取值的特征有偏好，所以出现了使用增益率的C4.5算法。

C4.5算法与增益率（后剪枝，可以处理连续数据—>多叉树，特征要计算排序）

$Gainratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

固有值：$IV(a)=-\sum_{v=1}^{V}\frac{|D_v|}{|D|}log_2\frac{|D_v|}{|D|}$ ，Dv是第一级特征a下的第二级特征，固有值随V的个数增加而增加。

CART决策树（减少log的使用降低计算量，还可以用于回归，二叉树）

使用Gini系数替代ID3里的熵，Gini系数越小越均衡（被错分的概率低），说明该样本只属于同一类的概率（纯度）越高。

$Gini(D)=\sum_{k=1}^{y}\sum_{k’ \ne k}p_k*p_k’=1-\sum_{k=1}^{y}p_k^2$

pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)

基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率

预剪枝与后剪枝：（对抗过拟合与欠拟合）

预剪枝：（边自上往下生成枝杈边剪枝）

预剪枝使得很多分支没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间。但是，有些分支虽当前不能提升泛化性。甚至可能导致泛化性暂时降低，但在其基础上进行后续划分却有可能导致显著提高，因此预剪枝的这种贪心本质，给决策树带来了欠拟合的风险。

后剪枝：（先生成枝桠，最后从下往上剪枝）

后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往优于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。

连续值处理：（密度/甜度）

连续（非离散）特征可以将特征值从小到大排列然后取

$T_a={\frac{a_i+a_{i+1}}{2},0<i<n}$ $Gain(D,a)=\max_{t \in T_a} Gain(D,a,t)=max Ent(D)-\sum_{\lambda \in {-,+}}\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda)$

按照 $T_a$ 进行划分 { - ，+ }，从而得到该情况下的信息增益。

缺失值处理：（检测数据缺失）

（1）如何在属性值缺失的情况下进行划分属性的选择？（创建决策树的时候怎么计算缺失值存在下的信息增益，选择正确的属性）
（2）给定划分属性，若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？（在分类过程中有缺失值的话怎么进行划分）

无缺失样本所占比例：$p=\frac{ \sum_{x \in \tilde{D}}w_x}{ \sum_{x \in D} w_x}$
无缺失样本中第k类所占比例：$\tilde{p}_k=\frac{ \sum_{x \in \tilde{D}_k}w_x}{ \sum_{x \in \tilde{D}} w_x}$
无缺失样本中在特征a上取值为$a_v$的样本所占比例：$\tilde{r}_v=\frac{ \sum_{x \in \tilde{D}_k}w_x}{ \sum_{x \in \tilde{D}} w_x}$

最后得到了推广了的公式：

$Gain(D,a)=p*Gain(D,\tilde a)=p*(Ent(\tilde D)-\sum_{v=1}^{V}\tilde{r}_vEnt(\tilde D^v))$

上式 = 总样本中非缺失的比例 *（非缺失中各类的熵-各类概率*各类特征值的熵）

$Ent(\tilde D)=-\sum_{k=1}^{y}\tilde{p}_klog_2{\tilde{p}_k}$

多变量决策树：

一般的决策树分类边界由若干个与坐标轴平行的分段组成：

判断过程：密度 -> 含糖率 -> 密度 -> 含糖率…

upload successful

多变量决策树有d个属性对应d维空间的一个数据点，对样本分类表示在坐标空间中找到不同样本之间的分类边界。

upload successful

“多变量决策树”能实现斜的划分边界，使决策树模型简化。在多变量决策树的学习过程中，不是为非叶结点寻找最优划分属性，而是试图建立合适的线性分类器：

upload successful

可以通过最小二乘或者嵌入神经网络进一步优化。

增量学习：根据新样本可对学得的模型进行调整适应当前形势，而不需要重新训练。如ID4，ID5R还有ITI

熵与基尼系数哪个好

和熵模型的度量方式比，基尼系数对应的误差有多大呢？对于二类分类，基尼系数和熵之半的曲线如下：

1 2	Gini = 2 * p * (1-p) H = (-p * np.log2(p) - (1 - p) * np.log2(1 - p))/2.0

upload successful


import numpy as np
from matplotlib import pyplot as plt 
import matplotlib as mpl
mpl.rcParams['font.sans-serif'] = ['simHei']
mpl.rcParams['axes.unicode_minus'] = False
 
p = np.linspace(0.0001, 0.9999 ,50)
Gini = 2 * p * (1-p)
H = (-p * np.log2(p) - (1 - p) * np.log2(1 - p))/2.0
x1 = np.linspace(0,0.5,50)
y1 = x1
x2 = np.linspace(0.5,1,50)
y2 = 1- x2
 
plt.figure(figsize=(10,5))
plt.plot(p, Gini, 'r-', label='基尼指数')
plt.plot(p, H, 'b-', label='半熵')
plt.plot(x1, y1, 'g-', label='分类误差率')
plt.plot(x2, y2, 'g-')
plt.legend()
plt.xlim(-0.01, 1.01)
plt.ylim(0, 0.51)
plt.show()

从上图可以看出，基尼系数和熵之半的曲线非常接近，因此，基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。