- 博客(95)
- 收藏
- 关注
RSS订阅原创 非均匀分布的采样
#include<bits/stdc++.h>using namespace std;int main(){ default_random_engine e(time(0)); uniform_real_distribution<float> u(0,1); float sum_weights[5]={0.1, 0.5, 0.7, 1.2, 1.5}; ...
2019-07-06 22:17:57
2853
原创 八皇后
参考链接：https://www.jianshu.com/p/65c8c60b83b8八皇后问题的主要思想是使用回溯法。我们已经知道，八个皇后分别在每一行， 而所在的列是需要我们用递归来进行寻找的。#include<bits/stdc++.h>using namespace std;bool isOk(vector<vector<int>>& f...
2019-06-29 23:18:48
331
原创 求不相邻的最大子数组和
参考： https://blog.csdn.net/realxie/article/details/8063885题目：给定一个数组A，求出一些数，使得每个元素在数组A里两两不相邻，并且和最大。选择第i个元素，那么第i-1个元素一定不能选不选择第i个元素，那么第二个元素既可以选，也可以不选#include<bits/stdc++.h>using namespace st...
2019-06-20 21:59:48
1140
原创 用一个栈实现另一个栈的排序
参考 https://www.cnblogs.com/xiyuan2016/p/6830821.html题目：在一个栈中元素的类型为整型，现在想将该栈从栈顶到栈底按从大到小的顺序排序，只许申请一个栈，除此之外，可以申请其他变量，但是不能申请额外的数据结构 。思路：待排序的栈stack， 辅助栈help。 Note: 为使得 stack 栈顶到栈底元素降序，help保持 栈顶到栈底元素升序，...
2019-06-14 11:53:37
396
原创 Trapping Rain Water(leetcode hard)
这是自己在面试微软过程中遇到的编程题，印象比较深刻是因为当时自己尝试想了很多方法都是不对的。果然，这就是hard题目的魅力。思想：考虑在每一个位置，它可以存多少水。这取决于它左边最高的板子，它右边最高的板子，这两者的最小值高于当前位置多少。下面的代码里，forward和backward分别记录的是包括当前位置的板子的最高值。仔细想了下，是否包括当前位置，都是OK的。class Solutio...
2019-04-30 20:55:27
166
原创 为什么分类问题使用交叉熵损失函数？
待整理…[1] http://www.cnblogs.com/aijianiula/p/9460842.html[2] https://blog.csdn.net/yangyang688/article/details/82667273
2019-04-17 16:34:20
3780
原创 注意力模型
好记性不如烂笔头，现在整理一下attention model的各种类型。什么是attention一句话来说，attention是一个加权求和，重点是如何计算权重。我们有一个query向量（包含比较多信息的全局向量），一段key向量，利用query对所有key进行加权求和。背景在nlp领域，首先将attention用于机器翻译，显然，在进行翻译的时候，会关注不同的原文信息。具体来说，在机器...
2019-03-03 17:58:23
1426
原创 Regularization
概述L1和L2正则项本质上是对参数进行先验分布假设，具体来说L1对应拉普拉斯先验，L2对应高斯先验。ML与MAP的不同maximum likelihood (ML) 极大似然估计:MAP (maximum a posterior) 最大后验概率估计:即p(θ)p(\theta)p(θ)进行了先验假设。拉普拉斯分布L1正则化对应假设每个参数服从均值为0的拉普拉斯分布。b越小，越...
2019-02-25 22:23:37
471
原创 特征选择
特征选择和降维，它们是处理高维数据的两大主流技术。维数灾难问题大为减轻往往会降低学习任务的难度在特征选择中，涉及两个关键环节：1）如何获取特征子集 2）如何评价特征子集的好坏我们不可能遍历所有的特征子集，因此使用的是基于贪心的策略。搜索子集有三种方法：前向搜索，后向搜索，双向搜索。在子集评价问题中，可以使用信息增益作为评价准则。将特征子集搜索机制与子集评价机制相结合，即可得...
2019-02-24 22:05:18
1040
原创 机器学习中防止过拟合的方法
过拟合主要由两个原因造成：数据太少、模型太复杂获取更多的数据(1) 从数据源头获取更多的数据(2) 数据增强(3) 根据当前数据集估计数据分布参数，使用该分布产生更多数据：一般不采用此方法，因为估计分布参数的过程会引入误差对于神经网络而言，可以减少网络的层数、神经元的个数Early StoppingL1或L2正则化项Dropout...
2019-02-23 10:55:07
338
原创 激活函数从Sigmoid到各种Relu
在神经网络中，我们使用非线性激活函数，如果采用的是线性激活函数，则还是等价于上一步进行的线性变化，网络再深，也和一层是等价的。 - sigmoid: 11+e−x11+e−x\frac{1}{1+e^{-x}} - tanh: ex−e−xex+e−xex−e−xex+e−x\frac{e^x-e^{-x}}{e^x+e^{-x}} - relu: max(0,x)max(0,x)...
2019-02-11 22:11:35
2077
原创 Dropout与DropConnect
为了防止模型过拟合，dropout是一种trick，之前提到Batch Normalization的使用可以不必再使用dropout，但是我们还是有必要温习下什么是dropout。Dropoutdropout在全连接层使用。在训练阶段，对于每个节点，以p概率将其输出值保留，以1-p概率将其输出值乘以0。在测试阶段，输出结果要乘以p。原因是：保持训练阶段和测试阶段的期望值相同。训练阶段，对于每个...
2019-02-02 20:28:47
3283
2
原创 不止Batch Normalization
这次想总结一下神经网络中的各种normalization。Batch NormalizationLayer NormalizationInstance NormalizationGroup NormalizationBN为什么提出BN? 深度神经网络随着网络深度的加深，训练起来越来越困难，收敛越来越慢。我们看一下论文题目：《Batch Normalization: Acceler...
2019-01-29 20:51:25
199
原创 翻转字符串系列
leetcode 541. Reverse String II关键在于理清各种情况class Solution {public: string reverseStr(string s, int k) { int n = s.length(); int cnt=0; for(int i=0;i<n;i++){ ...
2019-01-13 15:37:09
162
原创 二叉树路径题目
leetcode 112 路径总和Ileetcode 113 路径总和IIleetcode 437 路径总和 IIIleetcode 257
2019-01-12 17:11:09
210
原创 查找
顺序查找法逐个进行比较。时间复杂度O(n)O(n)O(n)。二分查找使用的前提是：数据连续存储且有序。时间复杂度O(logn)O(logn)O(logn)。https://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?tpId=49&amp;&amp;tqId=29278&amp;rp=1&amp;ru=/activi...
2019-01-10 14:13:03
183
原创 桶排序
n个数，m个桶，时间复杂度是O(n+m∗nmlog(nm))=O(n+n(logn−logm))O(n+m*\frac{n}{m}log(\frac{n}{m}))=O(n+n(logn-logm))O(n+m∗mnlog(mn))=O(n+n(logn−logm))，最好的时间复杂度是O(n)O(n)O(n)。桶排序是牺牲空间换时间。题目：给你几万名员工的年龄数据，让你对这些年龄从小到大...
2019-01-09 16:45:56
174
原创 二叉搜索树和平衡二叉树
二叉搜索树定义：对任意节点而言，其左子树（如果存在）所有的节点值均小于该节点的值，其右子树（如果存在）所有的节点值均大于该节点的值。特点：中序遍历二叉搜索树得到的结果递增。查找插入需要明确的一点是：插入的新节点一定成为叶子节点。引入一个prev指针变量。删除这里节点的删除分为三种情况：1） 该节点没有子树2）该节点只有一颗子树3）该节点有两颗子树，有两种解决办法：合...
2019-01-09 11:20:03
416
原创 各种排序算法及其C++代码实现
概念一：排序算法是否是稳定的给定序列{3,15,8,8,6,9}若排序后得到{3,6,8,8,9,15}, 则该排序算法是不稳定的，原本后面的8（加粗）现在位于前面了。概念二： 内部排序、外部排序内部排序是指将待排序的数据存放在内存中进行排序的过程。外部排序是指待排序的数据很多，以致内存一次不能容纳所有数据，在排序过程中需要对外存进行访问的排序过程。概念三：评价标准排序过程中最基本的...
2019-01-08 20:29:27
2842
原创 回文的系列题目
一、判断一个字符串是不是回文串题目链接https://www.nowcoder.com/practice/df00c27320b24278b9c25f6bb1e2f3b8?tpId=69&amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;tqId=29674&amp;amp;amp;amp;amp;amp;rp=1&amp;amp;amp;amp;amp;amp;ru=/activity/oj&
2019-01-04 17:32:44
476
原创 有趣的数字
题目链接https://www.nowcoder.com/questionTerminal/af709ab9ca57430886632022e543d4c6考虑不到的点是 当出现重复数字的时候，差值最大和最下的对数计算问题。#include &amp;lt;iostream&amp;gt;#include &amp;lt;algorithm&amp;gt;using namespace std;int main(){...
2019-01-04 11:41:54
934
原创 字符移位
https://www.nowcoder.com/question/next?pid=1725829&qid=44802&tid=20692948题目：小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。冒泡思想#include <iostream>using namespace std;int ma...
2019-01-04 09:34:04
175
原创 最长公共子序列
不同于子串，子序列是不连续的。这时无法暴力穷举。https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a动态规划法：class LCS {public: int findLCS(string A, int n, string B, int m) { vector&amp;lt;vec...
2019-01-03 20:42:09
212
原创 最长公共子串
最长公共子串https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602暴力法：class LongestSubstring {public: int findLongest(string A, int n, string B, int m) { int res = 0; ...
2019-01-03 19:22:42
216
原创 K-Means
K-Means是无监督的聚类算法。传统K-Means算法的两个大的缺点：1） 必须事先给定K值，这个K值的选定是非常难以估计的2) 确定好K值后，需要随机初始化K个不同的中心，因此不同的初始化会得到完全不同的结果初始化优化K-Means++上面我们提到，K个初始化质心的位置选择对最后的聚类结果和运行时间都有很大的影响。K-Means++算法就是对传统K-Means随机初始化质心的方法...
2018-12-28 23:14:38
250
原创 熵、联合熵、条件熵、相对熵、交叉熵、互信息
[1] https://www.cnblogs.com/kyrieng/p/8694705.html熵H(X)=−∑xp(x)logp(x)H(X) = -\sum_xp(x)logp(x)H(X)=−∑xp(x)logp(x), 它表示的是随机变量XXX的不确定性，不确定性越大，熵越大。没有条件约束的时候，X是均匀分布，对应的熵最大。给定均值和方差的前提下，正态分布对应的熵最大。联合...
2018-12-28 10:57:53
803
原创 LightGBM
和XBGoost一样使用了二阶导数，LightGBM速度快，内存小，精度和XGBoost相当。使用直方图简化计算使用leaf-wise代替level-wise
2018-12-26 11:56:38
352
原创 AdaBoost与GBDT进行比较
AdaBoost: 加法模型，指数损失函数，使用前向分步算法求解模型参数。目标是使前向分步算法得到的αm\alpha_mαm和Gm(x)G_m(x)Gm(x)使fm(x)f_m(x)fm(x)在训练集上的指数损失最小。其中fm(x)=fm−1(x)+αmGm(x)f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)fm(x)=fm−1(x)+αmGm(x)。证明过程...
2018-12-24 08:50:39
1170
原创 提升树
定义：提升树是以分类树或回归树为基分类器的boosting方法。回归问题的提升树采用平方误差损失函数，是用当前模型去拟合数据的残差分类问题的提升树指数损失函数对于二分类问题，提升树只需将Adaboost里的基分类器限制为二类分类树即可。总结：提升树利用加法模型和前向分步算法实现学习的优化过程。当损失函数是指数损失函数（用于分类）和平方损失函数（用于回归）时，每一步的优化都是很简单...
2018-12-22 22:30:37
208
原创 随机森林用于特征选择
随机森林可以计算单个特征变量的重要性。计算特征X的重要性的方法：对RF中的每一棵决策树，计算出OOB数据的误差，记作errOOB1errOOB1errOOB1对所有OOB数据里的特征X加入噪声，然后计算OOB数据的误差，记作errOOB2errOOB2errOOB2RF有N棵树，则特征X的重要性为∑i(errOOB2i−errOOB1i)/N\sum_i (errOOB2_i-errOO...
2018-12-22 21:00:15
5394
原创 决策树(三)
决策树算法总结：优点决策树简单直观不需要归一化，不需要处理缺失值既可以处理离散特征，也可以处理连续特征不易受到异常值的影响缺点非常容易过拟合因样本的扰动，导致树结构剧烈改变寻找最优决策树是个NP难的问题，一般通过启发式方法...
2018-12-21 19:48:34
231
3
原创 决策树(二)
在决策树(一)中，我们介绍了三种不同的特征选择方式。ID3使用的是信息增益准则，C4.5使用的是信息增益率准则，CART在分类时使用的是基尼指数。ID3算法的不足没有考虑连续特征信息增益偏好取值数目较多的特征没有考虑缺失值没有考虑过拟合的问题C4.5对ID3中的四个问题进行了改进连续特征离散化：使用二分法对连续特征进行处理属性a在样本集D中有n个不同的值，将其从小到大排列...
2018-12-21 19:20:46
248
原创 决策树(一)
参考：《机器学习》周志华想对决策树做一个简单的回顾和总结，因为发现在Random Forest, GBDT和XGBoost中的基分类器中起到重要的作用。定义 一般的，一颗决策树包含一个根节点，若干个内部节点和若干个叶子节点；叶节点对应于决策结果，根节点和内部节点对应一个属性。 划分选择 决策树中关键的一步是：如何选择划分属性，即内部节点。我们希望落入叶子节点的样本尽可能地属...
2018-12-19 15:20:34
632
原创 PCA(Principal Component Analysis)
主成分分析是一种广泛使用的对数据进行降维的方法。在PCA 中，数据由原来的坐标系转换到了新的坐标系，新的坐标系的选择是由数据本身决定的。我们选择方差比较大的新坐标轴，从而对数据进行了降维。[讲述PCA比较好的文章链接](http://blog.codinglabs.org/articles/pca-tutorial.html)我们需要找到合适的基，也就是合适的新的坐标轴;然后将数据投影到该基上，
2018-12-10 21:03:23
284
原创 线性判别分析(LDA)
LDA是一种监督学习，通常作为数据预处理阶段的降维技术。监督降维方法！！！LDA降维的步骤：计算每个类别样本的均值向量，所有样本的均值向量通过均值向量，计算类间散度矩阵SBS_BSB和类内散度矩阵SWS_WSW对SW−1SBW=λWS_W^{-1}S_BW=\lambda WSW−1SBW=λW进行特征值求解，选择前K个特征向量组成WWW，其中K最大为N-1(N是类别数)新的子...
2018-12-10 18:28:23
562
原创 生成学习算法
生成学习算法：对p(x,y)p(x,y)p(x,y)进行建模，具体是p(y)p(y)p(y)和p(x∣y)p(x|y)p(x∣y)预测的时候，利用贝叶斯公式：高斯判别分析特点： input features x是连续的使用多变量高斯分布对p(x∣y)p(x|y)p(x∣y)进行建模具体来说：可以看到，两个多变量高斯分布的均值向量不同，但是协方差矩阵是一样的。然后对数据进行对数...
2018-12-10 10:09:33
182
原创 最大熵模型
logistic regression和最大熵模型都是对数线性模型，而对数线性模型属于广义线性模型。最大熵模型属于运用最大熵原理的多分类模型。我们要清楚两件事：什么是最大熵原理最大熵模型如何运用最大熵原理最大熵原理：在满足约束条件的模型集合中选择熵最大的模型。最大熵模型：给定训练集(x1,y1),(x2,y2),...,(xn,yn){(x_1,y_1),(x_2,y_2),.....
2018-12-09 00:00:14
277
原创 LR模型(logistic regression)
分类模型本质上是线性回归模型优化目标J(θ)=∑−yilog(h(θTxi))−(1−yi)log(1−h(θTxi))J(\theta) = \sum -y_ilog(h(\theta^Tx_i))-(1-y_i)log(1-h(\theta^Tx_i))J(θ)=∑−yilog(h(θTxi))−(1−yi)log(1−h(θTxi)),最小化其中h(θTx)=11+e−θ...
2018-12-07 11:28:05
2494
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人