icpc 2018 World Finals Problem A-Catch the Plane

一、题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Your plane to the ICPC Finals departs in a short time, and the only way to get to the airport is by bus.
Unfortunately, some of the bus drivers are considering going on strike, so you do not know whether
you can get to the airport on time. Your goal is to plan your journey in such a way as to maximize the
probability of catching your plane.
You have a detailed map of the city, which includes all the bus stations. You are at station 0 and the
airport is at station 1. You also have a complete schedule of when each bus leaves its start station and
arrives at its destination station. Additionally, for each bus you know the probability that it is actually
going to run as scheduled, as opposed to its driver going on strike and taking the bus out of service.
Assume all these events are independent. That is, the probability of a given bus running as planned does
not change if you know whether any of the other buses run as planned.
If you arrive before the departure time of a bus, you can transfer to that bus. But if you arrive exactly
at the departure time, you will not have enough time to get on the bus. You cannot verify ahead of time
whether a given bus will run as planned – you will find out only when you try to get on the bus. So if
two or more buses leave a station at the same time, you can try to get on only one of them.

查看更多

评论

反向传播函数简介


参考:

[1]. 深层神经网络:搭建深层神经网络块(吴恩达)


THE END.

评论

sklearn.model_selection 交叉验证

前言

1. 什么是交叉验证法?

它的基本思想就是将原始数据(dataset)进行分组,一部分做为训练集来训练模型,另一部分做为测试集来评价模型。

2. 为什么用交叉验证法?

交叉验证用于评估模型的预测性能,尤其是训练好的模型在新数据上的表现。交叉验证本身只能用于评估,但是可以对比不同 Model 或者参数对结构准确度的影响。然后可以根据验证得出的数据进行调参,也可以在一定程度上减小过拟合。

查看更多

评论

集成学习 实践

我们使用 集成学习 方法来对乳腺癌预测,这里的例子使用的数据集是 Wisconsin Breast Cancer dataset/Chapter%2003/wisc_bc_data.csv) 。这个数据集的 diagnosis 列为每一个记录的标签,有 B 和 M两个值,而其他列均是特征。下面我们来一步一步处理。

查看更多

评论

Numpy.tile() 函数的作用

一、文档

1
2
3
4
5
6
7
8
9
10
11
12
13
14
numpy.tile(A, reps):

Construct an array by repeating A the number of times given by reps.

If reps has length d, the result will have dimension of max(d, A.ndim).

If A.ndim < d, A is promoted to be d-dimensional by prepending new axes.
So a shape (3,) array is promoted to (1, 3) for 2-D replication, or shape (1, 1, 3) for 3-D replication.
If this is not the desired behavior, promote A to d-dimensions manually before calling this function.

If A.ndim > d, reps is promoted to A.ndim by pre-pending 1’s to it.
Thus for an A of shape (2, 3, 4, 5), a reps of (2, 2) is treated as (1, 1, 2, 2).

Note : Although tile may be used for broadcasting, it is strongly recommended to use numpy’s broadcasting operations and functions.

查看更多

评论

KNN 实践:识别手写数字

一、前言

先简单回顾一下 KNN 的原理:用距离目标最近的 k 个样本数据的分类来代表目标的分类。

查看更多

评论

高斯混合模型和EM算法

一、混合模型(Mixture Model)

混合模型是一个可以用来表示在总体分布(distribution)中含有 K 个子分布的概率模型。换句话说,混合模型表示了观测数据在总体中的概率分布,它是一个由 K 个子分布组成的混合分布。混合模型不要求观测数据提供关于子分布的信息,来计算观测数据在总体分布中的概率。

查看更多

评论

Bagging 和 随机森林(Random Forest,RF)

前面已经了解到集成学习有两个流派,一个是 Boosting 派系,它的特点是各个弱学习器之间有依赖关系。另一种是 Bagging 流派,它的特点是各个弱学习器之间没有依赖关系,可以并行拟合。而随机森林又是对 Bagging 的一个改进算法,可以很方便的并行训练。

查看更多

评论

AdaBoost 简介【译】

原文:AdaBoost 简介

目前的集成学习(Ensemble Learning)方法大致可分为两类:一是个体学习器之间存在强依赖关系、必须串行生成的序列化方法,代表算法是Boosting;二是个体学习器之间不存在强依赖关系,可同时生成的并行方法,代表算法是 Bagging 和 “随机森林(Random Forest)”。

首先要知道 AdaBoost(adaptive boosting) 算法Boosting算法族中的一员。Boosting算法可将弱学习器提升为强学习器。所谓的弱学习器就是泛化性能略高于随机猜测的学习器,而强学习器很显然就是指泛化能力较高的学习器了。Boosting算法原理图:

Boosting

AdaBoost算法中有一个很重要的环节。每一个训练样本都被赋予权值,并且随着训练过程样本权值不断更新。更新的原则是:误分类样本被赋予更高的权值,而正确分类样本的权值被相应降低。通过这种方式能够将重点放在不能正确分类的样本上,新选出来的分类器能够发挥原有分类器没有的作用,提高整体的分类效果。

查看更多

评论

模型评估与选择

一、经验误差与过拟合

  1. 错误率(error rate):分类错误的样本数占样本总数的比例,E = a/m
  2. 精度(accuracy):精度 = 1 一 错误率
  3. 误差(error):学习器的实际预测输出与样本的真实输出之间的差异
  4. 经验误差(empirical error):学习器在训练集上的误差,也叫训练误差(training error)
  5. 泛化误差(generalization error):学习器在新样本上的误差
  6. 过拟合(overfitting):当学习器把训练样本学得”太好”了的时候,很可能巳经把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质,这样就会导致泛化性能下降。这种现象称为过拟合。其中最常见的情况是由于学习能力过于强大,以至于把训练样本所包含的不太一般的特性都学到了。过拟合为什么无法避免?机器学习面临的问题通常是NP 难甚至更难,而有效的学习算法必然是在多项式时间内运行完成,若可彻底避免过拟合, 则通过经验误差最小化就能获最优解,这就意味着我们构造性地证明了 “P=NP” ;因此只要相信”P≠NP “ ,过拟合就不可避免P。
  7. 欠拟合(underfitting):是指对训练样本的一般性质尚未学好。通常是由于学习能力低下而造成的。

查看更多

评论

SVM 简介【译】

原文:An introduction to Support Vector Machines (SVM)

如果你在处理文本分类问题,为了提炼数据,可能已经尝试过朴素贝叶斯(Naive Bayes)分类算法。如果你的数据集还算正常的话,并且想要一步到位表现更好的话,可以考虑使用 SVM。SVM 是一个在有限数据集上十分快速且靠谱的分类算法。

查看更多

评论

大数定理随笔

在数学与统计学中,大数定律又称大数法则、大数律,是描述相当多次数重复实验的结果的定律。根据这个定律知道,样本数量越多,则其平均就越趋近期望值。

查看更多

评论

支持向量机 SVM:详解非线性SVM

一、非线性SVM

二、SMO(Sequential Minimal Optimizaion)算法

三、异常值的处理-松弛变量的引入


参考:

  1. Python3《机器学习实战》学习笔记(八):支持向量机原理篇之手撕线性SVM

  2. 支持向量机的原理和实现

  3. 机器学习与数据挖掘-支持向量机(SVM)

  4. 支持向量机(SVM)是什么意思?

  5. 支持向量机通俗导论(理解SVM的三层境界)

  6. Support Vector Machines
    

  7. 零基础学SVM—Support Vector Machine(一)

THE END.

评论

ARTS ISSUE#002

  • Algorithm : Binary Tree Inorder
  • Review : [点评一篇英文技术文章]
  • Tip : [学习一个技术技巧]
  • Share : [分享一个技术观点和思考]

THE END.

评论

Binary Tree Zigzag Level Order Traversal

The more we do,the more we can do.

查看更多

评论

ARTS ISSUE#001


THE END.

评论

Binary Tree Inorder

You cannot find peace by avoiding life.

查看更多

评论

Git Commit Message Format

Never leave todays’s work tomorrow.

查看更多

评论

Want to Improve Your Memory?

来源 : Want to Improve Your Memory? Science Tells Us the Key (and It Can Actually Be Fun)

The key to improving your memory is surprise.

Somehow, the novelty of surprise creates a halo of better memory for all the otherwise trivial events of one’s day that we ordinarily forget.”

  • Distract yourself.
  • Celebrate quick wins.
  • Take regular body breaks.
  • Take the opportunity to try something new.

THE END.

评论

支持向量机 SVM:SVM简介

支持向量机(support vector machine),一般简称SVM,通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

SVM 原理分为软间隔最大化、拉格朗日对偶、最优化问题求解、核函数、序列最小优化 SMO 等部分。

查看更多

评论