文档章节

Pocket Perceptron 算法

无若
 无若
发布于 2017/08/03 22:16
字数 1163
阅读 22
收藏 0
点赞 0
评论 0

Perceptron (感知器)算法是存在一定限制的

  1. Perceptron 算法针对的数据必须是线性可分的!
  2. Perceptron 算法要运行多久才能运行完毕?

在上一篇文章中(感知器算法),如果出现如下样本:

              orgi_samples = [
                [[20, 10], -1], 
                [[23, 12], -1],
                [[20, 8], -1], 
                [[25, 14], 1], 
                [[28, 15], 1],
                [[30, 38], 1], 
                [[1, 1], 1], # 噪声样本 
                ]

其中有一个是模拟的噪声,那么整个程序就会陷入死循环,感知器整个就会陷入混乱,永远找不到要求的阈值。那么就需要在容忍噪声样本的情况下,在所有阈值中选取一个错误率最小的,那么用公式表示就是:

可惜的是这要进行多少次纠正才能选取所有的阈值,依然是一个未知数,所以必须是控制指定轮次,在有限阈值的情况下进行选取。

具体做法即为 Pocket Perceptron 算法,其核心就是把每次(t)的 W(t) 与最新的 W(t+1) 的成功次数进行比较,如果成功次数 W(t+1) 比较多,则对 Pocket 中的 W 进行替换,这一过程就是其实就是贪心算法。需要注意的是,这个最终的 W,不是完美的,其最终不一定是全部满足所有样本的,即可能是忽略一些噪声的。

Pocket Perceptron 算法步骤:

  1. 初始化 pocket 的 weight 为 W
  2. 轮次 从 t = 0,1,2 ... n (n 为人为控制的次数)
  • (1) 找到一个随机的错误  被叫做  
  • (2) 尝试通过下面的方法修正错误:
  • (3) 如果   让错误更少发生,那么就让  替代掉  ,直到迭代结束。注意,这里迭代次数是由用户自主决定的。
  • (4) 最终取得的 W (被叫做 ) 作为 g。
#coding=utf-8

import numpy as np
import operator
import Queue

class PocketPerceptron(object):

    def __init__(self, orgi_weight = [], orgi_samples = [], run_trun_times = 2):
        """
        Args:
            orgi_weight:  原始权重
                例子:
                orgi_weight = [3, 7]
                
            orgi_samples: 原始样本
                例子:
                orgi_samples = [
                [[20, 10], -1], 
                [[23, 12], -1],
                [[20, 8], -1], 
                [[25, 14], 1], 
                [[28, 15], 1],
                [[30, 38], 1], 
                [[1, 1], 1], # 噪声样本 
                ]
                    
            run_trun_times: 运行轮次倍数(样本数量的倍数),默认为样本数量的2倍
        """
        self.weight_t = 0
        self.weight = np.array(orgi_weight)
        self.orgi_samples = orgi_samples
        # 最大运行轮次为 样本数量的 倍数
        self.max_turn = run_trun_times * len(orgi_samples)
        # 用于存放最佳结果的口袋
        self.pocket = {
            'current_weight_t': 0, 
            'max_succ_cnt': 0
        }
        
        # 用于已经计算过的队列,减少统计时的计算量
        self.out_queue = Queue.Queue()
    
    def add_orgi_sample(self, new_sample=[]):
        self.orgi_samples.append(new_sample)
    
    def statistics_matching(self, sample_t, samples, results):
        # print 'current_wt:', self.weight_t, 'queue_size:', self.out_queue.qsize()
        succ_list = []
        while not self.out_queue.empty():
            elem = self.out_queue.get()
            # print 'current_wt:', self.weight_t, 'queue_inx:', elem
            succ_list.append(elem)
        
        matching_cnt = 0
        for i, elem in enumerate(samples):
            if i in succ_list:
                matching_cnt += 1
                continue
                
            out = (self.weight_t * sample_t) + np.dot(self.weight, elem)
            #print self.weight_t, i, np.sign(out) == results[i]
            if np.sign(out) == results[i]:
                # print 'current_wt:', self.weight_t, 'calc_inx:', i
                matching_cnt += 1
                
        return matching_cnt
    
    def greed(self, sample_t, samples, results):
        """
        贪心函数,一旦发现成功次数多的 weight_t ,立即对 pocket 中的 weight_t 进行替换
        """
        current_weight_t_succ_cnt = self.statistics_matching(sample_t, samples, results)

        if self.pocket['max_succ_cnt'] < current_weight_t_succ_cnt:
            self.pocket['current_weight_t'] = self.weight_t
            self.pocket['max_succ_cnt'] = current_weight_t_succ_cnt
            
    
    def learning(self):
        samples = []
        results = []

        for s in self.orgi_samples:
            samples.append(np.array(s[0]))
            results.append(np.array(s[1]))
            
        sample_t = 1
        inx = 0
        run_turn = 0
        
        self.pocket['current_weight_t'] = self.weight_t
        self.pocket['max_succ_cnt'] = 0
        while inx < len(samples):
            # print 'turn: ', inx, ', w:', self.weight_t   
            out = (self.weight_t * sample_t) + np.dot(self.weight, samples[inx])
            
            if np.sign(out) != results[inx]:
                self.greed(sample_t, samples, results)
                #print 'curr pocket:', self.pocket['current_weight_t'], self.pocket['max_succ_cnt']
                self.weight_t = self.weight_t + (results[inx] - out) * sample_t
                inx = 0
                run_turn += 1
                if run_turn > self.max_turn:
                    break
            else:
                self.out_queue.put(inx)
                inx += 1
        
        self.greed(sample_t, samples, results)
        #print 'finally pocket:', self.pocket['current_weight_t'], self.pocket['max_succ_cnt']
        self.weight_t = self.pocket['current_weight_t']
        print 'finally weight:', self.weight_t
        
    
    def judge(self, new_sample=[]):
        new_sample = np.array(new_sample)
        out = np.dot(self.weight, new_sample) + self.weight_t
        return np.sign(out)


if __name__ == '__main__':

    orgi_samples = [
        [[31, 20], 1], 
        [[20, 10], -1], 
        [[20, 15], -1],
        [[20, 8], -1], 
        [[40, 23], 1],
        [[30, 38], 1], 
        [[1, 1], 1], # 噪声样本 
        [[2, 2], 1], # 噪声样本 
        [[30, 26], 1],
        ]

    orgi_weight = [3, 7]

    print u'输入样本进行学习'
    pocket_perceptron = PocketPerceptron(orgi_weight, orgi_samples, 2)
    pocket_perceptron.learning()
    print ''
    
    print u'样本验证'
    for sample in orgi_samples:
       judge = pocket_perceptron.judge(sample[0]) 
       print sample[0], 'judge out:', judge, 'sample out:', sample[1]
    print ''
    
    print u'新建一个输入,查看此样本是否能被批准'
    # 新建一个输入,查看此样本是否能被批准
    print "30, 8: ", pocket_perceptron.judge([30, 8]) # 1
    print ''
    
    # 添加样本重新学习
    print u'添加样本重新学习'
    pocket_perceptron.add_orgi_sample([[30, 8], -1])
    pocket_perceptron.learning()
    print ''
    
    print u"新样本验证"
    print "30, 8: ", pocket_perceptron.judge([30, 8]) # -1
    print "30, 11: ", pocket_perceptron.judge([30, 11]) # 1
    
    

运行结果:

输入样本进行学习
finally weight: -166

样本验证
[31, 20] judge out: 1 sample out: 1
[20, 10] judge out: -1 sample out: -1
[20, 15] judge out: -1 sample out: -1
[20, 8] judge out: -1 sample out: -1
[40, 23] judge out: 1 sample out: 1
[30, 38] judge out: 1 sample out: 1
[1, 1] judge out: -1 sample out: 1
[2, 2] judge out: -1 sample out: 1
[30, 26] judge out: 1 sample out: 1

新建一个输入,查看此样本是否能被批准
30, 8:  -1

添加样本重新学习
finally weight: -166

新样本验证
30, 8:  -1
30, 11:  1

 

© 著作权归作者所有

共有 人打赏支持
无若

无若

粉丝 41
博文 128
码字总数 106726
作品 0
南京
程序员
TensorFlow实践——Multilayer Perceptron

本文是在Softmax Regression的基础上增加了一个隐含层,实现了Multilayer Perceptron的一个模型,Multilayer Perceptron是深度学习模型的基础,对于Softmax Regression的TensorFlow实现,可以...

google19890102 ⋅ 04/26 ⋅ 0

4.2 - 《机器学习基石》Home Work 1 Q.18-20

第18题要求在第16题 Random PLA 算法的基础上使用 Pocket 算法对数据做二元划分。Pocket算法在第2篇文章介绍过,通常用来处理有杂质的数据集,在每一次更新 Weights(权向量)之后,把当前犯...

Lee的白板报 ⋅ 2014/03/17 ⋅ 0

PHP 机器学习库--PHP-ML

PHP-ml 是 PHP 的机器学习库。同时包含算法,交叉验证,神经网络,预处理,特征提取等。 PHP-ML 要求 PHP >= 7.0。 示例 简单的分类示例: use PhpmlClassificationKNearestNeighbors; $sam...

匿名 ⋅ 2017/03/13 ⋅ 59

机器学习笔记-Neural Network

林轩田机器学习技法关于特征学习系列,其中涉及到 , , , , , , - , 等。 机器学习笔记-Neural Network 机器学习笔记-Deep Learning 机器学习笔记-Radial Basis Function Network 机器...

robin_Xu_shuai ⋅ 2017/12/09 ⋅ 0

机器学习基石(一)

《机器学习基石》是国立台湾大学林轩田讲授的一门课程,课程的续集是《机器学习技法》。《机器学习基石》是网上热荐的一门机器学习课程,相关资源可以在youtube找到,也可在评论区索要云盘链...

宣的写字台 ⋅ 2017/12/04 ⋅ 0

感知机(perceptron)

感知机属于有监督的学习,生成的模型称为判别模型。其通过特定的函数将输入的特征向量,输出为实例的类别(+1或-1),该函数即为将实例划分为两类的分离超平面。为获得最优化的超平面,感知机...

abebill ⋅ 2017/06/30 ⋅ 0

中文自然语言处理工具包--FudanNLP

FudanNLP主要是为中文自然语言处理而开发的工具包,也包含为实现这些任务的机器学习算法和数据集。 演示地址: http://jkx.fudan.edu.cn/nlp/query FudanNLP目前实现的内容如下: 中文处理工具...

匿名 ⋅ 2010/07/19 ⋅ 0

写给大家看的机器学习书(第三篇)

题记 —— 我们为何出发 在开始这个系列文章的第三篇之前,为了对初次见面的朋友更友好,将这个题记放在前面。 哪怕所有的初心最终都被遗忘,至少现在的我们足够认真。 ——阿真 机器学习很火...

八汰 ⋅ 2017/03/06 ⋅ 0

文本分析算法和机器学习算法

Word2Vec算法,词语向量化,可以计算词之间的相似度 TextRank文章关键字提取  HanLP汉语言处理包 https://github.com/hankcs/HanLP(汉语分词,文章关键字提取,文章摘要提取) Maven...

满小茂 ⋅ 2016/11/11 ⋅ 0

2 - 学习回答是非题

课程来自Coursera上的国立台湾大学《机器学习基石》(Machine Learning Foundations),由林轩田老师讲授。 如何设定目标函数集 首先回顾下机器学习的一般性定义: 集合{χ}是所有可能的输入...

Lee的白板报 ⋅ 2014/03/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

istio 文档

https://istio.io/docs/concepts/ https://istio.io/docs/concepts/traffic-management/handling-failures/ https://istio.io/docs/concepts/traffic-management/rules-configuration/......

xiaomin0322 ⋅ 14分钟前 ⋅ 0

编程语言的作用及与操作系统和硬件的关系

一、编程语言的作用及与操作系统和硬件的关系 作用:编程语言是计算机语言,是一种程序员与计算机之间沟通的介质,通过编程语言可以使得计算机能够根据人的指令一步一步去工作,完成某种特定...

slagga ⋅ 25分钟前 ⋅ 0

runtime实现按钮点击事件

也不能说是实现吧,,,就是有点类似于RAC里边的写法,不用给btn添加另外的点击事件,就那个add...select...这样子很不友好,来看下代码: [self.btn handleControlEvent:UIControlEventTou...

RainOrz ⋅ 25分钟前 ⋅ 0

Windows系统运维转linux系统运维的经历

开篇之前,首先介绍一下我的背景把:我是一个三线城市的甲方运维。最近,在《Linux就该这么学》书籍的影响下和朋友小A(Linux运维已经三年了,工资也比我的高很多)的影响下,决定转行。最近...

linux-tao ⋅ 26分钟前 ⋅ 0

zip压缩工具,tar打包工具

zip压缩工具 zip打包工具跟前面说到的gzip,bz2,xz 工具最大的不一样是zip可以压缩目录。如果没有安装,需要使用yum install -y zip 来安装。安装完之后就可以直接使用了,跟之前提到的压缩...

李超小牛子 ⋅ 34分钟前 ⋅ 0

使用npm发布自己的npm组件包

一、注册npm账号 官网:https://www.npmjs.com/signup 注册之后需要进行邮箱验证,否则后面进行组件包发布时候会提示403错误,让进行邮箱核准。 二、本地新建一个文件夹,cd进入后使用npm i...

灰白发 ⋅ 35分钟前 ⋅ 0

010. 深入JVM学习—垃圾收集策略概览

1. 新生代可用GC策略 1. 串行GC(Serial Copying) 算法:复制(Copying)清理算法; 操作步骤: 扫描年轻代中所有存活的对象; 使用Minor GC进行垃圾回收,同时将存活对象保存到“S0”或“S...

影狼 ⋅ 36分钟前 ⋅ 0

JVM性能调优实践——JVM篇

在遇到实际性能问题时,除了关注系统性能指标。还要结合应用程序的系统的日志、堆栈信息、GClog、threaddump等数据进行问题分析和定位。关于性能指标分析可以参考前一篇JVM性能调优实践——性...

Java小铺 ⋅ 37分钟前 ⋅ 0

误关了gitlab sign-in 功能的恢复记录

本想关sign-up的,误点了sign-in 退出后登录界面提示: No authentication methods configured 一脸懵逼.. 百度后众多方案说修改application_settings 的 signin_enabled字段; 实际上新版本字段...

铂金蛋蛋 ⋅ 38分钟前 ⋅ 0

登录后,后续请求接口没有带登录cookie可能原因

1.XMLHttpRequest.withCredentials没设置好,参考https://developer.mozilla.org/zh-CN/docs/Web/API/XMLHttpRequest/withCredentials...

LM_Mike ⋅ 38分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部