精华内容
下载资源
问答
  • 机器学习(四):剪枝技术(基础篇) 相关的决策树文章: 机器学习(四)ID3决策树 机器学习(四)C4.5决策树 机器学习(四)CART分类树 机器学习(四)CART回归树 机器学习(四)决策树绘图 到现在为止,已经完成...

    机器学习(四):剪枝技术(基础篇)

    相关的决策树文章:

    到现在为止,已经完成回归树的构建,但是需要某种措施来检查构建过程是否恰当。这个技术就是剪枝技术。剪枝技术是决策树算法中十分重要的一部分,我们需要掌握剪枝的原理和代码。

    树剪枝

    一棵树如果结点过多,表明该模型可能对数据进行了“过拟合”。
    通过降低树的复杂度来避免过拟合的过程称为剪枝(pruning)。上小节我们也已经提到,设置tolS和tolN就是一种预剪枝操作。另一种形式的剪枝需要使用测试集和训练集,称作后剪枝(postpruning)。本节将分析后剪枝的有效性,但首先来看一下预剪枝的不足之处。

    1.预剪枝

    预剪枝具有一定的局限性,现在用一个新的数据集。
    数据集下载地址:数据集下载
    我们现在画图看一看数据分布:

    import matplotlib.pyplot as plt
    import numpy as np
    
    
    def loadDataSet(fileName):
        """
        函数说明:加载数据
        Parameters:
            fileName - 文件名
        Returns:
            dataMat - 数据矩阵
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-09
        """
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float, curLine))  # 转化为float类型
            dataMat.append(fltLine)
        return dataMat
    
    
    def plotDataSet(filename):
        """
        函数说明:绘制数据集
        Parameters:
            filename - 文件名
        Returns:
            无
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-11-12
        """
        dataMat = loadDataSet(filename)  # 加载数据集
        n = len(dataMat)  # 数据个数
        xcord = [];
        ycord = []  # 样本点
        for i in range(n):
            xcord.append(dataMat[i][0]);
            ycord.append(dataMat[i][1])  # 样本点
        fig = plt.figure()
        ax = fig.add_subplot(111)  # 添加subplot
        ax.scatter(xcord, ycord, s=20, c='blue', alpha=.5)  # 绘制样本点
        plt.title('DataSet')  # 绘制title
        plt.xlabel('X')
        plt.show()
    
    
    if __name__ == '__main__':
        filename = 'ex01.txt'
        plotDataSet(filename)
    

    运行结果如下:
    在这里插入图片描述
    可以看到,对于这个数据集与我们使用的第一个数据集很相似,但是区别在于y的数量级差100倍,数据分布相似,因此构建出的树应该也是只有两个叶结点。但是我们使用默认tolS和tolN参数创建树,你会发现运行结果如下所示:
    在这里插入图片描述
    可以看到,构建出的树有很多叶结点。产生这个现象的原因在于,停止条件tolS对误差的数量级十分敏感。如果在选项中花费时间并对上述误差容忍度取平均值,或许也能得到仅有两个叶结点组成的树:
    在这里插入图片描述
    可以看到,将参数tolS修改为10000后,构建的树就是只有两个叶结点。然而,显然这个值,需要我们经过不断测试得来,显然通过不断修改停止条件来得到合理结果并不是很好的办法。事实上,我们常常甚至不确定到底需要寻找什么样的结果。因为对于一个很多维度的数据集,你也不知道构建的树需要多少个叶结点。

    可见,预剪枝有很大的局限性。接下来,我们讨论后剪枝,即利用测试集来对树进行剪枝。由于不需要用户指定参数,后剪枝是一个更理想化的剪枝方法。

    2.后剪枝

    使用后剪枝方法需要将数据集分成测试集和训练集。首先指定参数,使得构建出的树足够大、足够复杂,便于剪枝。接下来从上而下找到叶结点,用测试集来判断这些叶结点合并是否能降低测试集误差。如果是的话就合并。

    为了演示后剪枝,我们使用ex02.txt文件作为训练集,而使用的新数据集ex02test.txt文件作为测试集。
    测试数据集下载:数据集下载
    在我们使用ex02.txt训练回归树,然后利用ex2test.txt对回归树进行剪枝。我们需要创建三个函数isTree()、getMean()、prune()。

    • isTree()用于测试输入变量是否是一棵树,返回布尔类型的结果。换句话说,该函数用于判断当前处理的结点是否是叶结点。
    • getMean()是一个递归函数,它从上往下遍历树直到叶结点为止。如果找到两个叶结点则计算它们的平均值。该函数对树进行塌陷处理(即返回树平均值)。
    • prune()则为后剪枝函数。

    编写代码如下:

    import matplotlib.pyplot as plt
    import numpy as np
    
    
    def loadDataSet(fileName):
        """
        函数说明:加载数据
        Parameters:
            fileName - 文件名
        Returns:
            dataMat - 数据矩阵
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-09
        """
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float, curLine))  # 转化为float类型
            dataMat.append(fltLine)
        return dataMat
    
    
    def plotDataSet(filename):
        """
        函数说明:绘制数据集
        Parameters:
            filename - 文件名
        Returns:
            无
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-11-12
        """
        dataMat = loadDataSet(filename)  # 加载数据集
        n = len(dataMat)  # 数据个数
        xcord = [];
        ycord = []  # 样本点
        for i in range(n):
            xcord.append(dataMat[i][0]);
            ycord.append(dataMat[i][1])  # 样本点
        fig = plt.figure()
        ax = fig.add_subplot(111)  # 添加subplot
        ax.scatter(xcord, ycord, s=20, c='blue', alpha=.5)  # 绘制样本点
        plt.title('DataSet')  # 绘制title
        plt.xlabel('X')
        plt.show()
    
    def binSplitDataSet(dataSet, feature, value):
        """
        函数说明:根据特征切分数据集合
        Parameters:
            dataSet - 数据集合
            feature - 带切分的特征
            value - 该特征的值
        Returns:
            mat0 - 切分的数据集合0
            mat1 - 切分的数据集合1
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-12
        """
        mat0 = dataSet[np.nonzero(dataSet[:,feature] > value)[0],:]
        mat1 = dataSet[np.nonzero(dataSet[:,feature] <= value)[0],:]
        return mat0, mat1
    
    def regLeaf(dataSet):
        """
        函数说明:生成叶结点
        Parameters:
            dataSet - 数据集合
        Returns:
            目标变量的均值
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-12
        """
        return np.mean(dataSet[:,-1])
    
    def regErr(dataSet):
        """
        函数说明:误差估计函数
        Parameters:
            dataSet - 数据集合
        Returns:
            目标变量的总方差
        Website:
        https://www.cuijiahua.com/
        Modify:
            2017-12-12
        """
        return np.var(dataSet[:,-1]) * np.shape(dataSet)[0]
    
    def chooseBestSplit(dataSet, leafType = regLeaf, errType = regErr, ops = (1,4)):
        """
        函数说明:找到数据的最佳二元切分方式函数
        Parameters:
            dataSet - 数据集合
            leafType - 生成叶结点
            regErr - 误差估计函数
            ops - 用户定义的参数构成的元组
        Returns:
            bestIndex - 最佳切分特征
            bestValue - 最佳特征值
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-12
        """
        import types
        #tolS允许的误差下降值,tolN切分的最少样本数
        tolS = ops[0]; tolN = ops[1]
        #如果当前所有值相等,则退出。(根据set的特性)
        if len(set(dataSet[:,-1].T.tolist()[0])) == 1:
            return None, leafType(dataSet)
        #统计数据集合的行m和列n
        m, n = np.shape(dataSet)
        #默认最后一个特征为最佳切分特征,计算其误差估计
        S = errType(dataSet)
        #分别为最佳误差,最佳特征切分的索引值,最佳特征值
        bestS = float('inf'); bestIndex = 0; bestValue = 0
        #遍历所有特征列
        for featIndex in range(n - 1):
            #遍历所有特征值
            for splitVal in set(dataSet[:,featIndex].T.A.tolist()[0]):
                #根据特征和特征值切分数据集
                mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
                #如果数据少于tolN,则退出
                if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN): continue
                #计算误差估计
                newS = errType(mat0) + errType(mat1)
                #如果误差估计更小,则更新特征索引值和特征值
                if newS < bestS:
                    bestIndex = featIndex
                    bestValue = splitVal
                    bestS = newS
        #如果误差减少不大则退出
        if (S - bestS) < tolS:
            return None, leafType(dataSet)
        #根据最佳的切分特征和特征值切分数据集合
        mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
        #如果切分出的数据集很小则退出
        if (np.shape(mat0)[0] < tolN) or (np.shape(mat1)[0] < tolN):
            return None, leafType(dataSet)
        #返回最佳切分特征和特征值
        return bestIndex, bestValue
    
    def createTree(dataSet, leafType = regLeaf, errType = regErr, ops = (1, 4)):
        """
        函数说明:树构建函数
        Parameters:
            dataSet - 数据集合
            leafType - 建立叶结点的函数
            errType - 误差计算函数
            ops - 包含树构建所有其他参数的元组
        Returns:
            retTree - 构建的回归树
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-12
        """
        #选择最佳切分特征和特征值
        feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
        #r如果没有特征,则返回特征值
        if feat == None: return val
        #回归树
        retTree = {}
        retTree['spInd'] = feat
        retTree['spVal'] = val
        #分成左数据集和右数据集
        lSet, rSet = binSplitDataSet(dataSet, feat, val)
        #创建左子树和右子树
        retTree['left'] = createTree(lSet, leafType, errType, ops)
        retTree['right'] = createTree(rSet, leafType, errType, ops)
        return retTree
    
    def isTree(obj):
        """
        函数说明:判断测试输入变量是否是一棵树
        :param obj: 测试对象
        :return:
        """
        import types
        return (type(obj).__name__ == 'dict')
    
    def getMean(tree):
        """
        函数说明:对树进行塌陷处理(即返回树平均值)
        Parameters:
            tree - 树
        Returns:
            树的平均值
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-14
        """
        if isTree(tree['right']): tree['right'] = getMean(tree['right'])
        if isTree(tree['left']): tree['left'] = getMean(tree['left'])
        return (tree['left'] + tree['right']) / 2.0
    
    def prune(tree, testData):
        """
        函数说明:后剪枝
        Parameters:
            tree - 树
            test - 测试集
        Returns:
            树的平均值
        Website:
            https://www.cuijiahua.com/
        Modify:
            2017-12-14
        """
        #如果测试集为空,则对树进行塌陷处理
        if np.shape(testData)[0] == 0: return getMean(tree)
        #如果有左子树或者右子树,则切分数据集
        if (isTree(tree['right']) or isTree(tree['left'])):
            lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
        #处理左子树(剪枝)
        if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet)
        #处理右子树(剪枝)
        if isTree(tree['right']): tree['right'] =  prune(tree['right'], rSet)
        #如果当前结点的左右结点为叶结点
        if not isTree(tree['left']) and not isTree(tree['right']):
            lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
            #计算没有合并的误差
            errorNoMerge = np.sum(np.power(lSet[:,-1] - tree['left'],2)) + np.sum(np.power(rSet[:,-1] - tree['right'],2))
            #计算合并的均值
            treeMean = (tree['left'] + tree['right']) / 2.0
            #计算合并的误差
            errorMerge = np.sum(np.power(testData[:,-1] - treeMean, 2))
            #如果合并的误差小于没有合并的误差,则合并
            if errorMerge < errorNoMerge:
                return treeMean
            else: return tree
        else: return tree
    
    if __name__ == '__main__':
        train_filename = 'ex01.txt'
        train_Data = loadDataSet(train_filename)
        train_Mat = np.mat(train_Data)
        tree = createTree(train_Mat)
        print(tree)
        test_filename = 'ex02.txt'
        test_Data = loadDataSet(test_filename)
        test_Mat = np.mat(test_Data)
        print(prune(tree, test_Mat))
    

    结果如下:
    在这里插入图片描述
    看样子好像没有太大区别。不过经过剪枝后的树相对而言少了一些。

    总结:

    • CART算法可以用于构建二元树并处理离散型或连续型数据的切分。若使用不同的误差准则,就可以通过CART算法构建模型树和回归树。
    • 一颗过拟合的树常常十分复杂,剪枝技术的出现就是为了解决这个问题。两种剪枝方法分别是预剪枝和后剪枝,预剪枝更有效但需要用户定义一些参数。
    展开全文
  • fp-growth 最详细教程

    2020-01-13 10:52:01
    self.nodeLink = None #链接相似元素 self.parent = parentNode #当前父节点 self.children = {} #用于存放子节点 def inc(self,numOccur): self.count +=numOccur def disp(self,ind = 1,i=1): print(' ...

    参考代码:https://blog.csdn.net/baixiangxue/article/details/80335469 

    class treeNode:
        def __init__(self,nameValue,numOccur,parentNode):
            self.name = nameValue     #名字变量
            self.count = numOccur     #计数变量(频率)
            self.nodeLink = None        #链接相似元素项
            self.parent = parentNode    #当前父节点
            self.children = {}          #用于存放子节点
    
        def inc(self,numOccur):
            self.count +=numOccur
    
        def disp(self,ind = 1,i=1):
            print(' '*ind,self.name,' ',self.count)
            for child in self.children.values():
                child.disp(ind+1)   #子节点向右缩减
    '''
    #创建一个单节点
    rootNode = treeNode('这是父节点',9,None)
    print(rootNode.children.keys())
    #创建一个子节点
    rootNode.children['这是子节点'] = treeNode('这是子节点',13,None)
    print(rootNode.children.keys())
    #显示节点
    rootNode.disp()
    #再增加一个子节点
    rootNode.children['这是另一个子节点'] = treeNode('这是另一个子节点',3,None)
    #显示节点
    
    rootNode.disp()
    '''
    def loadSimpDat():
        simpDat = [['r','z'],
                   ['z','y','x','t','s'],
                   ['z'],
                   ['r','x','s'],
                   ['y','r','x','z','t'],
                   ['y','z','x','s','t']]
        return simpDat
    simpDat=loadSimpDat()
    
    def createInitSet(dataSet):
        retDict = {}
        for trans in dataSet:
            fset = frozenset(trans)
            retDict.setdefault(fset,0)
            retDict[fset] += 1
        return retDict
    
    retDict = createInitSet(simpDat)
    
    def updateHeader(nodeToTest,targetNode):
        #print('nodeToTest,targetNode'),nodeToTest.disp(),targetNode.disp()
        #print(nodeToTest.nodeLink)
        while (nodeToTest.nodeLink != None):
            nodeToTest = nodeToTest.nodeLink
            #print('nodeToTest'),nodeToTest.disp()
        nodeToTest.nodeLink = targetNode
        #nodeToTest.nodeLink.disp()
    #headerTable['r'][1].nodeLink.nodeLink.disp()
    def updateTree(items,myTree,headerTable,count):
        #print('items,headerTable,count',items,'||',headerTable,'||',count)
        #print('myTree'),myTree.disp()
        if items[0] in myTree.children:
            #print('1-------------')
            #print(myTree.children.keys())
            myTree.children[items[0]].inc(count)
            #print('myTree'),myTree.disp()
        else:
            #print('2-------------')
            #print(myTree.children.keys())
            myTree.children[items[0]] = treeNode(items[0],count,myTree) #***
            #print('parent=====myTree'),myTree.disp()
            t=myTree.children[items[0]]
            #print('children',myTree.children)
            #print(t.name,t.count)
            #print(headerTable[items[0]])
            if headerTable[items[0]][1] == None:
                #print('3-------------')
                #print(myTree.children.keys())
                
                headerTable[items[0]][1] = myTree.children[items[0]]
                #print('3-1-----------'),headerTable[items[0]][1].disp()
                #print('3-1-1'),myTree.children[items[0]].disp()
                #print('3-1-2'),myTree.disp()
                t=myTree.children[items[0]]
            else:
                #print('4-1-1'),myTree.disp()
                #print(headerTable,headerTable)
                #print('4-------------')
                #print(myTree.children.keys())
                #print('4-1-----------'),headerTable[items[0]][1].disp()
                updateHeader(headerTable[items[0]][1],myTree.children[items[0]])
                #print('5-------------')
                #headerTable[items[0]][1].disp()
        if len(items) > 1:
            #实例化children[items[0]]
            #print('---e--',myTree.children[items[0]].children)
            updateTree(items[1:],myTree.children[items[0]],headerTable,count)#### 可以转化主枝干
            
    def createTree(dataSet,minSup=1):
        headerTable={}
        for trans in dataSet:
            for item in trans:
                headerTable[item] = headerTable.get(item,0) + 1*dataSet[trans]
        #根据最小支持度过滤
        #print('headerTable',headerTable)
        lessThanMinSup = list(filter(lambda k:headerTable[k] < minSup,headerTable.keys()))
        for k in lessThanMinSup:
            del(headerTable[k])
        freqItemSet = set(headerTable.keys())
        #如果所有数据都不满足最小支持度,返回None
        if len(freqItemSet) ==0:
            return None,None
        for k in headerTable:
            headerTable[k] = [headerTable[k],None]
        myTree = treeNode('$',1,None)
        #print('fffff',myTree.children.keys())
        # 第二次遍历数据集
        for tranSet,count in dataSet.items():
            localD = {}
            for item in tranSet:
                if item in freqItemSet:
                    localD[item] = headerTable[item][0]
            if len(localD) > 0:
                #根据全局频繁项对每个事务中的数据进行排序,等价
                orderedItems = [v[0] for v in sorted(localD.items(),key = lambda p:(p[1],p[0]),reverse=True)]
                #print('orderedItems',orderedItems)
                #print(myTree.children.keys())
                #myTree.disp()
                updateTree(orderedItems,myTree,headerTable,count)
                #print('0000***',myTree.children.keys())
                
        return myTree,headerTable
    
    myTree,headerTable = createTree(retDict,minSup=3)
    
    #myTree.disp()
    
    
    def ascendTree(leafNode, prefixPath): #迭代上溯整棵树
        #print('leafNode, prefixPath'),leafNode.disp(),print(prefixPath)
        if leafNode.parent != None:
            #print('leafNode.parent'),leafNode.parent.disp()
            #print('prefixPath',prefixPath)
            prefixPath.append(leafNode.name)
            #print('prefixPath-1',prefixPath)
            ascendTree(leafNode.parent, prefixPath)
    #headerTable['r'][1].parent.parent
    def findPrefixPath(basePat, treeNode): #treeNode comes from header table
        #print('basePat, treeNode',basePat), treeNode.disp()
        condPats = {}
        while treeNode != None:
            prefixPath = []
            #print('**********treeNode,prefixPath'),treeNode.disp(),print(prefixPath)
            ascendTree(treeNode, prefixPath)
            #print('treeNode'),treeNode.disp()
            if len(prefixPath) > 1: 
                condPats[frozenset(prefixPath[1:])] = treeNode.count #上溯[1:]
            #print('condPats',condPats)
            #print('__treeNode'),treeNode.disp()
            treeNode = treeNode.nodeLink
            #print('__treeNode',treeNode)#  'treeNode',当前树的节点
            
        return condPats
    
    def mineTree(myTree, headerTable, minSup, preFix, freqItemList):
        #print('myTree, headerTable, minSup, preFix, freqItemList',myTree, headerTable, minSup, preFix, freqItemList)
        bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1][0])]# 1.排序头指针表
        #print('bigL',bigL)
        for basePat in bigL:  #从头指针表的底端开始
            newFreqSet = preFix.copy()
            #print ('newFreqSet: ',newFreqSet)
            newFreqSet.add(basePat)
            #print ('finalFrequent Item: ',newFreqSet)    #添加的频繁项列表
            freqItemList.append(newFreqSet)
            #print('freqItemList',freqItemList)
            condPattBases = findPrefixPath(basePat, headerTable[basePat][1])
            #print ('condPattBases :',basePat, condPattBases)
            # 2.从条件模式基创建条件FP树
            myCondTree, myHead = createTree(condPattBases, minSup)
            #print ('head from conditional tree: ', myHead,myCondTree)
            if myHead != None: # 3.挖掘条件FP树
                #print ('conditional tree for: ',newFreqSet)
                #myCondTree.disp()            
                mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
    
    freqItemList = []
    mineTree(myTree, headerTable, 3, set([]), freqItemList)
    print(freqItemList)

     

    展开全文
  • 文章在研究基于剪枝概念格的...该方法在多剪枝格基础上进行导出频繁集的合并,进而获得全局频繁集,有效地降低了频繁集表示的规模;理论分析和实验结果表明,该方法能获得满足用户要求的近似所有全局频繁集。
  • 【CVPR 2021】剪枝篇(一):Network Pruning via Performance Maximization论文地址:主要问题:主要思路:具体实现:基本符号:子网络生成:性能预测网络:事件记忆模块:精度分布不平衡:性能最大化算法:实验...

    论文地址:

    https://openaccess.thecvf.com/content/CVPR2021/papers/Gao_Network_Pruning_via_Performance_Maximization_CVPR_2021_paper.pdf

    主要问题:

    通道剪枝是一种比较通用而且效果较好的模型压缩方法,通过修剪权重和激活的通道来获得一个小的子网络

    为了找到这样的子网络,许多现有的信道剪枝方法都使用分类损失作为指导

    然而修剪过的子网络并不一定具有较高的精度和低分类损失,而这往往是由于损失度量不匹配造成的(作者在后面的实验中也证明了性能预测网络的梯度和分类损失有不同的方向)

    因此在本文中,作者首先考虑了剪枝的损失度量不匹配问题,并提出了一种新的卷积神经网络的通道剪枝方法,用来直接最大化子网络的性能(即精度)

    主要思路:

    具体地说就是,我们训练一个独立的神经网络来预测子网络的性能,然后最大化网络的输出作为指导剪枝

    并且在这个剪枝过程中,我们可以直接使用子网络和小批量精度作为样本来训练性能预测网络(是否想到了强化学习)

    但是有效地训练这种性能预测网络往往是比较困难的,可能会面临灾难性遗忘和子网络分布不平衡的问题

    为了解决这个问题,作者使用一个事件记忆模块来沿着剪枝轨迹收集样本

    直接使用这些样本是有问题的,因为这些样本的准确性分布远不均匀,但是这个问题可以通过重新采样这些样本来解决(跟DQN里面经验池很像)

    利用上述技术,性能预测网络在剪枝过程中进行了增量训练

    在性能预测网络访问足够的样本并足够精确后,放到剪枝过程中,为通道剪枝提供额外的监督

    由于性能预测网络的训练和剪枝工作同时进行,因此没有额外的成本

    此外作者并没有放弃分类损失(通常是交叉熵损失),并且参考多目标学习的理念,在最终损失函数的定义中同时考虑了分类损失和性能最大化

    这背后的基本原理是,分类损失和性能最大化都为修剪提供了有用但不同的信息,并且合并它们将会得到更好的结果

    在这里插入图片描述

    具体实现:

    基本符号:

    在CNN中,第 i i i 层的特征图可以表示为 F i ∈ R C i × W i × H i , i = 1 , . . . , L F_i\in R^{C_i×W_i×H_i},i=1,...,L FiRCi×Wi×Hi,i=1,...,L,其中 C i C_i Ci 是通道数, L L L 是层数

    1 ( ⋅ ) 1(\cdot) 1() 表示指标函数, ⊙ ⊙ 表示点积

    子网络生成:

    正如我们前面所讨论的,直接采样子网络通常会产生琐碎的结果,特别是当剪枝率很高的时候

    为了训练一个针对信道剪枝的性能预测网络,我们不需要遍历所有的子网络

    假设原始模型的 FLOPs 为 T t o t a l T_{total} Ttotal,剪枝率为 p p p,我们对从 p T t o t a l pT_{total} pTtotal T t o t a l T_{total} Ttotal 的子网络很感兴趣

    我们首先丢弃 FLOPs 低于 p T t o t a l pT_{total} pTtotal 的子网络,因为它们不满足 FLOPs 约束

    因此,我们更喜欢生成具有特定 FLOPs 的有意义的子网络作为性能预测网络的训练样本

    我们开始先通过将原始模型修剪到目标 FLOPs p T t o t a l pT_{total} pTtotal 来生成这些子网络

    为了实现这一点,我们首先引入了基本的可微剪枝算法

    我们使用可微门来描述一个通道,对于第 i i i 层,门的定义为:

    o i = 1 / ( 1 + e − ( w i + s ) / τ ) o_i=1/(1+e^{-(w_i+s)/\tau}) oi=1/(1+e(wi+s)/τ)

    其中 1 / ( 1 + e − ( w i + s ) / τ ) 1/(1+e^{-(w_i+s)/\tau}) 1/(1+e(wi+s)/τ) 就是 sigmoid 函数, o i ∈ R C i o_i\in R^{C_i} oiRCi 并且 o i ∈ [ 0 , 1 ] o_i\in [0,1] oi[0,1],

    w i ∈ R C i w_i\in R^{C_i} wiRCi 是门控单元可学习的参数, s s s 是从 Gumbel 分布的采样, s ∈ G u m b e l ( 0 , 1 ) s\in Gumbel(0,1) sGumbel(0,1) τ \tau τ 是来控制锐度的超参数

    这里的 o i o_i oi 是连续的,用来精确地生成子网络

    然后我们进一步将其规范到 0 0 0 1 1 1

    a i = 1 o i > 1 2 ( o i ) a_i=\mathbb{1}_{o_i>\frac{1}{2}}(o_i) ai=1oi>21(oi)

    其中 a i ∈ { 0 , 1 } C i a_i\in \{0,1\}^{C_i} ai{0,1}Ci

    由于指示函数 1 ( ⋅ ) 1(\cdot) 1() 不可微,作者使用了直通式估计器(straight-through estimator)来计算梯度

    上述两个等式中的可微分门则使用 Gumbel-Solftmax 算法来近似伯努利分布(虽然有近似伯努利分布,但作者发现它们的差异也并不显著)

    为了实现最终的剪枝,我们将门控单元应用到特征图上:

    F i ^ = a i ⊙ F i \hat{F_i}=a_i⊙F_i Fi^=aiFi

    其中 a i a_i ai 被扩充到了 F i F_i Fi 的大小

    这样整个剪纸过程的优化目标就可以写作:

    min ⁡ w L ( f ( x ; a , Θ , y ) + R ( T ( a ) , p T t o t a l ) ) \min_wL(f(x;a,\Theta,y)+R(T(a),pT_{total})) minwL(f(x;a,Θ,y)+R(T(a),pTtotal))

    其中 w w w 包括了所有门控单元的可学习参数, a a a 是用于表示 CNN 模型结构的向量, a = c a t ( a 1 , . . . , a i , . . . , a L ) a=cat(a_1,...,a_i,...,a_L) a=cat(a1,...,ai,...,aL) T ( a ) T(a) T(a) 是由 a a a 定义的子网络的 FLOPs , x , y x,y x,y 分别是输入图片及其标签, f ( ⋅ ; a , Θ ) f(\cdot;a,\Theta) f(;a,Θ) 是由 Θ \Theta Θ 参数化的 CNN 模型(其结构由 a a a 定义), R ( T ( a ) , p T t o t a l ) = l o g ( m a x ( T ( a ) , p T t o t a l ) / p T t o t a l ) R(T(a),pT_{total})=log(max(T(a),pT_{total})/pT_{total}) R(T(a),pTtotal)=log(max(T(a),pTtotal)/pTtotal) 是推动子网络到达目标 FLOPs 的正则化项

    在上述等式的优化过程中会生成许多具有不同结构 a a a 的子网络

    假设精度 q q q 是基于给定的小批量计算的,我们就可以得到一对代表一个子网络及其精度的样本 ( a , q ) (a,q) (a,q)

    性能预测网络:

    一旦我们获得了样本 ( a , q ) (a,q) (a,q),我们就可以训练一个神经网络来预测给定子网络结构的性能

    我们首先定义了性能预测网络: q p r e d = P N ( a ) q_{pred}=PN(a) qpred=PN(a)

    P N ( ⋅ ) PN(·) PN() 就是所提出的性能预测网络

    然后使用 sigmoid 函数作为输出激活,因此 q p r e d q_{pred} qpred 0 0 0 1 1 1 的范围之间

    性能预测网络由全连接层和 GRU 组成。简而言之,全连接的层将每个层的结构向量转换为一个紧凑的向量表示形式,并使用GRU来连接不同的层

    作者使用GRU,是考虑到 a i − 1 a_{i−1} ai1 a i a_i ai 有隐式的依赖性,因此 GRU 可能会使得性能预测网络有可能捕获子网络中复杂的交互

    PN优化是一个回归问题,作者采用平均绝对误差损失(MAE)进行优化:

    m i n w p L p = ∣ q − P N ( a ) ∣ min_{w_p}L_p=|q-PN(a)| minwpLp=qPN(a)

    其中 w p w_p wp 是性能预测网络的参数

    事件记忆模块:

    作者做的这项工作的早期版本直接利用当前迭代的子网络来训练性能预测网络

    然而,作者发现它只会恶化剪枝过程,这是因为性能预测网络很难预测早期子网络,这种现象被称为灾难性遗忘(catastrophic forgetting)

    为了克服这个问题,我们需要定期回放以前的子网络

    因此作者进一步提出了一个事件记忆模块(Episodic Memory Module)来记忆早期的子网络

    事件记忆定义为 E M = ( A , Q ) EM=(A,Q) EM=(A,Q),其中 A ∈ R m × K , Q ∈ R K A\in R^{m×K},Q\in R^K ARm×K,QRK m m m 是向量 a a a 的长度, K K K 是当前 EM 的大小

    当我们向 EM 添加一个子网络时, K K K 自动加 1 1 1,并且 K K K 小于预先定义的最大 EM 容量 K m a x K_{max} Kmax

    但是正如前面提到的,小批量精度不是一个很好的估计精度;而另一方面,如果我们使用整个训练数据集来计算精度,计算成本就太过昂贵

    为了利用效率和精度,我们每 c c c 次迭代收集子网络和相应的小批量精度的均值,以构建一个增强的子网络表示:

    a ‾ = 1 a > 1 2 ( 1 c ∑ i = 1 c a i ) , q ‾ = 1 c ∑ i = 1 c q i \overline{a}=1_{a>\frac{1}{2}}(\frac{1}{c}\sum^c_{i=1}a_i),\overline{q}=\frac{1}{c}\sum^c_{i=1}q_i a=1a>21(c1i=1cai),q=c1i=1cqi

    注意如果 c c c 太大,那么上面的参数是无效的,导致增强的表示是无用的

    此外在收集子网络时,我们不比计算梯度

    假设我们在 EM 模块中已经有 K K K 个子网,那么 EM 就可以通过以下方式更新:

    P r − j = { A i = a ‾ , i = arg min ⁡ i ∣ Q i − q ‾ ∣ i f K = K m a x , A K + 1 = a ‾ o t h e r w i s e P_{r-j}= \begin{cases} A_i=\overline{a},i=\argmin_i |Q_i-\overline{q}|& if K=K_{max},\\ A_{K+1}=\overline{a} & otherwise \end{cases} Prj=Ai=a,i=iargminQiqAK+1=aifK=Kmax,otherwise

    也就是说当 K = K m a x K=K_{max} K=Kmax 时,我们将替换掉跟当前样本精度最相近的样本

    事实上,在修剪过程中,大多数子网络在满足目标 FLOPS 后都具有相似的性能

    因此,我们将使用 K m a x K_{max} Kmax 来鼓励子网络的多样性

    精度分布不平衡:

    在剪枝过程中,作者绘制了子网络精度的经验分布,发现精度集中在84左右:
    在这里插入图片描述
    为了防止性能预测网络提供没有价值的解决方案,并使其收敛速度更快,作者提出可以根据子网络的准确性进行重新采样

    即将所有的子网络按照 Q Q Q 的等差 1 N − 1 ( m a x ( Q ) − m i n ( Q ) ) \frac{1}{N-1}(max(Q)-min(Q)) N11(max(Q)min(Q)) 分为 N N N 个组

    然后我们对每一组的子网络进行计数,并根据其计数的倒数对其进行重新抽样

    这就相当于创建 N N N 个伪类并进行重新采样

    性能最大化算法:

    在拥有了一个相对靠谱的性能预测网络后,我们开始最大限度地提高搜索更好的子网络的性能

    子网络的性能可以表示为 P N ( a ) PN(a) PN(a),因此我们可以最大化 P N ( a ) PN(a) PN(a) 作为精度的估值

    max ⁡ w P N ( a ) \max_wPN(a) maxwPN(a) min ⁡ w 1 P N ( a ) \min_w\frac{1}{PN(a)} minwPN(a)1 是等价的,因此为了使得训练更稳定,我们优化目标就可以写作: min ⁡ w l o g ( 1 P N ( a ) ) \min_wlog(\frac{1}{PN(a)}) minwlog(PN(a)1)

    这样总的优化目标就可以表示为:

    min ⁡ w J ( w ) = L ( f ( x ; a , Θ ) , y ) + γ ( K , L P ) ⋅ l o g ( 1 P N ( a ) ) + λ R ( T ( a ) , p T t o t a l ) \begin{aligned} \min_wJ(w)=&L(f(x;a,\Theta),y)+\gamma(K,L_P)\cdot log(\frac{1}{PN(a)})\\ &+\lambda R(T(a),pT_{total}) \end{aligned} wminJ(w)=L(f(x;a,Θ),y)+γ(K,LP)log(PN(a)1)+λR(T(a),pTtotal)

    其中 γ ( K , L P ) \gamma(K,L_P) γ(K,LP) 是一个反映性能预测网络置信度的函数,被用来自动控制 l o g ( 1 P N ( a ) ) log(\frac{1}{PN(a)}) log(PN(a)1) 的量级, λ \lambda λ 被用来控制正则化的量级

    γ ( K , L P ) \gamma(K,L_P) γ(K,LP) 定义为: γ ( K , L P ) = 1 K ≥ K m a x 4 ( K ) ⋅ ( 1 − L p ) 2 \gamma(K,L_P) =1_{K\geq\frac{K_{max}}{4}}(K)\cdot(1-L_p)^2 γ(K,LP)=1K4Kmax(K)(1Lp)2,范围为 [ 0 , 1 ] [0,1] [0,1]

    通常来说更低的 L p L_p Lp 表示 P N ( ⋅ ) PN(\cdot) PN() 具有更高的置信度,但是 P N PN PN 的训练是一项增量学习任务,在 P N PN PN 能够访问足够的样本之前, L p L_p Lp 可能不是很可靠

    虽然存在损失-度量不匹配的问题,但来自损失函数和性能最大化的信息仍有一些重叠

    由于我们已经使用了分类损失,因此希望从性能最大化中获得独特的信息

    为了实现这一点,我们使梯度彼此正交

    假设 g L i = ∂ L ∂ w i g^i_L=\frac{\partial L}{\partial w_i} gLi=wiL 表示第 i i i 层的分类损失的梯度, g p i = ∂ l o g ( 1 P N ( a ) ) ∂ w i g^i_p=\frac{\partial log(\frac{1}{PN(a)})}{\partial w_i} gpi=wilog(PN(a)1) 是性能最大化损失的梯度

    这两个项的修正梯度为:

    g i = g L i + g ^ p i g^i=g^i_L+\hat{g}^i_p gi=gLi+g^pi

    其中 g p i g_p^i gpi 可以分解成两部分: g p i = g ^ p i + g ‾ p i g_p^i=\hat{g}_p^i+\overline{g}_p^i gpi=g^pi+gpi,其中 g ^ p i ⊥ g L i \hat{g}_p^i\bot{g}_L^i g^pigLi 并且 g ‾ p i \overline{g}_p^i gpi g L i g^i_L gLi 方向相同

    作者也给出了整个算法的伪代码:
    在这里插入图片描述

    实验结果:

    在这里插入图片描述

    展开全文
  • CART剪枝算法详解

    千次阅读 2019-01-09 12:27:12
    CART剪枝算法 CART剪枝算法从“完全生长“的决策树的底端剪去一些子树,使决策树变小(模型变简单),从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成:首先从生成算法产生的决策树T0底端开始不断剪枝,...

    CART剪枝算法

    CART剪枝算法从“完全生长“的决策树的底端剪去一些子树,使决策树变小(模型变简单),从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成:首先从生成算法产生的决策树T0底端开始不断剪枝,直到T0的根节点,形成一个子树序列{T0,T1 ,…, Tn};然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,从中选择最优子树。

    1. 剪枝,得到子树序列

    子树的损失函数:
                C α ( T ) = C ( T ) + α ∣ T ∣ {C_\alpha }(T) = C\left( T \right) + \alpha \left| T \right| Cα(T)=C(T)+αT
      T为任意子树,C(T)为对训练数据的预测误差,可以是基尼指数,|T|为子树T的叶子节点个数,α>= 0为参数,Cα(T)为参数是α时的子树T的整体损失,|T|衡量树的复杂度,α权衡训练数据的拟合程度与树的复杂度。
    为了使得损失函数减小,有两种办法:
    1> 降低第一部分的不确定次数,但我们知道这是不可能的了,因为降低不确定次数的办法是再找寻一个特征,或者找寻特征的最优切分点。这在生成决策时就已经决定了,无法改变。 (换句话说就是使得子树T的预测误差下降,这可能就要重新选择特征)
    2> 进行剪枝操作,这是可以的。剪枝最明显地变化就是叶结点个数变少。假设是一个三叉树,那么一次剪枝它的叶结点数减少2个。变化量为2α,有了这变化量,我们就可以用来求解最优决策子树了。

           在α参数给定时,假设只有一个子结点发生剪枝,那么该子结点上的叶结点都将全部归并到该结点,由此我们计算此结点的不确定次数。倘若不确定次数增大的量超过2α,那么剪枝失败,算法将尝试其他子结点。因为新得的子树损失函数反而增大。  这从侧面又反映了什么样的事实?  该子结点的分类规则大大降低了不确定次数,并不存在噪声,所以没必要进行剪枝。所以在剪枝过程中,找寻的就是那些噪声点,被过度规则的那些子结点,把这些合并了,万事大吉,自然而然决策树的准确率将上升。

           那么问题来了,α是未知的,从函数和以上的分析中我们可以看出α的值对剪枝结果有很大的影响,我们如何找到这个合适的α来使拟合程度与复杂度之间达到最好的平衡呢,最好的办法就是,我们将α从0取到正无穷,对于每一个固定的α,我们都可以找到使得Cα(T)最小的最优子树T(α) 。当α 很小的时候,T0是最优子树,当α很大的时候,单独一个根节点Tn是最优的子树。(Breiman等人证明:可以用递归的方法对树进行剪枝,将a从小增大,a0<a1<…<an<+无穷,产生一系列的区间[ai,ai+1),i =0,1,…,n;剪枝得到的子树序列对应着区间[ai,ai+1),i =0,1,…,n的最优子树序列{T0, T1, … , Tn},序列中的子树是嵌套的。嵌套应该很好理解,向上剪枝的过程,树越变越小嘛)

    我们通过无限个α去求有最优的子树序列式很困难的,是一个NP完全问题,那怎么办呢?

           这里有一个前提,对固定的α,一定存在使损失函数Cα(T)最小的子树,将其表示为Tα。Tα在损失函数最小的意义下是最优的,这样的最优的子树是唯一的。其实所要表达的意思就是Tα和α是一一对应的。
    我们通过无限个α去求最优的子树序列是很困难的,但是根据剪枝的核心思想我们知道,无论多么复杂的决策树,生成的最优子树序列都是有限的,这里记作{T0,T1 ,…, Tn},那么我们只需要寻找每一个最优子树对应的α不就可以了嘛。

           如上分析,我们现在的思路就是要得出最优子树序列,这子树序列又如何生成呢?(怎么感觉说着说着又说回来了呢,我们的最终结果不就是要得到这些最优子树序列吗?为什么还要记录相应的α值呢?这个本人也不胜理解)我们先说说求子树序列的事情。

           我们先假设我们找到了当前的最优子树,且必然发生剪枝(一定要注意这句话,这是我们接下来所有推导的前提)。具体地,从整体树T0开始剪枝,我们每次剪枝剪的都是某个内部节点的子节点,也就是将某个内部节点的所有子节点回退到这个内部节点里,并将这个内部节点作为叶子节点。因此在计算整体的损失函数时,这个内部节点以外的值都没变,只有这个内部节点的局部损失函数改变了,因此我们本需要计算全局的损失函数,但现在只需要计算内部节点剪枝前和剪枝后的损失函数。

    对任意内部节点t,
    剪枝前的状态:有|Tt| 个叶子节点,预测误差是C(Tt)
    剪枝后的状态:只有本身一个叶子节点,预测误差是C(t)
    剪枝前以t结点为根结点的子树的损失函数是:
    C α ( T t ) = C ( T t ) + α ∣ T t ∣ {C_\alpha }({T_{\rm{t}}}) = C\left( {{T_t}} \right) + \alpha \left| {{T_t}} \right| Cα(Tt)=C(Tt)+αTt剪枝以后以t为单结点树的损失函数是: C α ( t ) = C ( t ) + α {C_\alpha }(t) = C\left( t \right) + \alpha Cα(t)=C(t)+α
    当alpha=0及alpha充分小,有不等式 C α ( T t ) < C α ( t ) {C_\alpha }({T_t}) < {C_\alpha }(t) Cα(Tt)<Cα(t)
    当alpha增大时,在某一alpha有
    C α ( T t ) = C α ( t ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ( 1 ) {C_\alpha }({T_t}) = {C_\alpha }(t)·······(1) Cα(Tt)=Cα(t)1
    当alpha再增大时,以上不等式(1)反向。在(1)式的情况下, α 1 = C ( t ) − C ( T t ) ∣ T t ∣ − 1 {\alpha _1} = \frac{{C(t) - C({T_t})}}{{\left| {{T_t}} \right| - 1}} α1=Tt1C(t)C(Tt)我们之前假设在得到最优子树时必然发生了剪枝,那么什么时候必然发生剪枝?当我们取得损失函数中的α>=α1时,必然对Tt进行剪枝,因为此时剪枝后损失函数的值要比剪枝前小。

           那是不是剪掉当前的t结点就可以得到最优子树了呢,当然不是,不同的结点会计算出不同的α1,我们就以此α1作为损失函数的α值(解释一下,当α=α1时,该节点剪枝前后的损失函数的值是一样的,但是剪枝后结点少,也必然要剪枝,此时该结点处的损失函数值也是最小的),这时会算出不同的损失函数值来,当然是取损失函数值最小的结点来剪枝。这里我们将结点t作为变量,计算得到的α记为α(t),则有如下公式: min ⁡ t C ( t ) + α ( t )         ( 2 ) \mathop {\min }\limits_t C(t) + \alpha (t)    (2) tminC(t)+α(t)    2但是在李航的《统计学习方法》中却用以下公式来衡量应该剪枝的结点: g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1     ( 3 ) g(t) = \frac{{C(t) - C({T_t})}}{{\left| {{T_t}} \right| - 1}}  (3) g(t)=Tt1C(t)C(Tt)  3       有一篇博文是这样解释的:整体损失函数 = 内部节点t的损失函数 + 其他节点的损失函数和 我们在计算2式的时候只是让等号右边的第一项达到了最小,可是局部结点的损失函数最小并不能代表整体的损失函数最小,所以并不能以2式来剪枝。但本人认为这种说法经不起推敲,如果我们对2式了解透彻的话应该知道,在α确定的情况下,整体的损失函数的计算相当于是对局部结点损失函数的累加,在某个结点剪枝而其他结点不改变的情况下,2式等号右边的第二项并没有变化,因此这并不能说明问题。但我们可以这样说,针对单个结点的剪枝我们可以用2式来衡量,可多个结点的剪枝用这种局部结点的计算公式是行不通的。

           而α就不一样了,在上面已经说过了,剪枝得到的子树序列对应着区间[ai,ai+1),i =0,1,…,n的最优子树序列{T0, T1, … , Tn},我们在不同的α(g(t))下剪枝可以得到一一对应的有限个最优子树。在李航的《统计学习方法》中,将g(t)解释为剪枝后整体的损失函数减少额程度,如果不看之前的推导,只看公式3,我们是可以理解的,其实这跟信息增益的概念差不多,但加入了结点个数这个变量来权衡模型复杂度的影响。在T0中剪去g(t)最小的Tt,将得到的子树作为T1,同时将最小的g(t)设为α1。T1为区间[α1, α2)的最优子树。
    那为什么是最小的g(t)呢?(以下是别的博文上的解释,说的很好,我就直接拿过来用了,自己就不再赘述了)
    在这里插入图片描述
           以图中两个点为例,结点1和结点2,g(t)2大于g(t)1, 假设在所有结点中g(t)1最小,g(t)2最大,两种选择方法:当选择最大值g(t)2,即结点2进行剪枝,但此时结点1的不修剪的误差大于修剪之后的误差,即如果不修剪的话,误差变大,依次类推,对其它所有的结点的g(t)都是如此,从而造成整体的累计误差更大。反之,如果选择最小值g(t)1,即结点1进行剪枝,则其余结点不剪的误差要小于剪后的误差,不修剪为好,且整体的误差最小。从而以最小g(t)剪枝获得的子树是该alpha值下的最优子树!

           通过以上的说明,我们现在应该可以理解,将α从小增大,产生一系列的区间,剪去 g(t)属于[αi, αi+1)的对应的结点,就会得到该区间上的最优子树,如此剪下去,直到得到根结点。在这一过程中,不断增加α的值,产生新的区间。

    2. 从剪枝得到的子树序列中通过交叉验证选取最优子树Tα。

           具体地,利用独立的验证数据集,测试子树序列T0, T1, … , Tn中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中,每棵子树T0, T1, … , Tn都对应于一个参数α0, α1, … ,αn。所以,当最优子树Tk确定时,对应的αk也确定了,即得到最优决策树Tα。

    最后附上CART剪枝算法:
    输入:CART算法生成的决策树T0
    输出:最优决策树Tα
    (1)设k=0,T=T0
    (2)设α=+∞
    (3)自下而上地对各个内部结点t计算C(Tt),|Tt|以及
    g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 g(t) = \frac{{C(t) - C({T_t})}}{{\left| {{T_t}} \right| - 1}} g(t)=Tt1C(t)C(Tt) α = m i n ( α , α ( t ) ) α=min(α,α(t)) α=min(α,α(t))这里,Tt表示t为根结点的子树,C(Tt)是对训练数据的预测误差,|Tt|是Tt的叶结点个数。
    (4)对α(t)=α的内部结点t进行剪枝,并对叶结点t以多数表决法决定其类,得到树T。
    (5)设k=k+1,αk=α,Tk=T。
    (6)如果Tk不是由根结点及两个叶结点构成的树,则回到步骤3;否则令Tk=Tn。
    (7)采用交叉验证法在子树序列T0,T1,…,Tn中选取最优子树Tα
    最后,我还是不明白这一点,为什么我们还要记录最终的α值,不是只要得到最优子树就可以了吗?

    参考文献:

    1. Demon的黑与白 https://blog.csdn.net/u014688145/article/details/53326910
    2. MrTriste https://blog.csdn.net/wjc1182511338/article/details/76793164
    3. 李航. 统计学习方法[M]. 北京:清华大学出版社,2012
    展开全文
  • 决策树的先剪枝和后剪枝

    万次阅读 2017-12-25 17:55:06
    转载自:...剪枝一般是为了避免树的过于复杂,过于拟合而进行的一个动作,剪枝操作是一个全局的操作。(二)预剪枝: 预剪枝就是在树的构建过程(只用到训练集),设置一个阈值(样本个数小于预定阈
  • (一)剪枝算法的简介: 剪枝一般是为了避免树的过于复杂,过于拟合而进行的一个动作,剪枝操作是一个全局的操作。 (二)预剪枝: 预剪枝就是在树的构建过程(只用到训练集),设置一个阈值(样本个数小于预定阈值或...
  • 利用L1范数的CNN模型剪枝

    千次阅读 2021-12-21 09:29:36
    剪枝4.4.微调参考文献 1.原理 ​ 缩放因子和稀疏性引起的惩罚。我们的想法是为每个通道引入一个缩放因子 γ,它与该通道的输出相乘。然后我们联合训练网络权重和这些缩放因子,并对后者进行稀疏正则化。最后,我们用...
  • 决策树的剪枝:REP/PEP/CCP算法

    千次阅读 多人点赞 2019-02-18 11:25:08
    面对这样的问题,我们一般所采用的方法是对决策树进行剪枝操作。 决策树的过拟合问题 决策树算法生成的决策树非常庞大,每个变量都被详细地考虑过。在每一个叶节点上,只要继续分支会有信息增益的情况,不管信息...
  • 文章目录1. CNN模型model slimming常用方法1.1 Low-rank Decomposition1.2 Weight Quantization1.3 Weight Pruning / ... YOLO V3 剪枝思路2.1 主要思路2.2 参考文献3. YOLO V3剪枝开源项目简介3.1 [tanluren/yolov3
  • 我们提出来一个最新的元学习方法,对非常深的神经网络进行自动化通道剪枝。首先训练出一个PruningNet,对于给定目标网络的任何剪枝结构都可以生成权重参数。我们使用一个简单的随机结构采样方法来训练PruningNet,...
  • 随着决策树深度的增大,模型效果会变化,但增大太多就会导致过拟合的情况,对于过拟合,常见的有两咱优化方式:剪枝优化 和 随机森林。这篇博客简要介绍剪枝优化,随机森林在后续的博客中再做介绍。
  • 训练,剪枝和微调4.4.结果4.5.多程方案的结果5.分析6.结论参考文献 通过网络瘦身学习高效的卷积网络 摘要 ​ 深度卷积神经网络 (CNN) 在许多实际应用中的部署在很大程度上受到其高计算成本的阻碍。在本文中,我们为 ...
  • 决策树算法与不同的剪枝方法

    千次阅读 2017-08-15 17:10:46
    剪枝:使用测试集递归剪枝,计算原始测试错误率,如果两个叶节点合并后测试错误率降低了,就将其合并。 优点: 计算复杂度不高,可以离线生成树,输出结果易于理解,对缺失值不敏感,可以处理不相关特征...
  • 该作者使用了三种剪枝方法,分别是结构化剪枝(每层剪枝的通道比例是预定义的),自动化剪枝(全局剪枝比例确定,每层剪枝比例由算法决定),非结构化权重剪枝(只有权重的剪枝比例是预定义的)。 根据以上三种方法...
  • C4.5:对于ID3可能越分越细导致过拟合,于是C4.5中,优化要除以分割太细的代价,这个比值叫做信息增益率,显然分割太细分母增加,信息增益率会降低。 信息增益比 = 惩罚参数 * 信息增益 CART:分类回归树...
  • 谈搜索算法的剪枝优化

    千次阅读 2014-07-10 21:14:04
    【摘要】本文讨论了搜索算法中“剪枝”这一常见的优化技巧. 首先由回溯法解决迷宫问题展开论述,介绍了什么是剪枝; 而后分析剪枝的三个原则正确、准确、高效,并分别就剪枝的两种思路:可行性剪枝及最优性剪枝,结合例题...
  • 前面记录了特征值的选取,现在我们就来说一下剪枝。 决策树的剪枝 在决策树创建时,由于数据中的噪声和离群点,许多分枝反映的是训练数据中的异常,剪枝方法处理这种过分拟合数据的问题。 有常用的两种剪枝方法:...
  • 权重共享方案进一步允许设计一种Single-Path Vision Transformer剪枝方法(SPViT),在给定目标效率约束的情况下,快速将预训练的vit剪枝成精确而紧凑的混合模型,并显著降低搜索成本。在两个具有代表性的ViT模型上...
  • YOLOV2网络剪枝

    千次阅读 2019-08-20 12:26:41
    其基本的思想是:神经网络的参数众多,但其中有些参数对最终的输出结果贡献不大而显得冗余,剪枝顾名思义,就是要将这些冗余的参数剪掉。 首先,需要根据对最终输出结果的贡献大小来对模型的神经元们排序,然后,...
  • 当我们加载一个训好的模型,刚开始剪枝训练时,L(perf)较小(因为这初始模型已经训好了嘛),P(K)较大(因为kernel都还比较大嘛),所以第一导出的梯度显著小于第二导出的梯度,K在惩罚主导的梯度影响下,...
  • 语言模型srilm(二) prune剪枝

    千次阅读 2015-12-15 22:29:58
    为什么引入剪枝传统的N-gram backoff模型,提升性能的两条主要路径是增加阶数和增加语料,两者带来的共同副作用是增加了模型的大小,进而增加了语音识别解码器的内存占用。为了减少模型的大小,同时保证性能最大化,...
  • 决策树的剪枝理论

    千次阅读 2018-08-15 10:08:18
    所谓的剪枝就是对决策树的叶节点进行修剪,把多个叶节点进行合并,把小类合成一个大类然后以其中所占个数最多的类作为该大类的类。其实几乎决策树的构建都要进行剪枝操作,剪枝操作比树的构造还要重要 剪枝分为两...
  • 基于ID3、C4.5与CART的决策树三生成与剪枝原理详解1、决策树学习决策树学习本质:从训练数据集中归纳出一组分类规则。可能有多个,可能没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。...
  • L_0范数简单的计算了向量中的非零,它是一个不可微分的常量函数。 所以这是一个非常困难的组合优化问题。 2、应用变分优化方法将不可微的函数转化为可微函数。这通常是通过在参数$ \ theta $上引入一个概率分布p_...
  • 频繁集的产生格结构(lattice structure)常常用来表示所有可能的集。发现频繁集的一个原始方法是确定格结构中每个候选集的支持度。但是工作量比较大。另外有几种方法可以降低产生频繁集的计算复杂度。减少...
  • 小文件合并

    2021-01-05 17:12:41
    但要注意到,我们一般只合并n天前的数据,比如3天前,所以基本上我们是在合并冷数据,合并热数据可能出现问题,一般不推荐合并。 小文件合并工具大致可分为 小文件目录扫描 和 小文件合并 两个阶段,下面予以介绍。 ...
  • YOLOV3剪枝 论文:Network Slimming-Learning Efficient Convolutional Networks through Network Slimming 剪枝项目参考https://github.com/tanluren/yolov3-channel-and-layer-pruning 主要思路 1、利用...
  • 分析了现有的对Apriori算法的改进方向,新算法将Apriori的剪枝步骤合并入从Lk-1与Lk-1连接生成Ck的连接步骤,通过使用临时集TQ存储Lk-1中单个数据集与Lk-1中其他数据集连接的结果,从而将被扫描集合的大小从Lk...
  • 在训练过程中,对权重的更新加以正则进行诱导,使其更加稀疏,使大部分的权值都为 0 。 http://papers .nips .cc /paper/ 6504 -learning-structured-sparsity- in -deep-neural-networks .pdf 动态的模型...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,326
精华内容 1,730
关键字:

项合并剪枝

友情链接: Reader_First.rar