定义

• P Problem: 任意性，对于任意的输入规模n，问题都可以在n的多项式时间内得到解决；
• NP(Non-deterministic Polynomial) Problem: 存在性，可以在多项式的时间里验证一个解的问题；
• NPC(Non-deterministic Polynomial Complete) Problem: 满足两个条件 (1)是一个NP问题 (2)所有的NP问题都可以约化到它。可以理解为NP的泛化问题。
• NP-Hard Problem: 满足NPC问题的第二条，但不一定要满足第一条 —> 不一定可以在多项式时间内解决的问题

搞笑版P=NP证明

反证法。设P = NP。令y为一个P = NP的证明。证明y可以用一个合格的计算机科学家在多项式时间内验证，我们认定这样的科学家的存在性为真。但是，因为P = NP，该证明y可以在多项式时间内由这样的科学家发现。但是这样的发现还没有发生（虽然这样的科学家试图发现这样的一个证明），我们得到了矛盾。

ppt

Pipeline

design features for nodes/link/graphs —> obtain features for all data —> train an ML model —> apply the model

Intro

• title: Machine Learning with Graphs
• year: Fall 2021
• CS224W page
• note、note中文翻译
  Read more »

Background

Why Threads?

• I/O concurrency
• multi core parallelism
• convenience for, like routine

Backgorund

• big data
• lots of kv data stuctures, like inverted index

Method

Abstract view

C++的内存分配方式

• 全局/静态变量区
• 常量存储区
• 栈：在局部变量和函数参数在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是栈的内存容量有限。
• 堆：由new分配的内存块，需要手动通过delete来释放。如果没有delete，那么在程序结束后，操作系统会自动回收。
• 自由存储区：由malloc等分配的内存块，和堆是十分相似，不过它是用free来结束自己的生命的。

相同点

• 三者皆使用连续内存，且array和vector的底层由自建数组实现
• 都可以用下标访问

[TOC]

原贴

卷积神经网络

• 卷积神经网络大致就是covolutional layer, pooling layer, ReLu layer, fully-connected layer的组合，例如下图所示的结构。
  

• 转载自胡神的“自学CS路线、资源推荐”
• 名校公开课程评价网

目标检测

定义

• 图像识别+定位
• 识别：分类问题，准确率
• 定位：分类/回归问题，找到一个框/4个坐标，IOU

传统目标检测

用回归做定位问题

• 训练一个cnn网络，在最后一个卷积层后分两个head，一个head做分类，另一个回归
• 先fine tuning分类任务，再fine tuning回归
• 缺点：回归问题，很难做

用分类做定位问题

• 滑动窗口（选择不同位置不同大小的区域），对其定位，对每个框内的图像做分类
• 缺点：窗口冗余、复杂度高、多物体多分类时复杂度更高