我的2022年度总结
今天是2022年12月31日,据说这是2022年的最后一天,我坐在寝室的座位上,开始写下对这一年的总结。
2018年和2019年的12月31日,我在紫云篮球场的跨年晚会中迎来新的一年,而2020年的12月31日则是在寝室度过了百无聊赖的一晚,我记得那天还顺便复习了计算机网络,因为平时没咋学,但是这门课的期末考试又特别的烦人,2021年的12月31日,这时候我已经大四了,刚结束保研没几个月,这一天我也是坐在寝室的电脑前写了一小篇年度总结,没想到2022年的最后一天,我依然在用这种莫名其妙的方式来度过。
先说好,我不喜欢做什么年终总结。如果说这一年我做出了什么有意义的事情,那总结就有向朋友圈邀功请赏之嫌;如果这一年啥也没干,那我假惺惺地做个总结,故作痛心疾首地感叹为什么这一年啥也没干,第二天醒来依旧继续摆烂,那这样的总结似乎也就没甚意义了。
我的2022年,以六月底为分界线,被分成了两个部分。前半年主要在忙毕业的事情,说是忙,其实也没有在毕业论文中投入太多的精力,用一个随便的选题加上随便跑的实验结果,再加上随便的行文组织,没想到最后还混了个优秀毕设,反而是毕业前各种麻烦的手续,花了我 ...
CMU-15/440 Distributed Systems 6:DFS
分布式系统课程15-440学习笔记6,这一部分内容主要讲了分布式文件系统的内容。
Introduction
分布式文件系统(Distributed File System, DFS)是指部署在分布式系统中的文件系统,我们可以通过DFS提供的文件系统接口来访问存储在服务器(是一个分布式系统)上的文件。
文件系统接口提供的操作主要包括:
文件的打开和关闭,文件统计信息的读取
从文件中读/写数据
给文件上锁
删除/重命名文件/目录
查询目录下的文件列表
那么为什么要设计成DFS?
可以在多个用户之间共享数据
用户的移动性
文件位置的透明度
备份和中心化的管理
分布式文件系统面临的主要挑战有:
异构性,分布式系统中有大量不同的计算机设备和用户
规模化问题,如何扩大系统的规模
安全性,文件和数据的安全性
容错,对系统崩溃的处理方法
系统的并发性能
虽然分布式文件系统有这么多目标,但是我们在实际开发/工作/研究DFS的过程中,应该要定下优先的目标,即应该先解决哪个挑战。DFS的设计和开发过程中,有很多这样的trade-off, ...
NLP与对抗学习
这是CMU11-711 Advanced NLP课程中的一节,主要介绍了对抗学习在NLP中的应用。最近对这方面有点兴趣,希望通过学习这节课的PPT来了解一些基本的知识。课程链接https://phontron.com/class/anlp2022/schedule/adversarial.html
对抗学习Adversarial Learning
对抗学习是机器学习中的一大类方法,它的基本思路是,训练一个模型和一个对抗者(Adversary)来共同学习,达到更好的学习效果。这里面有这样几个常见的概念需要加以区分:
对抗生成网络Generative adversarial networks,即GAN,它的基本思路是让模型生成一些输出结果(比如图像和文本)并且让对抗方尝试去判断输出结果的真伪
对抗特征学习Adversarial feature learning,它的基本思路是让模型去生成一些特征,并且对抗方会尝试判断不同类型的特征
对抗鲁棒性Adversarial robustness,对抗方会尝试干扰输入模型的内容并让模型无法起到应有的作用,在这个过程中训练出更健壮 ...
浙江大学研究生课程《数据挖掘》考前速成
浙江大学计算机学院研究生课程《数据挖掘》考试重点内容的速成。
Data
关键的统计信息
Mean 平均值,进一步有加权平均值
Median 中位数
Mode 众数
Quartiles,Q1是排在第25%的数据,Q3是数据中排在75%处的数据
Inter-quartile range IQR=Q3-Q1
Variance 方差, Standard Deviation标准差
箱线图Boxplot
根据数据的五个特征:最小值,Q1,中位数,Q3和最大值进行作图,中间三个画成一个矩形区域,但是箱线图有一些缺点,比如下面这样两组不同的数据分布,他们的箱线图是一样的:
Data Similarity and Dissimilarity
枚举特征
衡量枚举特征的相似度,可以直接计算数据中相同的属性个数,再除以属性值就可以。对于一些不是二元属性的枚举属性,可以讲数据转换成多个二元属性(Yes/No),
数值特征
闵可夫斯基距离的计算方式如下:
曼哈顿距离:h=1
欧几里得距离:h=2
supremum距离:h=无穷大,计算的结果是里面最大的 ...
UCB-LinuxSysAdminDecal学习记录
UCB的Linux System Admin Decal是一门Linux系统使用的入门课程,介绍了一些最基本的Linux使用知识,从Shell脚本到操作系统和计算机网络,再到版本控制和虚拟化。总的来说可以作为了解性的课程粗略地学习一下
Shell Script
一些比较神奇的shell指令
!!表示重新显示上一条执行的命令
!:1这样的用法可以从上一条命令中获取对应位置的参数
!表示pipeline,可以连续执行命令,并且上一条的输出结果作为下一条的输入
> <表示输入输出的重定向
Bash编程的基本规则
Bash脚本中用定义好了变量之后可以用$变量名的方式来引入变量,比如我们定义a="ls",然后下一行输入$a,那么这一行的输出就是ls的执行结果,我们要以文本的形式查看变量里的内容需要用echo来输出,否则会被当成命令来执行
Bash脚本中的变量没有类型,比如我定义a=1,那么$a+1得到的结果不是2而是字符串1+1,我们可以用expr命令来实现表达式的计算,expr $a+1的结果就是2
在Bash脚本的条件判断中,0表示 ...
CMU-15/440 Distributed Systems 5:RPC
分布式系统课程15-440学习笔记5,这一节主要讲远程过程调用RPC的内容。本笔记部分内容参考了该课程的推荐教材Distributed Systems
Introduction
很多时候,分布式系统的通过进程之间显式的通信来实现各种功能,但是这样的设计完全没有隐藏通信的细节,这就导致系统的访问透明性存在问题。这个问题可以用远程过程调用(Remote precedure call, RPC)来解决。
所谓的透明性(Transparency)指的是本来是存在的事物或属性,从某种角度看好像不存在,比如说对于写Python的人而言,计算机底层汇编语言的运行情况他是不知道的,这个时候,汇编程序对这个人来说就是透明的,他不需要知道汇编的运行方式也可以写出能跑的Python代码。
RPC的原理实际上非常简单,它可以让一个程序调用位于其他机器上的procedure,当机器A上的进程调用了机器B上的procedure,那么A上的这个进程就会被挂起,并且被调用的procedure在B上开始执行,得到的结果再返回给A上的进程。这个过程中,A上的进程用调用函数的方式传递所需的参数,然后 ...
CMU-15/440 Distributed Systems 4:Mutex
分布式系统课程15-440学习笔记4,这一节主要讲分布式系统中的Mutual Exclusion问题
互斥
互斥(Mutual Exclusion)是分布式系统的关键设计点之一,我们需要保证在每个时刻只有一个代码实例可以访问临界区。互斥需要保证系统具有:
正确性/安全性,即上面说的每个时刻最多只有一个进程可以获得访问临界区的锁
公平性,任何发出请求的进程都必须有机会获得访问临界区的机会,不能出现饥饿现象
中心化的互斥
基本模型
在中心化的互斥实现方法中,需要有一台机器作为Coordinator,它负责维护一个请求队列,并根据在当前锁被上一个进程释放的时候,将这个锁重新分配给队列最前面的那个进程
image-20220813000354455
Leader选举
但是很多时候,分布式系统中没有专门的Coordinator,或者Coordinator会出现fail的情况,这个时候就需要从分布式系统的进程中选举出一个合适的进程作为Leader,这个过程可以分为这样两个步骤:
步骤1,进程P发现原本的Leader出现了fail,需要重新选举
步 ...
CMU-15/440 Distributed Systems 3:Golang and Synchronization
分布式系统课程15-440学习笔记3,这一节主要讲go语言和go语言中的并发与同步模型
并发中的一些关键概念
要解释清楚什么是并发,首先应该要知道这样几个基本的概念:
临界区Critical Section,指的是访问被共享的那部分资源的代码片段
竞争条件Race Condition,多个线程同时访问代码中的临界区并对共享的资源进行更新,导致无法预知的后果
非确定性程序Indeterminate Program,一个或者多个竞争条件,导致程序最后的输出不是确定的
互斥Mutual Exclusion,即保证每个时刻都只有一个线程/进程可以访问临界区,以此来避免竞争,同时又要保证线程/进程只需等待有限的时间,即不浪费资源,并保证访问的公平性
Golang的并发模型
Golang(即Go语言)设计了channel和go routines两种语法特性来实现它的线程模型。其中,channel的作用是用来传递信息并实现go routine的同步,同时提供回调的服务。而go routine则是由Go创建的可以独立执行的函数,并且有独立的调用栈,可以看作是一种轻量级的 ...
CMU-15/440 Distributed Systems 2:Networking Communication
分布式系统课程15-440学习笔记2,这一节主要讲网络通信相关的内容。
进程之间的交互是分布式系统中的核心,不研究位于不同机器上的进程之间的通信的分布式系统研究是没有意义的。
网络链接Network Links
网络链接是网络通信中的基本组成单位,节点指的就是一台计算机(当然有的时候一台计算机上会分出多个虚拟节点)
image-20220623172117716
如果我们需要组建更复杂的网络,就需要用更复杂的组网方式,通过网线将多台计算机连接成网络。
image-20220629235707467
复用Multiplexing是计算机网络中一种很常见的技术,即多个链接共享同一个信道进行通信,交换机在这个过程中起到了很重要的作用。
image-20220630225907847
包交换(Packet Switching)是最常见的通信方式,一个自包含(关于自包含,我的理解是可以通过数据包本身的设定来读取里面所有的内容)的数据包从起始点发出,在网络中独立地进行传播,直到抵达目的地。
但是在信道被复用的情况下,通过同一个信道传输多个不同的包 ...
CMU-15/440 分布式系统1:Introduction
CMU的15/440是一门分布式系统的入门课程,我一直对这个领域有点兴趣,想通过公开课来学习,不过MIT的6.824似乎难度较大,对我这种菜鸡不太友好,所以先找了一门听说比6.824容易一点的课来学一学。
什么是分布式系统?
分布式系统是什么?这门课程给出的定义如下:
A collection of independent computers that appears to its users as a single coherent system
也就是说,分布式系统是一个由多台独立的计算机构成的系统,这些计算机从用户的角度来看是单个系统。并且,分布式系统具有这样几个重要的特征:
没有共享内存,不同的计算机之间通过消息进行交流通信
每个计算机在它本地的操作系统上运行
系统计算机之间具有异构性
但同时,分布式系统会隐藏内部的各台计算机的组织架构和通信方式,对外的表现就像是单台计算机一样,并提供通用的接口供外部调用。同时,分布式系统具有较好的可扩展性和故障恢复能力,可以自由地增加/减少计算机的数量并且在其中的某一台计算机出现故障的时候用其他的计算机 ...
一个Python助教的学期总结
一个Python助教的学期总结
俗话说的好,你要是觉得xx不好,你就去建设它。上个学期我曾在98发过一个帖子,简单概括了我对本科教学的一些看法,也引起了一些讨论。我在里面曾提到本科教学的一大弊病是助教不足,所以这个学期我报名去担任了《Python程序设计》这门计算机通识课程的两个班的助教,来简单说一下我在担任助教过程的一些所见所闻。
首先说明一下,《Python程序设计》并不是专业课,而是一门面向非计算机专业的通识课程,因此我所在的班级基本什么专业的同学都有,当然也有一些计院的同学来刷分的。这门课程讲的东西实际上非常少,主要就是最基本的一些python语法和简单的python程序编写,我觉得这门课主要的难点在于应付期末理论考试而不是做出编程题。我在担任助教的这段时间里也主要负责为同学解答编程题方面的问题。这个过程中,我发现,事情没有我所想的这么简单。
先分享几个担任助教过程中遇到的有趣的事情,每个故事我都起了一个小标题:
开门大吉
刚开学的时候,需要安装Python以及相关的开发环境Thonny,一个月过去之后仍然有非常多的人不会用Thonny,包括很多基本的操作比如如何创建 ...
MIT6.033系统设计2:计算机网络
MIT6.033这门课程的主题是Computer System Engineering,即计算机系统工程,这门课程主要教授计算机系统设计相关的知识,内容涵盖了操作系统、计算机网络和分布式系统等多个计算机系统的子方向,内容比较全面。虽然这门课没有公开的作业,但还是值得一学,由于每节课的PPT内容较少,我们将内容按照操作系统、计算机网络和分布式系统三个大块进行记录。现在是第二部分计算机网络的内容。
网络的层级结构
很多时候,一台机器承载不了一个完成的系统,这时候我们需要将一个系统部署在多台机器上,而计算机网络中的各种通信协议就是为了完成机器 之间的交流而设置的。
image-20220514101058436
网络是对计算机之间连接的一种抽象,网络由一系列端点(即计算机设备)和交换机通过一系列的网络链接组成。网络系统中,各种各样的网络协议在机器通信时起到非常关键的作用,并且各种各样的网络协议被分成了若干层,自上而下依次有应用层、传输层、网络层和链接层(相当于OSI七层体系中的下四层,在TCP/IP体系中也叫做网络接口层),每个层都是对网络协议具体功能的抽 ...
MIT6.033系统设计1:导言与操作系统层面的设计
MIT6.033这门课程的主题是Computer System Engineering,即计算机系统工程,这门课程主要教授计算机系统设计相关的知识,内容涵盖了操作系统、计算机网络和分布式系统等多个计算机系统的子方向,内容比较全面。虽然这门课没有公开的作业,但还是值得一学,由于每节课的PPT内容较少,我们将内容按照操作系统、计算机网络和分布式系统三个大块进行记录。
引言:系统设计中的复杂性,模块化和抽象
这门课讲述的内容是系统设计(主要指的是计算机系统),我们就首先需要搞清楚一个问题——什么是系统?对此,6.033这门课程给出的定义是:
a set of interconnected components that has an expected behavior observed at the interface with its environment
这门课认为系统是由一系列内部相关联的组件构成的集合,并且可以在某种合适的环境下,通过它提供的接口可以观察到某种期望的表现。而搭建一个系统的难点就在于,系统的复杂性。系统的复杂性限制了我们的设计。
...
CMU10-708概率图模型3:Exact Inference
CMU10-708的Lecture3,主要内容是介绍概率图模型中的因子图和精确推理等内容
因子图Factor Graph
因子图提供了一种同时可以用来表示有向图模型和无向图模型的方法,它将概率图模型中不同变量之间的联合分布转化成因子的势能函数之间的乘积。它可以用在马尔可夫随机场(无向图模型),条件随机场和贝叶斯网络(有向图模型)等多种不同的概率图中,非常General
因子图的生成方式如下图所示,对于有向图模型,我们可以将图模型中所有的联合概率分布转换成对应的因子,同时入度为0的节点(即不受其他点的概率分布的约束)还有自己对应的因子,因为这些节点自己就是一个边缘分布,而在无向图模型中,所有的最大团可以转换成一个对应的因子。
image-20220331223007259
我们可以将一系列因子表示为,最终整个图模型的联合概率分布可以被转化成: 这里的Z是归一系数。我们可以先通过一些例子来看因子图的转化。
例子1如下图所示,这是一个有向图模型,再转化成因子图之后,原本的联合分布中一定会出现的条件概率分布就可以转化成因子对应的势能函数
imag ...
MIT6.830数据库系统-lab4:Transaction
MIT6.830 Database Systems课程Project的第四部分,主要实现一些事务处理和并发相关的功能,我们需要为SimpleDB设计一个二阶段锁的管理器
Overview
在开始这个lab的coding之前,我们先来复习一些数据库中的基本常识。事务是数据库中一组原子操作的集合,原子性指的是事物中的一系列操作只能被完全执行,或者完全没有执行,不能出现只执行了其中部分操作的情况。数据库中的事务具有ACID四个特点:
原子性:就是上面说的,一个事务只能被完整的执行或者不执行
一致性:在事务开始之前和事务结束以后,数据库的完整性没有被破坏
独立性:数据库允许并发,但是多个事务之间不能互相影响,不能因为并发事务的交叉执行导致数据库的不一致
持久性:事务处理结束后,对数据的修改就是永久的,即便系统故障也不会丢失
而为了实现事务的这些特性,数据库往往采用被称为“锁”的机制来实现。锁代表了事务对数据表的访问权限,经典的共享锁和排他锁基本使用规则如下:
如果一个事务要对一个对象进行读操作,就必须持有它的共享锁
如果一个事务要对一个对象进行 ...
CMU11-877 AMML2:Multi-modal Interaction
CMU的公开课程11-877《Advanced Topics in MultiModal Machine Learning(AMML)》课程的学习笔记,这门课程以读各种各样的论文为主,没有什么平时作业。第二周要读的论文主要是几片研究多模态模型的可解释性的(个人理解,这几篇论文都在研究多模态模型是否真的学到了模态的交互信息)
如何判断多模态模型的模态交互能力
第一篇论文是发表在EMNLP2020上的《Does my multimodal model learn cross-modal interactions? It’s harder to tell than you might think!》这篇论文提出了一种通用的检验多模态机器学习模型是否学到了跨模态交互能力的方法。
论文提出,多模态的机器学习模型可以分成两类,一类是模态相加式的模型,这类模型我们可以将它统一表示为: 这里的t和v分别代码数据的文本特征和图像特征(假设只有文本和图像两个模态),这种模型对数据的不同模态特征分别单独进行编码。
而另一类模型是有模态交互的模型,这类模型会对数据不同模态的特征进 ...
CMU11-877 AMML1:Introduction to Multi-modal Learning
CMU的公开课程11-877《Advanced Topics in MultiModal Machine Learning(AMML)》课程的学习笔记,这门课程以读各种各样的论文为主,没有什么平时作业。第一周主要阅读两篇综述论文,分别是表示学习的综述《Representation Learning: A Review and New Perspectives》和多模态机器学习的综述《Multimodal Machine Learning: A Survey and Taxonomy》,不过因为是综述,所以我没有特别仔细阅读,主要就是了解个大概。
表示学习Representation Learning
表示学习(Representation Learning)是机器学习领域的经典话题,它的目的是通过学习到的模型,将输入的数据转化成一个对应的表示(可以是向量,这种向量也叫做数据的嵌入Embedding),这种方法在机器学习的很多领域都得到了比较广泛的应用。
这是因为机器学习模型实际上只能处理数值的运算,而模型的输入可能是图像、文本、语音、视频等各种形式的数据,模型 ...
MIT6.830数据库系统-lab3:Query Optimizer
MIT6.830 Database Systems课程Project的第三部分,我们需要实现一些数据库系统中的查询优化的功能,使用数据库提供的统计信息来对嵌套的Join操作进行优化
Overview
MIT6.830的lab3中,我们主要需要实现一个基于cost的查询优化模块,这个模块的主要作用是在SimpleDB处理Join等SQL语句的时候可以对输入的SQL查询进行优化,并且我们这里实现的是最简单的基于cost的查询优化模块,这里的cost会根据SimpleDB中数据表的统计信息计算出来,而这种统计信息就来自于之前实现的存储模块。
SimpleDB中,整个查询优化模块的架构如下图所示:
在这个lab中,我们首先要实现TableStats这个类来计算每个表的统计信息,然后进一步实现Join操作的查询估计和嵌套Join的优化这两个核心功能,下面就让我们进入正题。
数据表的统计信息
我们首先要来实现统计一个直方图类IntHistogram和StringHistogram,用来统计一个表的一列的数据分布情况,然后用每个列对应的这个统计表来组成整个数据表的 ...