算法手记-CSDN博客

原创开启算法手记

从今天开始，我将不断记录自己学习和复习算法（包括数据结构、机器学习、深度学习、NLP、推荐系统等）的过程，和大家一起进步。公众号：

2020-09-01 22:29:37 110 1

1、背景深度学习在CTR预估领域已经有了广泛的应用，常见的算法比如Wide&Deep，DeepFM等。这些方法一般的思路是：通过Embedding层，将高维离散特征转换为固定长度的连续特征，然后通过多个全联接层，最后通过一个sigmoid函数转化为0-1值，代表点击的概率。即Sparse Features -> Embedding Vector -> MLPs -> Sigmoid -> Output.这种方法的优点在于：通过神经网络可以拟合高阶的非线性关系，同时减少了人

2020-10-22 23:20:12 1162

原创《推荐系统》-AFM模型

1、引言在CTR预估中，为了解决稀疏特征的问题，学者们提出了FM模型来建模特征之间的交互关系。但是FM模型只能表达特征之间两两组合之间的关系，无法建模两个特征之间深层次的关系或者说多个特征之间的交互关系，因此学者们通过Deep Network来建模更高阶的特征之间的关系。因此 FM和深度网络DNN的结合也就成为了CTR预估问题中主流的方法。有关FM和DNN的结合有两种主流的方法，并行结构和串行结构。两种结构的理解以及实现如下表所示：图1、两种结构的理解今天介绍的NFM模型(Neural Factor

2020-10-22 23:07:28 281

原创《推荐系统》-NFM模型

1、引言在CTR预估中，为了解决稀疏特征的问题，学者们提出了FM模型来建模特征之间的交互关系。但是FM模型只能表达特征之间两两组合之间的关系，无法建模两个特征之间深层次的关系或者说多个特征之间的交互关系，因此学者们通过Deep Network来建模更高阶的特征之间的关系。因此 FM和深度网络DNN的结合也就成为了CTR预估问题中主流的方法。有关FM和DNN的结合有两种主流的方法，并行结构和串行结构。两种结构的理解以及实现如下表所示：图1、两种结构的理解今天介绍的NFM模型(Neural Factor

2020-10-22 00:05:50 357

原创《推荐系统》-PNN模型

1、原理PNN，全称为Product-based Neural Network，认为在embedding输入到MLP之后学习的交叉特征表达并不充分，提出了一种product layer的思想，既基于乘法的运算来体现体征交叉的DNN网络结构，如下图：图1、Product-based Neural Network Architecture按照论文的思路，我们也从上往下来看这个网络结构：输出层输出层很简单，将上一层的网络输出通过一个全链接层，经过sigmoid函数转换后映射到(0,1)的区间中，得到我

2020-10-21 23:59:00 1284

原创《推荐系统》-Deep&Cross Network模型

1、原理Deep&Cross Network模型我们下面将简称DCN模型：一个DCN模型从嵌入和堆积层开始，接着是一个交叉网络和一个与之平行的深度网络，之后是最后的组合层，它结合了两个网络的输出。完整的网络模型如图：图1、the Deep & Cross Network嵌入和堆叠层我们考虑具有离散和连续特征的输入数据。在网络规模推荐系统中，如CTR预测，输入主要是分类特征，如“country=usa”。这些特征通常是编码为独热向量如“[ 0,1,0 ]”；然而，这往往导致过度的高

2020-10-21 23:37:38 321

原创《推荐系统》-DeepFM模型

1、背景对于一个基于CTR预估的推荐系统，最重要的是学习到用户点击行为背后隐含的特征组合。在不同的推荐场景中，低阶组合特征或者高阶组合特征可能都会对最终的CTR产生影响。之前介绍的因子分解机(Factorization Machines, FM)通过对于每一维特征的隐变量内积来提取特征组合。最终的结果也非常好。但是，虽然理论上来讲FM可以对高阶特征组合进行建模，但实际上因为计算复杂度的原因一般都只用到了二阶特征组合。那么对于高阶的特征组合来说，我们很自然的想法，通过多层的神经网络即DNN去解决。DNN

2020-10-20 23:43:29 285

原创《推荐系统》-FFM模型

1、FFM理论在CTR预估中，经常会遇到one-hot类型的变量，one-hot类型变量会导致严重的数据特征稀疏的情况，为了解决这一问题，在上一讲中，我们介绍了FM算法。这一讲我们介绍一种在FM基础上发展出来的算法-FFM（Field-aware Factorization Machine）。FFM模型中引入了类别的概念，即field。还是拿上一讲中的数据来讲，先看下图：图1、点击数据在上面的广告点击案例中，“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”这三个特

2020-10-20 22:32:24 463

原创《推荐系统》-FM模型

1、背景在计算广告和推荐系统中，CTR预估(click-through rate)是非常重要的一个环节，判断一个商品的是否进行推荐需要根据CTR预估的点击率来进行。在进行CTR预估时，除了单特征外，往往要对特征进行组合。对于特征组合来说，业界常用的方法有人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree） + LR、FM（Factorization Machine）和FFM（Field-aware Factorizat

2020-10-20 00:55:12 614

原创《推荐系统》-Wide&Deep

1、背景Wide and deep 模型是 TensorFlow 在 2016 年 6 月左右发布的一类用于分类和回归的模型，并应用到了 Google Play 的应用推荐中。wide and deep 模型的核心思想是结合线性模型的记忆能力（memorization）和 DNN 模型的泛化能力（generalization），在训练过程中同时优化 2 个模型的参数，从而达到整体模型的预测能力最优。记忆（memorization）即从历史数据中发现item或者特征之间的相关性。泛化（generaliz

2020-10-20 00:28:33 259

转载《算法》-字符串[数据压缩]

1、为什么要做数据压缩？数据压缩的主要目的还是减少数据传输或者转移过程中的数据量。2、什么是数据压缩？是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高传输、存储和处理效率的一种技术方法。或者是按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。3、常见的数据压缩算法LZW压缩LZW压缩是一种无损压缩，应用于gif图片。适用于数据中存在大量重固子串的情况。原理：LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个

2020-09-17 22:49:33 1615

转载《算法》-字符串[正则表达式]

正则表达式(Regular Expression)是一种文本模式，包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为"元字符"）。正则表达式描述了一种字符串匹配的模式（pattern），可以用来检查一个字符串是否含有满足该pattern的子串，正则表达式典型应用如下图：常见的表示前面的符号重复0或多次，比如AB表示的字符串由一个A和0个或多个B组成。|表示或操作，如AB|CD,可以表示字符串AB或者CD()可以改变默认的优先级，举例如下：每个正则表达式都对应一个非确定有限状态自动机

2020-09-16 21:58:42 146

转载《算法》-字符串[子字符串查找]

字符串的一种基本操作就是子字符串查找。比如在文本编辑器或是浏览器中查找某个单词时，就是在查找子字符串。子字符串的长度（可能为100或1000）相对于整个文本的长度（可能为100万甚至是10亿）来说一般是很短的，在如此多的字符中找到匹配的模式是一个很大的挑战，为此计算机科学家们发明了多种有趣、经典且高效的算法。暴力子字符串查找算法要解决这个问题，首先想到的是暴力查找的方法，在文本中模式可能出现匹配的任何地方检查是否匹配。隐式回退首先是隐式回退的实现方式，之所以叫隐式回退，在与显式回退的实现对比后就明白

2020-09-15 22:15:14 485

转载《算法》-字符串[单词查找树]

查找所需要的单词的时间和键的长度成正比查找未命中只需检查若干个单词单词查找树单词查找树API基本性质每个链接对应一个字符每个结点可能有一个值有值，说明存在从根结点到这个结点的字符串。没有值，说明不存在从根结点到这个结点的字符串。没有对应的键值。它的存在是为了简化查询。查找命中：对应结点有值（注意不单单是指向该对应结点d链接存在，并且该结点一定要有值！）未命中：没有值 or 链接为空结点的表示每个结点下面有R个链接，一个链接对应一个字符键隐式..

2020-09-14 23:04:37 188

转载《算法》-字符串[字符串排序]

引入字符串方便比较吗？不方便怎么办呢？把每一个字符对应成一个数字 toIndex(c)一共有多少个字符？ R个数字R需要几个二进制位来表示？ lgR个如扩展ASCII码共256个字符，需要8位二进数来表示。区别Alphabet.toChar(index) 把数字对应成字符。这个是字母表的第i位String.charAt(index) 字符串的第i位是什么字符。这个是字符串的第i位。字符表API标准字符表键索引计数输入字符串和字符串对应的组别（组别也是

2020-09-14 01:17:28 241

转载《算法》-图[最短路径]

最短路径地图或者导航系统是最短路径的典型应用，其中顶点对应交叉路口，边对应公路，边的权重对应经过一段路的成本（时间或距离）。在这个模型中，问题可以被归纳为：找出从一个顶点到达另一个顶点的成本最小的路径。此外，网络路由、任务调度等也属于同类问题。加权有向图加权有向图是研究最短路径问题的模型。在加权有向图中，每条有向边都有一个与之关联的权重，路径的权重指路径上所有边的权重之和，所以在加权有向图中，求顶点v到w的最短路径问题就成了求顶点v到w的所有路径中权重最小者。数据结构加权有向边加权有向边是构成加

2020-09-13 12:54:04 298

转载《算法》-图[最小生成树]

最小生成树简单理解在前面我们了解到了无向图和加权有向图，类似的我们给无向图的每一条边加上权重，就得到了加权无向图最小生成树：图的生成树是它的一棵含有所有顶点的无环连通子图。加权图的最小生成树（MST）是它的一棵权值之和最小的生成树最小生成树算法有很多应用，比如顶点是城市，边是城市之间的航线，那么最小生成树可以看作覆盖这些城市做需要的最短总航线。下面我们先来看基本的实现原理。贪心算法首先我们先来介绍一个概念切分：切分就是将图的所有顶点分为两个非空且不重叠的两个集合，横切边是一条连接两个属于不同

2020-09-12 02:37:05 192

转载《算法》-图[有向图]

有向图简单的来说有向图就是连接带方向的图。有向图的例子在现实生活中也很多，比如在一段时间内银行间的现金流动，或者在某些地方的一些道路是单向的啊，那么这些现金流以及单向的道路就要用带方向的边来描述，这时有向图就有了用武之地。一个有向图的例子如下：有向图该怎么实现呢？，对于无向图我们使用邻接表来实现，这种表达方式非常高效，并且略加思考就可以发现，邻接表完全可以直接套用在有向图上。假设要添加一条v->w的边，只要每次调用add()函数的时候只在adj[v]所指向的Bag添加w即可，这么看来无向图可以看

2020-09-10 23:53:51 773

转载《算法》-图[无向图]

四种重要的图模型：无向图（简单连接）有向图（连接有方向性）加权图（连接带有权值）加权有向图（连接既有方向性又带有权值）无向图定义：由一组顶点和一组能够将两个顶点相连的边组成。特殊：自环（一条连接一个顶点和其自身的边）；平行边（连接同一对顶点的两条边）数学家将含有平行边的图称为多重图；将没有平行边或自环的图称为简单图。现实当中，两点就可以指代一条边。术语表两个顶点通过一条边相连，称这两顶点相邻，并称该连接依附于这两个顶点。某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所

2020-09-09 23:14:33 562

转载《算法》-查找[散列表]

散列表也是一种符号表，主要特征是可以将键通过散列函数映射为一个数组索引，然后利用这个数组索引就可以做很多东西。散列函数当我们输入一个对象，不论这是个什么东西，经过散列函数处理之后输出一个0到M-1的范围之内的整数。对于散列函数有一些要求：相等的对象（使用equals()函数）的散列值是相同的2.同样的散列值不同的两个对象不相等3.在输出范围之内尽量均匀分布下面介绍两种实现散列表的方式，分别基于拉链发和线性探测法。基于拉链法的散列表(SeparateChaining)假设键的数目为N，

2020-09-09 00:38:42 144

转载《算法》-查找[平衡查找树]

平衡树平衡树是一类改进的二叉查找树。一般的二又查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均推复杂度会上升，为了更高效查询，平衡树应运而生了。在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均复杂度偏低2-3查找树2-3 查找树是一种能够在动态插入当中保持完美平衡的数据结构，完美平衡即树中的所有空链接到根节点的距离都是相同的。在一棵大小为 N 的 2-3 树中，查找和插入操作访问的结点必然不超过logN个，为了保证查找树的平衡性，我

2020-09-08 01:37:00 251

m0_37748303的博客