第五部分-应对不确定性与大规模问题
第五部分：应对不确定性与大规模问题
本部分聚焦于处理动态输入、超大规模搜索空间及实际工程中的复杂优化问题。
5.1 在线算法 (Online
Algorithms)
5.1.1 在线算法
离线和在线
离线算法 (Offline
Algorithm)：在计算开始前，问题的所有输入数据（整个序列）均已知。算法可以统筹全局做出最优决策。
在线算法 (Online Algorithm)：输入是以序列形式逐步到来的
(\(x_1, x_2,
\dots\))。算法必须在接收到每一个输入 \(x_i\)
时立即做出决策，且该决策通常是不可逆的。算法无法预知未来的输入。
在线算法分析和竞争比
在线算法的分析通常被建模为在线选手 (Online Player) 与 恶意对手
(Malicious Adversary) 之间的博弈： - 在线选手运行在线算法。 -
恶意对手了解选手的算法逻辑，并精心构造一组最坏情况的输入序列，试图最大化在线选手的代价。
目标：设计一种算法，使得即使在对手最恶毒的攻击下，其表现也不会比拥有上帝视角的离线最优算法差太多。
设 \(A\) 是 ...
第四部分-计算复杂性与近似解
第四部分：计算复杂性与近似解
本部分探讨计算的边界，定义什么是“难解”问题，并介绍在无法求得精确解时的应对策略。
4.1 NP 完全理论
(NP-Completeness Theory)
在现有的算法设计技术中，分治策略 (Divide-and-Conquer)、动态规划
(Dynamic Programming) 和贪心算法 (Greedy Algorithm)
已经成功解决了大量计算问题。然而，仍存在一类问题，至今未能找到高效的（多项式时间的）算法。典型的“难解”问题包括：
0-1 背包问题 (0-1 Knapsack Problem)
旅行商问题 (Traveling Salesperson Problem, TSP)
集合覆盖问题 (Set Cover Problem)
顶点覆盖问题 (Vertex Cover Problem)
4.1.1 问题
判定问题和最优化问题
判定问题是指输出仅有两种可能结果的问题，即答案属于集合
{Yes, No} 或 {1, 0}。 最优化问题的目标是在所有可行解
(Feasible Solution) 中，寻 ...
第三部分-精确最优化策略
第三部分：精确最优化策略本部分聚焦于解决多阶段决策过程、和组合优化问题，旨在寻找全局最优解。
3.1 动态规划 (Dynamic Programming)3.1.1 动态规划和多阶段决策动态规划是解决多阶段决策过程 (Multi-stage decision process) 最优化的一种方法。对于离散问题，解析数学无法施展，动态规划则成为一个非常有效的工具。
不同于线性规划等方法，动态规划建立目标函数方程后，没有通用的求解算法，需结合具体问题特性采用相应的数学技巧，且随着状态变量维度的增加，计算量呈指数级增长。
依据决策过程的时间参量与演变性质，动态规划模型可划分为以下四个维度：
时间参量维度： 离散决策过程 (Discrete)：过程可被划分为有限个阶段。
连续决策过程 (Continuous)：过程随时间连续变化。
演变性质维度： 确定性决策过程 (Deterministic)：状态转移是确定的。
随机性决策过程 (Stochastic)：状态转移服从某种概率分布。
通常来说，动态规划算法时间复杂度为多项式级，最终的目标是获得最优策略族，即每一个中间节点到重点 ...
第二部分-基于规模的策略：分解与变换 (Structure Decomposition)
第二部分：基于规模的策略：分解与变换
(Structure Decomposition)
2.1 分治法
2.1.1 分而治之
分治的基本逻辑是将原始问题分解为若干子问题，在逐个解决各
个子问题的基础上，得到原始问题的解。那么最基础的，根据如何由分解出的子问题得出原始问题的解，
分治策略可分为两种情形：
原始问题的解只存在于分解出的某一个（或某几个）
子问题中，则只需要在这一（或这几个）子问题中求 解即可
原始问题的解需要由各个子问题的解再经过综合处理 得到
同时寻找最大值和最小值：
直接算法是
1234561. x ← A[1]; y ← A[1]2. for i ← 2 to n3. if A[i] < x then x ← A[i]4. if A[i] > y then y ← A[i]5. end for6. return (x, y)
总比较次数为\(2(n-1) = 2n -
2\)。
如果利用分支思想将数组对半分割，分别求出左右两半的最大最小值，再进行合并。
123456789101112Algorith ...
第一部分-算法分析基础与开发规范 (Foundations & Methodology)
第一部分：算法分析基础与开发规范
(Foundations & Methodology)
1.1 算法核心概念 (Core
Concepts of Algorithms)
1.1.1 算法的定义与本质
(Definition & Nature)
算法是执行特定任务的一组指令集（A set of instructions for performing
a
task）。程序通常会输入（Input）必要的数值，以正确的方式进行处理，然后将结果输出（Output）给用户。因此，程序通常被看作算法
（alogorithm）和数据（data）的结合。
算法的静态与动态 * 静态 (Static)：
算法在纸面或代码中由作者编写的形式。 * 动态 (Dynamic)：
算法被处理器（Processor）执行时的过程。
算法的四个核心特征
清晰且可执行 (Clear and Executable)：
每一条指令必须明确无歧义，且能够被执行。
确定性 (Determinate)：
在任何给定状态下，下一步的操作必须是唯一的，不存在二义性。
...
风险管理
风险管理
这是一次训练，旨在以不同的视角看待世界：识别可能发生的事、理解不可预测性、在不确定性中做决策。
Introduction
思维方法 [6]
归纳法Approche
inductive：观察多个具体案例，从而形成一个普遍规律。能发现规律，构建理论。但永远无法百分百确定（只要有一只黑天鹅就能推翻该规律）。
演绎法Approche
déductive：从一个规则或普遍定律出发，推导出某个特定情境的结论。例如规则特例结论三段论。
溯因法Approche
abductive：从一个令人惊讶的事实出发，寻找最合理的解释。合理，但未必真实。
论述式方法Approche
discursive：通过讨论、论证和反论证（logos）推进推理。
在风险管理中的应用
归纳法：分析经验反馈以得出规则。
演绎法：应用某个 ISO 规范或标准方法。
溯因法：通过假设来解释意外发生的事故。
论述式方法：专家之间进行讨论，以对威胁进行分级。
知识的类别
柏拉图洞穴寓言
认知层次
风险管理对应
Eikasi ...
梵蒂冈之囚
梵蒂冈之囚
本文作为自7月1日至10月20日期间日记的后记撰写。
（一）
当你走进梵蒂冈那生静卧于圣彼得大教堂阴影下的宗座宫，为之震撼以至恐怖是理所应当的。你会因惊讶的情感覆盖意识而驻足不前，而后又发现周围行人芳无其事穿行，顿时面色发红，担心不经意间让没见识的气息暴露。不必担心，这座已经近百年没有与外界交融的城市中，能称得上游客的，只有你一个人。作为那位教皇的客人，你大可挺起胸膛。
来，请到这边——这条绵延如林骨的回廊。此间为祈祷厅，此间为接见厅，如是如是……你以为我像一位导游？在我年轻的时候，曾有人嫉妒我的口才，而去诽谤我的长辈是一位导游。——在这样一座只有一位客人的宫殿中，当个导游或许也是份清闲职业。不不，你不必道歉，正如我也不会称你为您一样。
推开此扇本木门。请小心，王座厅中的一切——不，王座中有些物件十分脆弱、陈旧。你看，门上浮刻的是那篇“复生之火鸟”的史诗。对你来说，不过是最近的典故，甚至算不上什么典故。但对我来说，已经是不可追溯的传说了。
（二）
我推开门，却发现其后还有一扇小门，形成了三角形的封闭空间。再用力推开，我从那门进入了王座厅。王座厅 ...
FastMNMF及改进
FastMNMF及改进
FastMNMF
FastMNMF是一种基于矩阵联合对角化的MNMF的加速算法；后者在前一篇笔记中已经简略描述，是一种对NMF在音频应用上的多通道扩展。
MNMF
回顾MNMF的音频建模，MNMF认为一个音源\(s_{jfn}\)由多个表现为复高斯分布的成分\(c_{kfn}\)组成。
\[
s_{j f n}=\sum_{k \in \mathcal{K}_j} c_{k f n} \quad \text { avec } c_{k
f n} \sim \mathcal{N}_{\mathbb{C}}\left(0, w_{f k} h_{k n}\right)
\]
这些成分相互独立，因此源被定义为：
\[
s_{j f n} \sim \mathcal{N}_{\mathbb{C}}\left(0, \sum_{k \in
\mathcal{K}_j} w_{f k} h_{k n}\right)
\]
被观测信号被定义为源的线性组合：
\[
x_{ifn}=\mathcal{N}_{\mathbb{C}}\left ...
波束形成
波束形成
空间协方差矩阵 SCM
在多麦克风语音处理里，我们把每一个频点 \(f\) 上、在同一时刻 \(t\) 采集到的 \(\mathbf{M}\) 路复数
STFT系列表示为一个列向量：
\[
\mathbf{y}(t, f)=\left[\begin{array}{c}
Y_1(t, f) \\
Y_2(t, f) \\
\vdots \\
Y_M(t, f)
\end{array}\right] \in \mathbb{C}^{M \times 1}
\]
其空间协方差矩阵SCM定义为：
\[
\mathbf{\Phi}(f)=\mathbb{E}\left[\mathbf{y}(t, f) \mathbf{y}(t,
f)^{\mathrm{H}}\right] \in \mathbb{C}^{M \times M}
\]
有时也需要每一帧的局部SCM：
\[
\hat{\boldsymbol{\Phi}}_y(t, f)=\frac{1}{2 w+1}
\sum_{t^{\prime}=t-w}^{t+w} \mathbf{y} ...
从北京的四种毒蛇开始
从北京的四种毒蛇开始
众所周知，北京目前确认的毒蛇四种，分别是短尾蝮，华北蝮，西伯利亚蝮和虎斑颈槽蛇。前三种都属于蝰科亚洲蝮属；而虎斑颈槽蛇属于游蛇科剑蛇属。
关于文中的数据，原本先了解一下，但过于复杂以至于放弃了，所以没有标记注射类型（实际上是开始查的时候不知道存在多种类型，而又不想再确认）。
短尾蝮 Gloydius brevicaudus
似乎是北京分布最广的毒蛇，出现在低海拔的山区。据说，它分布的海拔上限为1100m。成年短尾蝮的体长一般在60-70cm，有一个快速缩短的尾端，尾部可能呈现粉红色。
短尾蝮似乎是一种伏击型猎手，会在草丛中蹲一天守株待兔。但它遭遇威胁时，会首先发出警告信号。它会将身体盘成S形，头部抬高，颈部膨胀，同时发出“嘶嘶”的声音，试图吓退攻击者。但这一点可能跟一般印象中的蛇的体弯行为（Body-bending
behaviour, BBB）不同\(^{[1]}\)(下图为乌苏里蝮，并非短尾蝮)：
在春秋季节，短尾蝮主要为昼行性，而炎热的夏季则转为夜行性。据说，炎热的夏季，短尾蝮喜欢在凉爽的黄昏到夜间从石缝里爬出来活动\(^{[2 ...