兼一书虫

树结构概念

排序算法 十大经典排序算法_动图演示 常见的10种排序算法 十大经典排序算法动画，看我就够了 十大经典排序算法 分类十种常见排序算法可以分为两大类： 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(n)$，因此也称为非线性时间比较类排序 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序 排序算法 比较类 交换排序 冒泡排序(稳定) 快速排序[分治] 插入排序 简单插入排序(稳定)[打扑克] 希尔排序(插入排序的改进) 选择排序 简单选择排序[选最值] 堆排序 归并排序(稳定)[递归] 二路归并排序 多路归并排序 非比较类 计数排序(稳定) 桶排序(稳定) 基数排序(稳定) 算法复杂度 排序方法 时间复杂度(均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 本地排序 插入排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定 都可 希尔排序 $O(n^{1.3})$ $O(n^2)$ ...

写在前面，本系列主要是对下面这本书做的学习笔记 常用数学符号的 LaTeX 表示方法 Markdown 常用数学符号和公式 基本概念 前言 最优化方法在机器学习领域处于中心地位，绝大多数算法最后都归结于求解最优化问题，从而确定模型参数，或直接获得预测结果 有监督学习，通过最小化损失函数或优化其他类型的目标函数确定模型的参数 数据降维算法，通过优化某种目标函数，确定降维后的结果，如主成分分析 按照优化变量的类型，可以将优化问题分为连续型优化问题与离散型优化问题 连续型优化问题的优化变量是连续变量，一般可借助导数求解 离散型优化问题的优化变量则为离散值 连续型优化问题又可分为凸优化问题与非凸优化问题，凸优化问题可以保证求得全局最优解 按照目标函数的数量 单目标优化：只有一个目标函数, 多目标优化：有多个目标函数 按照是否带有约束条件 不带约束的优化 带约束的优化 按照求解方式可分为 数值优化：求问题的近似解 解析解：求精确的公式解 基于概率的优化算法是优化算法家族中一种特殊的存在，典型的是遗传算法与贝叶斯优化 通常情况下最优化问题是求函数的极值，其优化变量是整 ...

学派对概率的诠释有两大学派，一种是频率派另一种是贝叶斯派，后面我们对观测集采用下面记号： X_{N\times p}=(x_{1},x_{2},\cdots,x_{N})^{T},x_{i}=(x_{i1},x_{i2},\cdots,x_{ip})^{T}$X$这个矩阵展开如下 X=\left(\begin{array}{cccc}x_{11} & x_{12} & \cdots & x_{1 p} \\ x_{21} & x_{22} & \cdots & x_{2 p} \\ \vdots & & & \\ x_{N 1} & x_{N 22} & \cdots & x_{N p}\end{array}\right)_{N \times p}表示有$N$个样本，每个样本都是$p$维向量，其中假设每个观测都是由 $p(x|\theta)$生成的 频率派频率派认为$p(x|\theta)$中的$\theta$是一个未知的常量，而数据是一个随机变量，关心的是数据，目标是估计未知的常量$\theta$ 常用的方法是最大似然估计 \theta_{MLE}=\mathop{argm ...

写在前面，本系列主要是对下面这本书做的学习笔记 常用数学符号的 LaTeX 表示方法 Markdown 常用数学符号和公式 随机事件与概率概率论同样在机器学习和深度学习中有至关重要的作用。如果将机器学习算法的输入数据和输出数据看作随机变量，则可用概率论的方法对数据进行计算，以此对不确定性进行建模 使用概率模型，可以输出概率值而非确定性的值，这对某些应用是至关重要的 对于某些应用问题，需要对变量之间的概率依赖关系进行建模，也需要概率论的技术，概率图模型是典型代表 随机数生成算法，即采样算法，需要以概率论作为理论指导 某些随机算法，如蒙特卡洛算法、遗传算法，同样需要以概率论作为理论或实现依据。 随机事件和概率是概率论中基本的概念，也是理解随机变量的基础 随机事件概率随机事件是可能发生也可能不发生的事件，这种事件每次出现的结果具有不确定性 例如，天气可能是晴天、雨天、阴天；考试分数可能为0与100之间的整数；掷骰子，1到6这几种点数都可能出现 以集合论作为工具，给出随机事件的定义 对于一个随机试验，其所有可能结果组成的集合称为样本空间记为$\Omega$ 随机试验可能的结果 ...

隐马尔可夫HMM定义 一站式解决：隐马尔可夫模型（HMM）全过程推导及实现 关于HMM、MEMM、CRF的一些知识整理整理 图解隐马尔可夫模型HMM_通俗易懂 隐马尔可夫模型(hidden Markov model, HMM)是可用于标注问题的统计学习模型 描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型 隐藏的马尔可夫链随机生成的状态的序列，称为状态序列(state sequence)每个状态生成一个观测 而由此产生的观测的随机序列，称为观测序列(observation sequence) 序列的每一个位置又可以看作是一个时刻 这里的$Z$就是状态序列，$x$是观测序列，设Q是所有可能的状态的集合，V是所有可能的观测的集合，$N$是可能的状态数，$M$是可能的观测数 Q = \{q_1,q_2, \cdots ,q_N \} \qquad V = \{v_1,v_2, \cdots ,v_M \}三要素 隐马尔可夫三要素 隐马尔可夫模型由初始状态概率$\pi$、状态转移矩阵$A$、观测概率矩阵(或者叫发射矩阵)$B$决定，记作 \lambda = (\pi, A ...

前置知识 笔记整理自：Bilibili站上shuhuai008强势手推讲解的白板推导CRF系列课程，课程质量很高！ 条件随机场 【NLP】从隐马尔科夫到条件随机场 分类问题根据输出的类型，可以将其划分为硬模型和软模型 硬输出: 输出为0或1 软输出: 引入概率，不直接计算边界，而是计算取各类别的概率 软硬模型硬模型 svm支持向量机(最大间隔) 几何角度出发，求的是max margin classifier，式子最终的形式为 min (\frac {1}{2} w^Tw) \qquad s.t. \ y_i(w^Tx_i+b) \geq1,i=1,\cdots,N PLA感知机，可以看作最基本的神经元 f(w) = sign(w^Tx) LDA线性判别分析(误分类驱动) 核心思想: 类间大、类内小 软模型概率判别模型 建模核心 是对P(x,y)进行建模 例子_逻辑回归(Logistics Regression, LR)，或者也可以叫SoftMax Regression 例子_最大熵模型(Maximum Entropy Model, MEM) 利用最大熵思想( ...

贪心算法概念案例

动态规划概念动态规划(英语：Dynamic programming，简称 DP)，是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法 动态规划常常适用于有重叠子问题和最优子结构性质的问题 适用情况 动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题 最优子结构: 如果某条路径是起点到终点的最短路径，则起点到该路径上的每一点都是最短路径，一个最优化策略的子策略总是最优的，最优化原理是动态规划的基础 无后效性: 当前选择任何一条边都不会影响以后选择其他边，如果当前选择会影响后面的选择则不适用，每个状态都是过去历史的一个完整总结 动态规划解题的步骤 找出最优子结构 写出动态规划方程 使用自底向上或者自顶向下的方法求解 逆推求解 小结 动态规划的适用条件任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用 同样,动态规划也并不是万能的，适用动态规划的问题必须满足最优化原理和无后效性 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存 ...

递推和递归概念 递归: 从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题，是逆向的 递推: 是从简单问题出发，一步步的向前发展，最终求得问题。是正向的 一般来说，递推的效率高于递归(当然是递推可以计算的情况下)，比如：斐波那契数列 a_{n} = \frac {1}{\sqrt{5} [ (\frac {1+\sqrt{5}}{2})^n - (\frac {1-\sqrt{5}}{2})^n ]}案例递归实现指数型枚举题目 描述 从 $1∼n$ 这 $n$ 个整数中随机选取任意多个，输出所有可能的选择方案 难度 简单 输入格式 输入一个整数 $n$ 输出格式 每行输出一种方案 同一行内的数必须升序排列，相邻两个数用恰好 $1$ 个空格隔开。 对于没有选任何数的方案，输出空行 本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意 数据范围 1 \leq n \leq 15 输入样例 13 输出样例 1234567322 311 31 21 2 3 求解 递归方式 1234567891011n = input()def dfs(u, ...