EDA

探索性数据分析 EDA（Exploratory Data Analysis）是数据分析和挖掘的第一步，主要是对数据集进行了解，包括基本情况、特征情况、特征间关系等等，为进一步的分析和挖掘提供信息。

一个完整的 EDA 过程一般大致包括四步：

问题定义：问题定义涉及的主要任务是定义分析的主要目标，定义主要的可交付成果，概述主要角色和职责，获取数据的当前状态，定义时间表以及执行成本/收益分析。
数据准备：包括数据源定义、数据 schema 定义、数据特征了解、数据清理、数据转换、数据分割等。
数据分析：这是处理描述性统计信息和数据分析的最关键步骤之一。主要任务包括汇总数据，发现数据之间隐藏的关联和关系，开发预测模型，评估模型以及计算精度。
结果展示：以图表、摘要、地图和图表的形式将数据集呈现给目标受众。

Metrics

机器学习的数据集一般被划分为训练集和测试集，训练集用于训练模型，测试集则用于评估模型。针对不同的机器学习问题（分类、排序、回归、序列预测等），评估指标的选择也有所不同。本文主要介绍机器学习中常用的模型评估指标。

PEGASUS 论文笔记

Paper：[1912.08777] PEGASUS: Pre-training with Extracted Gap-sentences for Abstractive Summarization

Code：google-research/pegasus

核心思想：基于 GSG 的 Transformer 在文本摘要上的应用。

核方法和 SMO

上一部分介绍了硬间隔和软间隔支持向量机，本部分介绍非线性支持向量机（核方法）和序列最小最优化算法。

Find First and Last Position of Element in Sorted Array (LeetCode 34)

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1 2	Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

1 2	Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Constraints:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is a non decreasing array.
-10^9 <= target <= 10^9

Search in Rotated Sorted Array (LeetCode 33, 81, 153)

Given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You should search for target in nums and if you found return its index, otherwise return -1.

Example 1:

1 2	Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

1 2	Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Example 3:

1 2	Input: nums = [1], target = 0 Output: -1

Constraints:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is guranteed to be rotated at some pivot.
-10^4 <= target <= 10^4

Swap Nodes in Paris (LeetCode 24)

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

1	Given 1->2->3->4, you should return the list as 2->1->4->3.

Hard-SVM, Soft-SVM 和 KKT

SVM 是机器学习在神经网络兴起前最经典、有效的算法。它的思想主要是用一个超平面对数据集进行划分，但是能够分开数据集的超平面一般都有无数个，支持向量机的做法是 “间隔最大化”，也就是选择 “支持向量” 到分割平面距离之和最大的，进而将问题转换为一个凸优化问题。

支持向量机根据数据集可分程度的不同分为：

线性可分支持向量机：数据线性可分，硬间隔支持向量机
线性（不可分）支持向量机：数据近似线性可分，软间隔支持向量机
非线性支持向量机：数据线性不可分，核技巧 + 软间隔最大化

SVM 是一套完整的数据处理算法，核方法的引入使得它具有了对非线性数据的处理能力。具体的方式是将低维数据映射到高维，这样原来不可分的数据自然就可分了。比如假设两类数据点完全是均匀随机分布的，此时如果在平面内无论使用直线还是曲线都无法将它们分开，但假设我们有能力让某一类数据点全部脱离二维进入三维（此处可以想象桌子上散乱着小米和钢珠，你猛地用双手拍桌子，小米会跳起来进入第三维），那它们之间任意的平面都可以轻易将它们隔开。事实上，神经网络使用了类似的方法，感知机的中间隐层做的也是类似的事情。

本部分只介绍线性可分支持向量机和线性支持向量机。

Generate Parentheses (LeetCode 22)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

基本思想

激活函数在深度学习中的作用就跟神经元中 “细胞体” 的功能类似：确定输出中哪些要被激活。我们都知道 SVM 通过核方法对非线性可分的数据进行分类，这其实是一种提升的方法（机器学习中很多问题都是类似的降个维度或升个维度）。为啥提升维度就能够让原本线性不可分的数据可分呢？我们以下图为例：

两组不同标签的数据构成一个近似的同心圆。要想将两种不同的点分开，靠二维的一条直线肯定是没办法了，此时我们可以把数据映射到三维空间，我们可以想象让同心圆之间再插入一个圆，然后让这个圆以内的整块都凸起来，也就是让它脱离原来的维度。这时候我们只要在两个平面中间任意选择一个平面就可以将数据集分开了。那这和我们的激活函数有啥关系呢？其实激活函数所提供的 “非线性” 变换正是类似的方式。也就是说，只要有非线性的激活函数，三层（输入、1 个隐层、输出层）的神经网络理论上可以逼近任意函数。

Yam

Feeling, Coding, Thinking

EDA