EE364a 凸优化学习笔记

课程介绍 EE364a 课程主页:提供了教材和 slides、往年试卷等资料 Convex Optimization edX 课程页面:可以跳转 YouTube 用双语字幕插件学习,同时提供了课程讨论区 CVXPY:一个基于 Python 的凸优化库 Lecture 1 Introduction Mathematical optimization 最优化 优化问题:在一些约束的情况下,最小化一个目标函数 记法:$f_0(x) → min\ s.t.; f_i(x) \le b_i$ 把 min 和 s.t. 当做 attribute 属性名而不是单词 $x$:优化变量/决策变量 $f_0$:目标函数 决策如何 irritate 刺激 $f_i$:约束 另一种 interpretation 就是资源 $b_i$就是 budget 举三个例子: 投资 约束:预算、最大最小份额 目标:风险或者回报 电路设计 约束:制造工艺、频率、空间 目标:最小功率 机器学习 约束:先验知识、参数之间的耦合 目标:优秀的模型 一般的最优化问题,不是导数为零那么简单,方法都有些妥协(时间复杂度、不是总能找到解) 例外:一些经典问题,如最小二乘、线性规划、凸优化 Quiz The symbol x* usually denotes a solution Least-squares and linear programming 最小二乘和线性规划 最小二乘也叫 regression 回归 时间复杂度和$n^2k$成正比,$k$可以是案例数量、数据数量,$n$可以是特征、回归量 一个成熟的算法,200 年了...

March 30, 2021

《塞尔达传说 荒野之息》:游戏背后的艺术

2019 年 7 月入手了《塞尔达传说 荒野之息》卡带,到现在游戏时间断断续续 100+h 却一直没有去挑战最终 boss——冒险如此引人入胜,以至于我刻意回避主线剧情,不愿意让这场旅行结束。塞尔达传说也确实没有让我失望,每一次打开游戏都会给我新的惊喜。 前天下午,我在海拉鲁平原驯马的时候,意外触发了主线,找到了塞尔达公主的最后一段回忆——《绝望》。 公主的回忆——绝望 这一次我没忍住眼泪,丢下滑稽的怪物头套,换上最正式的装备,带上四英杰武器,直奔城堡。一路屠杀,打败盖侬,解救公主,是的就是这么快,盖侬城堡的谜题对于这位身经百战的勇者来说早已不是难题,紧接着就是片尾、鸣谢…… 而在这个时候,我发现游戏进度并不能保存,重开游戏发现唯一的变化只是附在存档页面上的一个小小的白色五角星。再次跑进城堡,盖侬还在,四英杰仍然在神兽体内,公主还是没有被拯救。 我好像突然失去了继续游戏的动力。曾经以为,通关之后可以在二周目去看看修复后城堡的辉煌,到公主房间里偷看日记,在没有守护者的大草原上骑马,去宁静和谐的一始村看看到底有没有我的房子,去找那些沉迷于勇者神话的 NPC 夸夸我。但这些期待原来只是幻想,一次次试炼都是徒劳,游戏的结局已经无法改变。 THE END 于是就这样,意外地结束了海拉鲁大地上的旅行。 为什么会喜欢《塞尔达传说》 终于放下剧情之后,我开始思考塞尔达这款游戏究竟有什么魔力。 看了 【中字】塞尔达传说 荒野之息 开发纪录片全三部合集,我尝试跟着开发者的思路,开始解剖这款游戏。 自由 “开放世界”这个概念好像有点烂大街,但《塞尔达传说 荒野之息》真的不一样。 如 游戏开发方式的改变,造就了《塞尔达传说 荒野之息》 这篇文章提到的,在 CEDEC 2017 游戏开发者大会演讲中,来自任天堂的藤林秀麿和米津真抛出“引力”、“大地图三角形法则”、“3 把尺”三大概念。 首先介绍的是“因为大所以显眼”,也就是基于尺寸的引力。 远远就能看到的独特地形,刺激着玩家的探索欲望,让他们觉得“也许有什么东西在那”,所以具有很强的引力。同样地,塔也是从远处就能看到的设施,因为对获取游戏世界广范围信息来说非常有用,所以也会吸引喜欢探索的玩家。 尺寸产生的引力的大小 另一方面,对于一心想要“提升自己在游戏世界里的体力”的玩家来说,打通后能够得到心之碎片的祠或许有着更强的引力。而想要“得到更强力的战斗装备”的玩家,则会认为得到稀有武器机会较高的怪物要塞(敌人基地)具有更强的引力。 对于一心想变强的玩家来说,引力的大小大致如图 此外在游戏世界进入夜晚之后,会发光的设施会变得更加显眼,因此引力也会有所变化。 晚上会发光的东西更加显眼。从“被光线所吸引”这层意思上看,玩家或许跟虫子类似!? 地图中的地形起伏基本都参考了三角法则,大概这就是常常让我感到“柳暗花明又一村”的奥秘;“3 把尺”指的是距离感、密度感、时间感,为了设计一个合理的“世界”,开发者参考了真实地图中便利店、邮筒的密度,各种旅游景点的游玩时间,好像真的能想象到他们拿着地图在京都四处测绘的样子。 关于关卡流程的设计,还找到了另一篇更专业的文章——运用关卡结构图分析《旷野之息》的关卡设计。 游戏其实和解决问题是密不可分的,Jesse Schell 在《游戏设计艺术》一书中就把游戏定义为“以一种嬉戏态度进行的解决问题的活动”。所有游戏里面都包含着许多问题让玩家去解决。如果问题只能按照设计者预设的答案来解决,玩家其实只是在被动地寻找唯一的解,这就可能会让获得成就感变得困难。甚至玩家会一直失败,造成了卡关。《旷野之息》的制作人藤林秀麿在 2017 的 GDC 的演讲上就提出: 希望把一直以来的被动游戏模式,转变为玩家自己的主动的游戏方式。 玩家尝试着使用自己思考得出的答案去解决问题,只要游戏给予积极的反馈,那无疑是对玩家努力的肯定,所以玩家获得的成就感也就更为强烈。而玩家获得了成就感后,也会主动去寻找下一个问题并继续思考解决。 就像《旷野之息》的技术导演堂田卓宏在 2017 的 GDC 上说的: 希望大家可以靠想象力享受各种解谜,希望大家能够享受“啊啊,我真是天才!”的瞬间。 这就是《旷野之息》带给玩家的解决问题的快感。 交互 交互,元素与元素之间的交互,我觉得是塞尔达最核心的部分。这些交互一方面充满游戏魔幻色彩,“冰箭”“法杖”“古代科技”,很多操作逻辑都从此展开,很多游戏乐趣也来源于此;另一方面这些交互细节又很真实,偶尔会蹦出一些创造性的想法,随手一试却发现真的可以实现。 简单列举一些元素交互: 火:点燃草地制造上升气流、通过火把的火焰判断风向、用金属武器和打火石制造篝火、一觉醒来篝火被雨水浇熄、点燃木制武器制造伤害加成、火山的高温岩石可以烤熟食物。 电:手持金属武器会被雷劈、把金属武器丢在怪物脚下大喊雷公助我、电属性箭在雨天能产生范围伤害、用属性武器在河里电鱼。 水:下雨天 NPC 都会抱着头跑回屋里、雪山顶上推下去的石头会滚成大雪球、火属性攻击在雪山上能产生更高伤害、裸泳比穿着普通衣服速度会更快。...

February 21, 2021

2020 | 庚子鼠年

相比元旦,更喜欢在农历新年给自己做个总结——大人们总有忙不完的事,表弟表妹们则有手机照顾;我早已过了写寒假作业的年龄,于是就可以顺理成章摸鱼了。 生活剪贴 升学 上半年的情绪或许就是那两个字——焦虑,peer pressure 非常有效,日常在“这背景也太强了我不想学了”和“他这样都过了我还能再努力一下”之间反复横跳。大半年过去,很多事的印象都模糊了,一些当初的抉择现在也有了不同的看法。不过,1 月份坐高铁回家时又怎么会想到 2019-20.03 学期会变成这个样子呢? 感谢那段时间互相鼓励的朋友们,大家带来的 peer relaxation 很关键。也要感谢我的父母,虽然他们的消息可能会有些滞后,会带有一些年代色彩,但出发点永远都是我。 不管怎么说,结果还是幸运的。升学的故事后来还改成了鸡汤,灌给了不少人。「局部最优解,放在一生来看,也不一定是全局最优。」还挺有道理的。 四牌楼 从湖区搬到牌区大约是八月底九月初,想着自己终于成为城里人了,我激动地开了好几个文档——《四牌楼觅食指南》、《南京旅游笔记》,一学期下来也写了不少内容,很欣慰。 游客穿过四牌楼校区正大门,拍下的第一张照片一定是中央大道的梧桐树。以前一直觉得牌区的梧桐很神秘,和别的地方相比,那片梧桐主干分叉的位置特别低,但又特别整齐。听小轩说“顶端优势”、“生长素”之类的才恍然大悟,后来再看这些梧桐时,就会去幻想他们分叉时的那个年代。 逸夫楼 14 层的厕所可能是牌区视野最好的地方之一,西面北面都有窗口,能看到近处大礼堂的绿顶、远处的紫峰大厦,能一直看着梧桐树从绿变黄再变白。除此之外还有交通学院楼顶、吴健雄实验室楼顶……是的还是这么喜欢爬楼。 疫情影响,普通市民都没法进校园,一下子少了很多锻炼的身影,而我原本计划的参观南京各大校园也只能作罢,遗憾。 生活体验派 曾经以为遥不可及的“线上社会”,比想象中来得早了不少。这给我带来的最大感触并非科技的力量,相反,而是重新发现“面对面”的重要性。 情绪始终是难以数字化的,显示器和音响只是承包了你的视觉(还是平面的)、听觉,而嗅觉、触觉、味觉之间的交互也是体验的重要一环。以前觉得放弃温暖被窝、冒着寒风爬山只为了等着太阳升起真的没意思;但当我真的站在山顶,俯瞰城市的灯光,天空的颜色肉眼可见地变化,耳边的欢呼声祝福声响起,才知道“看日出”的重量。 “生活体验派”这个词是小寇提的,这半年自己做得还算不错——做饭,健身,学羽毛球,看小原的演出,学吉他,在闲鱼当个卖家,给车换备胎,上大舞台演讲……不同的角色为生活增加了很多新奇体验,也确实帮助我在思考时多了一些维度。遇到一些神秘的人物、习惯,更多次发出“原来如此”的声音;看《观视频工作室》点评的社会现象时偶尔也能跟上思维的脚步。 金榜题名 Best Buy AirPods 为了 AirPods 买了 iPhone,结果就是忍不住还想买全家桶。当年那个高喊“索尼大法好”的同学,怎么转手就把索尼降噪豆卖了,怪了。 3D 打印机 拥有一台 3D 打印机是怎样的体验 NR200 人生第一台 ITX 主机,白色太美了 李宁 WS72 羽毛球拍 又菜又爱玩,希望明年能找到新的球友 DJI Mavic AIR 2(租借) 项目做得越多越能理解这些产品背后的技术含量;攒了很多素材没剪,下次一定 棱镜「我想以世纪和你在一起」2020 年度演唱会 感谢棱镜乐队的伴奏「在自己的路上 义无反顾地狂奔吧」 招商中证白酒指数 酱香型科技,不说了,卖得太早了 Best Watch 《切尔诺贝利》 《寄生虫》 《调音师》 《暴裂无声》 《半泽直树》 Best Play 健身环大冒险 两只 JOY-CON 的数据采集和判定很巧妙,热身、放松等剧情细节也很丰富,后来真正走进健身房也有他的一份功劳。可能是继《塞尔达传说》之后又一个入手 Switch 的理由,记得当时还一度被炒成理财产品。“任天堂就是世界的主宰!”...

February 11, 2021

拥有一台 3D 打印机是怎样的体验?

买一台自己的 3D 打印机大概是 去年寒假时候 的想法,后来朋友推荐了荷兰 Ultimaker 公司的开源方案,成本不高,其配件也能在淘宝买到,于是狠狠心付款下单,花了三天时间组装调试,完成一台十字结构双 Z 轴的 FDM 打印机。 所以拥有一台 3D 打印机是怎样的体验? 缺个手机壳缺个手机架,自己打印;看到不错的手办,自己打印;DIY 的产品缺个外壳,自己打印;正式加工前想检查下装配、干涉,也可以先用塑料打印一个。凡是你想得到的,都能花几个小时造出来。原本担心自己会再一次三分钟热度,让机器吃灰,没想到大半年下来机器利用率相当高,光耗材就已经买了七八卷了。3D 打印机可以说一定程度上改变了自己的工作方式,真的很妙!🙉 问题回答完了,下面分享一些使用经验。 基本参数 外观尺寸:358*428*498 打印行程:223*223*300 耗材:以 PLA 为例,大约是 70 元/千克 功率:约 200W(室温 10℃,热床 75℃),大约一毛钱每小时 噪音:正常运行房间里大约能测到 60dB,如果放进柜子做好减震隔音,宿舍 24 小时打印也是没问题的 代打:网上价格一般在 0.4 元/克左右,这样一算其中利润大概有数了 建模 建模用的是 SolidWorks,当选择 3D 打印作为成型方式时,建模过程中也需要相应调整一些细节,比如 3D 打印零件和螺丝怎么组 CP 才科学??;还有合理拆分零件,考虑强度需求,也要减小悬空部分,提高打印效率;针对打印机的行程、精度,量力而行,提前做好预期。 如果不想自己建模,也可以上 Thingverse 看看,很多有意思的模型分享(最近访问好像很不稳定)。 切片 切片这一步骤的输入是建模得到的 STL 等格式的模型,输出是 G-code 这种最为广泛使用的数控编程语言,给 3D 打印机执行。切片软件使用的是 Ultimaker Cura,因为公司的开源精神,这个软件生态挺不错,一直都在频繁迭代更新,经常会出一些试验性功能。 FDM 打印机的原理为层层堆积形成实体,每一层的运动路径是在计算机中生成的。为了生成这些路径,首先必须知道每一层的形状,即用水平面去切割模型,得到轮廓。外壳一般来说需要一个厚度,即所谓的壁厚。而对于每一层来说,将轮廓线重复打印几圈,即可构建一个比较厚的圈线。为了使模型具有一定的强度,需要在内部打印一些填充结构,具体操作就是在每一层的多边形内部加上一定模式的填充,如三角形、蜂窝等。最后,很多层堆积起来构建了一个实体,把每一层的路径组合起来,就得到了整个模型的路径,即所谓的 G-Code 文件。可见,模型打印有一些最基本的参数,包括层厚、壳厚、填充模式、填充密度等等。为了兼顾打印的效果、稳定、效率,这些参数可能要根据打印机的具体情况,多次调整尝试才能定下来。 同时 Cura 也有一些特殊处理,对于模型来说顶部和底部一般要求比较结实,因此 Cura 默认对顶部和底部的几层打印实心(100%填充)。 而打印模型就像盖房子一样,在空气中打印,对于悬空的地方是不能直接打印出来的。盖房子需要脚手架,3D 打印也需要支撑结构。Cura 在生成路径文件时,也会自动生成支撑结构,帮助成功打印模型。...

January 30, 2021

从接网线到科学上网——通信网知识总结

时间证明,学了《通信网》这门课带来的帮助远不止接路由器。写一篇博客整理一下各种零碎的知识点。 bit,比特,二进制位;Byte,字节,处理的基本单位;1Byte=8bit。网速用 b,硬盘用 B。 分层模型 OSI Model 互联网协议入门(一)——阮一峰的网络日志 http://www.ruanyifeng.com/blog/2012/05/internet_protocol_suite_part_i.html 互联网协议入门(二)——阮一峰的网络日志 http://www.ruanyifeng.com/blog/2012/06/internet_protocol_suite_part_ii.html 小白也能看懂的网络基础 03 | OSI 模型是如何工作的(HTTP 请求范例) https://sspai.com/post/64659 Physical 物理层 发送和接受原始比特流(0 和 1),定义了网络设备机械特性(光缆/电缆、引脚数量)、电气特性(电压大小)、传输方式(全双工)、信道复用。 Data Link 数据链路层 单纯的 0 和 1 没有任何意义,必须规定解读方式:多少个电信号算一组?每个信号位有何意义?这就是链接层的功能,它确定了 0 和 1 的分组方式——帧,即标头(Head)+数据(Data)。 标头中包含的地址是 MAC 地址,实现在同一个子网下面的广播(物理寻址) 差错控制(检测比特错误,奇偶校验、CRC 校验)(纠错由传输层解决) 流量控制(针对发送方,停等、Go-Back-N、选择重传) Network 网络层 规划 IP 地址(ipv4 和 ipv6 变化只会影响网络层),区分不同的计算机是否属于同一个子网。解决不同子网传输,就是逻辑寻址,确定最佳的数据传输路径(路由)。 ARP 协议、DHCP 协议 Transport 传输层 负责端到端通讯,“端口”(port),给每一个使用网卡的程序分配编号。每个数据包都发到主机的特定端口,所以不同的程序就能取到自己所需要的数据。 TCP/UDP 协议、流量控制(大文件分块)、差错控制(端到端) Session 会话层 会话层接收到表示层传来的数据信息后,负责在数据传输中设置和维护两台计算机之间的通信连接,以保证这段连接不会因中断而造成不必要的麻烦。 Presentation 表示层 将来自应用层的数据转换成所有计算机都通用的标准格式,并对数据进行压缩、加密。 Application 应用层 应用层即用户和计算机交流的场所,直接为用户的应用进程(例如电子邮件、文件传输和终端仿真)提供服务,如 HTTP、SMTP、FTP、DNS 等。 网络设备 入网指南 01 | 一文读懂你身边的「网络」 https://sspai....

January 23, 2021