光与影的个人博客

437. 路径总和 III

前后一共做了三次，每次都想不出来使用前缀和的方法。

思路1：DFS遍历

先序遍历整个二叉树，遍历到某一结点后，以该节点为子树，查找当前子树中，是否存在一条从根节点出发的路径，满足路径和条件。

复杂度分析：

• 时间复杂度：与DFS遍历不同的点，在于每到达一个节点都需要重新遍历子树，寻找备选最优解，时间复杂度为O(N^2)
• 空间复杂度：两次遍历不影响栈的深度，最大栈深度与DFS相同，空间复杂度为O(logN)

Question Answering

相较于检索更进一步，给出一个问题，自动的找出这个问题的最合适答案，可以将这个问题划分为两个步骤

1. 找到包含问题答案的文档
2. 在文档中找到当前问题的答案（阅读理解 Reading Comprehension）

如果一个机器理解了一段问题，机器应该能够提供问题的正确答案，且答案中不包含与问题无关的相关信息

SQuAD(Stanford Question Answering Dataset)

每个问题对应一篇文章，答案是文章内的一段单词序列。

为每个问题提供多个可选的标准答案

SQuAD如何评估（V1.1）

• 为每个问题提供三个标准答案
• 使用两种评分机制
  1. Exact match：按照字面意思理解，如果答案在三个标准答案中(1),不在标准答案中(0)
  2. F1-score：分别计算对于每个问题回答的F1-score(具体怎么算法不知道)，对整个数据集上求平均后得到结果
• 两种评分机制军忽略标点符号和无关的词汇（a,an,the）

早期机器翻译

采用 单词对应词典的形式，存储在磁带上，翻译时通过查字典的形式，找到对应词组合成句子。

基于统计的机器翻译（Statistical Machine Translation SMT）

从概率的角度解决机器翻译问题， 首先语料中学习概率模型（不同语言单词之间的概率和语言内的语言模型），通过建立的概率模型实现翻译功能。

RNN梯度消失/爆炸问题（vanishing/exploding gradient problem）

由于RNN对于不同时间步的输入使用同一个神经元，在反向传播计算梯度时，随着时间步的增加，会出现梯度爆炸和消失问题

语言模型

通过语言模型的构建，实现能够根据已知序列推断序列中的下一个单词，如搜索引擎中的搜索推断等。

模型的形式化定义如下，给定一系列单词，预测下一个单词的概率分布，该概率分布为当前模型词典库上词语的概率分布

句法分析

句法分析与上下文无关文法相对立，强调通过对于句子语法结构的分析，实现对于句子的理解。最常见的三种句法分析任务如下

1. 句法结构分析 识别句子中的短语结构和层次关系
2. 依存关系分析 识别句子中词与词之间的依存关系，确定词语的含义
3. 深层文法句法分析 利用深层文法对句子进行分析

依存句法分析（Dependency Parsing）

依存结构展示了句子中依赖于其他词语的单词，这种依赖体现为被修饰或者被限定

神经网络介绍

神经网络介绍部分省略

命名实体识别（NER）

标注中句子中的目标词性词语-实体，其中实体是指识别文本中具有特定意义的实体，主要包括人名、地名、机构名、专有名词等

命名实体存在的困难：

1. 难以确定实体的上下文边界（王小明 还是 小明）
2. 难以确定词语是否为 实体
3. 实体的具体含义依赖于上下文，难以确定
4. 难以辨别不知道的实体（特定语境 特定环境下的某些词作为实体）

最开始从b站老戴的全流程视频里了解到了死亡搁浅这款游戏，听说这个游戏好看不好玩，原计划在b站云通关，但是看了几期视频后，发现游戏所营造的世界观和剧情深深的吸引了我，于是等到了Epic夏促打折入手，这几天终于通关了游戏，心里有一些小感受，写一点东西，算是对死亡搁浅体验的个人总结。

想要通过计算机解决NLP问题，首先要解决的就是词语表示问题，由于一个词语在不同语境以及不同文化背景下含义的多样性，如何在计算机中有效的存储，表示不同词语的不同含义，是需要解决的重要问题。

传统表示方式

WordNet （discrete representation）

上义词是对事物的概括性、抽象性说明；下义词是事物的具体表现形式或更为具体的说明

采用同义词（synonym）和上义词（hypernym）两个相关词语集合来描述当前词语的含义，当前方法一定程度上能够正确表示词语含义，但是存在一定问题

1. 忽略了词语在不同语境中的细微语义差异（比如 “中” 只有在河南话中和 “好” 是同义词）
2. 词语的新的词义的添加较为困难
3. 同义词和上义词定义较为主观，需要人工来整理两个词语集合

主要包括三个基本核心概念：

• 镜像（image)：相当于一个静态的文件系统，类似于未安装的windows ios文件，相当于是一个未挂载的root文件系统
• 容器（container)：容器是镜像运行时的实体，可以启动、创建、停止以及删除。容器的实质是进程，但与直接在宿主执行的进程不同，容器进程运行于属于自己的独立的命名空间
• 仓库（Repository）：镜像中心，类似于maven的依赖包中心，用来保存镜像，最常使用的公共仓库是官方的Docker Hub

基本架构（cs架构）:

守护进程（daemon）是生存期长的一种进程，没有控制终端。它们常常在系统引导装入时启动，仅在系统关闭时才终止

• Docker 客户端(Client):与docker host中的守护进程进行通信，通过命令执行实际的操作（cs架构中的c）
• Docker 主机(Host):运行容器，存储镜像的机器
• Docker Registry：一个 Docker Registry 中可以包含多个仓库（Repository）；每个仓库可以包含多个标签（Tag）；每个标签对应一个镜像。