在凸性假设下,几何算法问题往往变得易于处理。优化,体积计算,几何学习和寻找质心都是凸集明显容易的问题的例子。我们将对这一现象进行深入的研究,探索三个相互联系紧密的路径。第一个是几何不等式理论。我们从经典的主题开始,如Brunn-Minkowski不等式,然后处理更近期的发展,如凸体的等周定理及其对对数凹函数的推广。第二个轨迹的动机是通过随机游走对几何分布进行抽样。这里我们将开发一些通用工具并使用它们来分析几何随机游动。第一条轨迹的不等式在限定这些轨迹的收敛速度方面起着关键作用。最后一个方面是采样和各种算法问题之间的联系,最显著的是,计算凸体的体积(或更普遍地说,积分一个对数凹函数)。有些令人惊讶的是,随机抽样将是用于这些问题的多项式时间算法的常见和基本特征。在某些情况下,包括体积问题,随机游走采样是唯一已知的得到多项式时间算法的方法。

https://www.cc.gatech.edu/~vempala/acg/notes.pdf

成为VIP会员查看完整内容
0
34

相关内容

这本教科书强调了代数和几何之间的相互作用,以激发线性代数的研究。矩阵和线性变换被认为是同一枚硬币的两面,它们的联系激发了全书的探究。围绕着这个界面,作者提供了一个概念上的理解,数学是进一步的理论和应用的核心。继续学习线性代数的第二门课程,您将会对《高等线性代数与矩阵代数》这本书有更深的了解。

从向量、矩阵和线性变换的介绍开始,这本书的重点是构建这些工具所代表的几何直观。线性系统提供了迄今为止看到的思想的强大应用,并导致子空间、线性独立、基和秩的引入。然后研究集中在矩阵的代数性质,阐明了它们所代表的线性变换的几何性质。行列式、特征值和特征向量都可以从这种几何观点中获益。在整个过程中,“额外主题”部分以广泛的思想和应用扩大了核心内容,从线性规划,到幂迭代和线性递归关系。每个部分都有各种层次的练习,包括许多设计用来用电脑程序解决的练习。

这本书是从线性变换和矩阵本身都是有用的对象的角度写的,但它是两者之间的联系,真正打开线性代数的魔法。有时候,当我们想知道一些关于线性变换的东西时,最简单的方法就是找到一组基然后看对应的矩阵。相反,有许多有趣的矩阵和矩阵运算家族,它们似乎与线性变换无关,但却可以解释一些基无关对象的行为。

线性与矩阵代数导论是线性代数的理想入门证明课程。学生被假定已经完成了一到两门大学水平的数学课程,尽管微积分不是明确的要求。教师将会感激有足够的机会选择符合每个教室需求的主题,并通过WeBWorK提供在线作业集。

成为VIP会员查看完整内容
0
51

本书是信息论领域中一本简明易懂的教材。主要内容包括:熵、信源、信道容量、率失真、数据压缩与编码理论和复杂度理论等方面的介绍。

本书还对网络信息论和假设检验等进行了介绍,并且以赛马模型为出发点,将对证券市场研究纳入了信息论的框架,从新的视角给投资组合的研究带来了全新的投资理念和研究技巧。

本书适合作为电子工程、统计学以及电信方面的高年级本科生和研究生的信息论基础教程教材,也可供研究人员和专业人士参考。

本书是一本简明易懂的信息论教材。正如爱因斯坦所说:“凡事应该尽可能使其简单到不能再简单为止。''虽然我们没有深人考证过该引语的来源(据说最初是在幸运蛋卷中发现的),但我们自始至终都将这种观点贯穿到本书的写作中。信息论中的确有这样一些关键的思想和技巧,一旦掌握了它们、不仅使信息论的主题简明,而且在处理新问題时提供重要的直觉。本书来自使用了十多年的信息论讲义,原讲义是信息论课程的高年级本科生和一年级研究生两学期用的教材。本书打算作为通信理论.计算机科学和统计学专业学生学习信息论的教材。

信息论中有两个简明要点。第一,熵与互信息这样的特殊量是为了解答基本问题而产生的。例如,熵是随机变量的最小描述复杂度,互信息是度量在噪声背景下的通信速率。另外,我们在以后还会提到,互信息相当于已知边信息条件下财富双倍的增长。第二,回答信息理论问邀的答案具有自然的代数结构。例如,熵具有链式法则,因而,谪和互信息也是相关的。因此,数据压缩和通信中的问题得到广泛的解释。我们都有这样的感受,当研究某个问题时,往往历经大量的代数运算推理得到了结果,但此时没有真正了解问题的全莪,最终是通过反复观察结果,才对整个问题有完整、明确的认识。所以,对一个问题的全面理解,不是靠推理,而是靠对结果的观察。要更具体地说明这一点,物理学中的牛顿三大定律和薛定谔波动方程也许是最合适的例子。谁曾预见过薛定谔波动方程后来会有如此令人敬畏的哲学解释呢?

在本书中,我们常会在着眼于问题之前,先了解一下答案的性质。比如第2章中,我们定义熵、相对熵和互信息,研究它们之间的关系,再对这些关系作一点解释·由此揭示如何融会贯通地使用各式各样的方法解决实际问题。同理,我们顺便探讨热力学第二定律的含义。熵总是增加吗?答案既肯定也否定。这种结果会令专家感兴趣,但初学者或i午认为这是必然的而不会深人考虑。

在实际教学中.教师往往会加人一自己的见解。事实上,寻找无人知道的证明或者有所创新的结果是一件很愉快的事情。如果有人将新的思想和已经证明的内容在课堂上讲解给学生,那么不仅学生会积极反馈“对,对,对六而且会大大地提升教授该课程的乐崆我们正是这样从研究本教材的许多新想法中获得乐趣的。

本书加人的新素材实例包括信息论与博弈之间的关系,马尔可夫链背景下热力学第二定律的普遍性问题,信道容量定理的联合典型性证明,赫夫曼码的竞争最优性,以及关于最大熵谱密度估计的伯格(回定理的证明。科尔莫戈罗夫复杂度这一章也是本书的独到之处。面将费希尔信息,互信息、中心极限定理以及布伦一闵可夫斯基不等式与熵幂不等式联系在一起,也是我们引以为豪之处。令我们感到惊讶的是.关于行列式不等式的许多经典结论,当利用信息论不等式后会很容易得到证明。

自从香农的奠基性论文面世以来,尽管信息论已有了相当大的发展,但我们还是要努力强调它的连贯性。虽然香农创立信息论时受到通信理论中的问题启发,然而我们认为信息论是一门独立的学科,可应用于通信理论和统计学中。我们将信息论作为一个学科领域从通信理论、概率论和统计学的背景中独立出来因为明显不可能从这些学科中获得难以理解的信息概念。由于本书中绝大多数结论以定理和证明的形式给出,所以,我们期望通过对这些定理的巧妙证明能说明这些结论的完美性。一般来讲,我们在介绍问题之前先描述回题的解的性质,而这些很有的性质会使接下来的证明顺理成章。

使用不等式串、中间不加任何文字、最后直接加以解释,是我们在表述方式上的一项创新希望读者学习我们所给的证明过程达到一定数量时,在没有任何解释的情况下就能理解其中的大部分步,并自己给出所需的解释这些不等式串好比模拟到试题,读者可以通过它们确认自己是否已掌握证明那些重要定理的必备知识。这些证明过程的自然流程是如此引人注目,以至于导致我们轻视了写作技巧中的某条重要原则。由于没有多余的话,因而突出了思路的逻辑性与主題思想u我们希望当读者阅读完本书后,能够与我们共同分亨我们所推崇的,具有优美、简洁和自然风格的信息论。

本书广泛使用弱的典型序列的方法,此概念可以追溯到香农1948年的创造性工作,而它真正得到发展是在20世纪70年代初期。其中的主要思想就是所谓的渐近均分性(AEP),或许可以粗略地说成“几乎一切事情都是等可能的"

第2章阐述了熵、相对熵和互信息之同的基本代数关系。渐近均分性是第3章重中之重的内容,这也使我们将随机过程和数据压缩的熵率分别放在第4章和第5章中论述。第6章介绍博弈,研究了数据压缩的对偶性和财富的增长率。可作为对信息论进行理性思考基础的科尔莫戈罗夫复杂度,拥有着巨大的成果,放在第14章中论述。我们的目标是寻找一个通用的最矩描述,而不是平均意义下的次佳描述。的确存在这样的普遍性概念用来刻画一个对象的复杂度。该章也论述了神奇数0,揭示数学上的不少奥秘,是图灵机停止运转概率的推广。第7章论述信道容量定理。第8章叙述微分熵的必需知识,它们是将早期容量定理推广到连续噪声信道的基础。基本的高斯信道容量问题在第9章中论述。第il章阐述信息论和统计学之间的关系,20世纪年代初期库尔贝克首次对此进行了研究,此后相对被忽视。由于率失真理论比无噪声数据压缩理论需要更多的背景知识,因而将其放置在正文中比较靠后的第10章。

网络信息理论是个大的主题,安排在第巧章,主要研究的是噪声和干扰存在情形下的同时可达的信息流。有许多新的思想在网络信息理论中开始活跃起来,其主要新要素有干扰和反馈第16章讲述股票市场,这是第6章所讨论的博弈的推广,也再次表明了信息论和博弈之间的紧密联系。第17章讲述信息论中的不等式,我们借此一隅把散布于全书中的有趣不等式重新收拢在一个新的框架中,再加上一些关于随机抽取子集熵率的有趣新不等式。集合和的体积的布伦一闵可夫斯基不等式,独立随机变量之和的有效方差的熵幂不等式以及费希尔信息不等式之间的美妙关系也将在此章中得到详尽的阐述。

本书力求推理严密,因此对数学的要求相当高·要求读者至少学过一学期的概率论课程且有扎实的数学背景,大致为本科高年级或研究生一年级水平。尽管如此,我们还是努力避免使用测度论。因为了解它只对第16章中的遍历过程的AEP的证明过程起到简化作用。这符合我们的观点,那就是信息论基础与技巧不同,后者才需要将所有推广都写进去。

本书的主体是第2,3,4,5,7,8,9,10,11和巧章,它们自成体系,读懂了它们就可以对信息论有很好的理解。但在我们看来,第14章的科尔莫戈罗夫复杂度是深人理解信息论所需的必备知识。余下的几章,从博弈到不等式.目的是使主题更加连贯和完美。

成为VIP会员查看完整内容
0
116

这是我2004年,2006年和2009年在斯坦福大学教授的概率理论博士课程的讲义。本课程的目标是为斯坦福大学数学和统计学系的博士生做概率论研究做准备。更广泛地说,文本的目标是帮助读者掌握概率论的数学基础和在这一领域中证明定理最常用的技术。然后将此应用于随机过程的最基本类的严格研究。

为此,我们在第一章中介绍了测度与积分理论中的相关元素,即事件的概率空间与格-代数、作为可测函数的随机变量、它们的期望作为相应的勒贝格积分,以及独立性的重要概念。

利用这些元素,我们在第二章中研究了随机变量收敛的各种概念,并推导了大数的弱定律和强定律。

第三章讨论了弱收敛的理论、分布函数和特征函数的相关概念以及中心极限定理和泊松近似的两个重要特例。

基于第一章的框架,我们在第四章讨论了条件期望的定义、存在性和性质,以及相关的规则条件概率分布。

第五章讨论了过滤、信息在时间上的级数的数学概念以及相应的停止时间。关于后者的结果是作为一组称为鞅的随机过程研究的副产品得到的。讨论了鞅表示、极大不等式、收敛定理及其各种应用。为了更清晰和更容易的表述,我们在这里集中讨论离散时间的设置来推迟与第九章相对应的连续时间。

第六章简要介绍了马尔可夫链的理论,概率论的核心是一个庞大的主题,许多教科书都致力于此。我们通过研究一些有趣的特殊情况来说明这类过程的一些有趣的数学性质。

在第七章中,我们简要介绍遍历理论,将注意力限制在离散时间随机过程的应用上。我们定义了平稳过程和遍历过程的概念,推导了Birkhoff和Kingman的经典定理,并强调了该理论的许多有用应用中的少数几个。

第八章建立了以连续时间参数为指标的右连续随机过程的研究框架,引入了高斯过程族,并严格构造了布朗运动为连续样本路径和零均值平稳独立增量的高斯过程。

第九章将我们先前对鞅和强马尔可夫过程的处理扩展到连续时间的设定,强调了右连续滤波的作用。然后在布朗运动和马尔可夫跳跃过程的背景下说明了这类过程的数学结构。

在此基础上,在第十章中,我们利用不变性原理重新构造了布朗运动作为某些重新标定的随机游动的极限。进一步研究了其样本路径的丰富性质以及布朗运动在clt和迭代对数定律(简称lil)中的许多应用。

https://statweb.stanford.edu/~adembo/stat-310b/lnotes.pdf

成为VIP会员查看完整内容
0
77

这是一门关于算法设计和分析的高级课程,涵盖了在典型的算法入门课程中没有学习到的一系列主题和技术。

本课程旨在让学生熟悉过去15-20年间在算法设计中开发的(部分)主要工具和技术,这些工具和技术目前是开发高效算法的关键要素之一。

本课程将涵盖一系列主题,包括以下内容:保留切割或距离时的图的稀疏性、各种近似算法技术和概念、度量嵌入和概率树嵌入、在线算法、乘法权值更新、流媒体算法、素描算法,以及对MapReduce算法的简要介绍。

https://people.inf.ethz.ch/gmohsen/AA20/

成为VIP会员查看完整内容
0
70

这本书的第五版继续讲述如何运用概率论来深入了解真实日常的统计问题。这本书是为工程、计算机科学、数学、统计和自然科学的学生编写的统计学、概率论和统计的入门课程。因此,它假定有基本的微积分知识。

第一章介绍了统计学的简要介绍,介绍了它的两个分支:描述统计学和推理统计学,以及这门学科的简短历史和一些人,他们的早期工作为今天的工作提供了基础。

第二章将讨论描述性统计的主题。本章展示了描述数据集的图表和表格,以及用于总结数据集某些关键属性的数量。

为了能够从数据中得出结论,有必要了解数据的来源。例如,人们常常假定这些数据是来自某个总体的“随机样本”。为了确切地理解这意味着什么,以及它的结果对于将样本数据的性质与整个总体的性质联系起来有什么意义,有必要对概率有一些了解,这就是第三章的主题。本章介绍了概率实验的思想,解释了事件概率的概念,并给出了概率的公理。

我们在第四章继续研究概率,它处理随机变量和期望的重要概念,在第五章,考虑一些在应用中经常发生的特殊类型的随机变量。给出了二项式、泊松、超几何、正规、均匀、伽玛、卡方、t和F等随机变量。

成为VIP会员查看完整内容
2
142

这些笔记的第一个版本是为第一年的研究生代数课程编写的。和大多数这类课程一样,讲义集中在抽象群,特别是有限群。然而,大多数数学家遇到的群并不是抽象的群,而是代数群、拓扑群或李群,而且感兴趣的不仅仅是群本身,还有它们的线性表示。我的意图是(将来的某一天)扩展笔记以考虑到这一点,并制作一本规模适中(c200页)的书,为数学、物理和相关领域的刚开始学习的研究生提供更全面的关于群论的介绍。

成为VIP会员查看完整内容
0
81

本书涵盖了这些领域中使用Python模块演示的概率、统计和机器学习的关键思想。整本书包括所有的图形和数值结果,都可以使用Python代码及其相关的Jupyter/IPython Notebooks。作者通过使用多种分析方法和Python代码的有意义的示例,开发了机器学习中的关键直觉,从而将理论概念与具体实现联系起来。现代Python模块(如panda、y和Scikit-learn)用于模拟和可视化重要的机器学习概念,如偏差/方差权衡、交叉验证和正则化。许多抽象的数学思想,如概率论中的收敛性,都得到了发展,并用数值例子加以说明。本书适合任何具有概率、统计或机器学习的本科生,以及具有Python编程的基本知识的人。

成为VIP会员查看完整内容
0
156

本课程的目的是提供非渐近方法的介绍,以研究在高维随机结构出现的概率,统计,计算机科学,和数学。重点是开发一套已被证明在不同领域的广泛应用程序中有用的公共工具。根据时间和听众的兴趣,主题可能包括:措施的集中;功能性,运输成本,鞅不等式;isoperimetry;马尔可夫半群,混合时间,随机场;hypercontractivity;阈值和影响;斯坦的方法;随机过程的最高原则;高斯和拉德马赫不等式;通用的链接;熵和组合维数;选择应用程序。

成为VIP会员查看完整内容
0
87

作为布尔逻辑的替代

虽然逻辑是理性推理的数学基础和计算的基本原理,但它仅限于信息既完整又确定的问题。然而,许多现实世界的问题,从金融投资到电子邮件过滤,本质上是不完整或不确定的。概率论和贝叶斯计算共同提供了一个处理不完整和不确定数据的框架。

不完全和不确定数据的决策工具和方法

贝叶斯编程强调概率是布尔逻辑的替代选择,它涵盖了为真实世界的应用程序构建概率程序的新方法。本书由设计并实现了一个高效概率推理引擎来解释贝叶斯程序的团队编写,书中提供了许多Python示例,这些示例也可以在一个补充网站上找到,该网站还提供了一个解释器,允许读者试验这种新的编程方法。

原则和建模

只需要一个基本的数学基础,本书的前两部分提出了一种新的方法来建立主观概率模型。作者介绍了贝叶斯编程的原理,并讨论了概率建模的良好实践。大量简单的例子突出了贝叶斯建模在不同领域的应用。

形式主义和算法

第三部分综合了已有的贝叶斯推理算法的工作,因为需要一个高效的贝叶斯推理引擎来自动化贝叶斯程序中的概率演算。对于想要了解贝叶斯编程的形式主义、主要的概率模型、贝叶斯推理的通用算法和学习问题的读者,本文提供了许多参考书目。

常见问题

第四部分连同词汇表包含了常见问题的答案。作者比较了贝叶斯规划和可能性理论,讨论了贝叶斯推理的计算复杂性,讨论了不完全性的不可约性,讨论了概率的主观主义和客观主义认识论。

贝叶斯计算机的第一步

创建一个完整的贝叶斯计算框架需要新的建模方法、新的推理算法、新的编程语言和新的硬件。本书着重于方法论和算法,描述了实现这一目标的第一步。它鼓励读者探索新兴领域,例如仿生计算,并开发新的编程语言和硬件架构。

成为VIP会员查看完整内容
0
158

本备忘单是机器学习手册的浓缩版,包含了许多关于机器学习的经典方程和图表,旨在帮助您快速回忆起机器学习中的知识和思想。

这个备忘单有两个显著的优点:

  1. 清晰的符号。数学公式使用了许多令人困惑的符号。例如,X可以是一个集合,一个随机变量,或者一个矩阵。这是非常混乱的,使读者很难理解数学公式的意义。本备忘单试图规范符号的使用,所有符号都有明确的预先定义,请参见小节。

  2. 更少的思维跳跃。在许多机器学习的书籍中,作者省略了数学证明过程中的一些中间步骤,这可能会节省一些空间,但是会给读者理解这个公式带来困难,读者会在中间迷失。

成为VIP会员查看完整内容
0
200
小贴士
相关VIP内容
专知会员服务
51+阅读 · 5月24日
专知会员服务
116+阅读 · 3月22日
专知会员服务
77+阅读 · 2020年12月3日
专知会员服务
70+阅读 · 2020年10月22日
专知会员服务
142+阅读 · 2020年7月28日
专知会员服务
81+阅读 · 2020年6月25日
专知会员服务
156+阅读 · 2020年6月3日
专知会员服务
158+阅读 · 2020年5月18日
机器学习速查手册,135页pdf
专知会员服务
200+阅读 · 2020年3月15日
相关论文
Xijun Li,Weilin Luo,Mingxuan Yuan,Jun Wang,Jiawen Lu,Jie Wang,Jinhu Lu,Jia Zeng
1+阅读 · 5月27日
Qiaoyi Liu,Dillon Huff,Jeff Setter,Maxwell Strange,Kathleen Feng,Kavya Sreedhar,Ziheng Wang,Keyi Zhang,Mark Horowitz,Priyanka Raina,Fredrik Kjolstad
0+阅读 · 5月26日
GeomCA: Geometric Evaluation of Data Representations
Petra Poklukar,Anastasia Varava,Danica Kragic
8+阅读 · 5月26日
Timothy M. Chan,Sariel Har-Peled,Mitchell Jones
0+阅读 · 5月25日
Ioannis Z. Emiris,Ioannis Psarros
3+阅读 · 2020年4月13日
Geometric Graph Convolutional Neural Networks
Przemysław Spurek,Tomasz Danel,Jacek Tabor,Marek Śmieja,Łukasz Struski,Agnieszka Słowik,Łukasz Maziarka
7+阅读 · 2019年9月11日
Meng Qu,Jian Tang
6+阅读 · 2019年6月20日
Tianyi Liu,Shiyang Li,Jianping Shi,Enlu Zhou,Tuo Zhao
3+阅读 · 2018年10月1日
Wenbin Li,Jing Huo,Yinghuan Shi,Yang Gao,Lei Wang,Jiebo Luo
8+阅读 · 2018年5月15日
Joel A. Tropp,Alp Yurtsever,Madeleine Udell,Volkan Cevher
4+阅读 · 2018年1月2日
Top