Lucius Blog

「适志于道寄骸于迹而无往不欣」

对比学习 (Contrastive Learning) 发展历程 - 综述

本文为「对比学习论文综述」的笔记，其中将对比学习分为了以下四个发展阶段：百花齐放 CV 双雄不用负样本 Transformer 其中涉及到的一些方法，具体关系如下：百花齐放 InstDisc (cvpr18) 把每一个个体当作一个类别，学一种特征将每一张图片都区分开，进而引...

Posted by Lucius on March 18, 2023

二进制哈希码快速搜索：Multi-Index Hashing

哈希方法通常包含两个部分：【编码】将元素通过「data-dependent」或「data-independent」的方式映射为二进制，并通过比较二进制码的汉明距离 (hamming distance) 来搜索相似元素；【搜索】由于二进制码往往比较长（例如 64, 128, 256 bits），采用直接映射的方式，通常找不到任何元素，因此通常考虑找汉明...

Posted by Lucius on March 11, 2023

演化算法：乌鸦搜索算法 (Crow Search Algorithm)

在机器学习中，我们所要优化的问题很多时候难以求导，因此通常会采用一些演化算法（又称零阶优化 / 黑盒优化）来近似求解。这些演化算法通常是根据一些生物的行为置顶，有如下分类：本文所要介绍的乌鸦搜索算法 (CSA) 就是其中的一种，属于演化算法。乌鸦搜索算法乌鸦搜索算法受乌鸦的行为所启发，即在乌鸦种群中，每只乌鸦都在干三件事：寻找藏食物的地点； ...

Posted by Lucius on March 7, 2023

层次聚类：BIRCH 聚类、Lance–Williams equation、BETULA 聚类

BIRCH 聚类 BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) 算法要求数据为向量形式，其通过构建 CF-tree (Clustering Feature Tree) 实现可扩展地高效聚类，具体来说，每个簇存储一个三元组： $$ CF=(N,\text{LS},\text{SS}), $$ ...

Posted by Lucius on March 7, 2023

软聚类算法：模糊聚类 (Fuzzy Clustering)

在介绍模糊聚类之前，我们先简单地列举一下聚类算法的常见分类：硬聚类 (Hard Clustering) Connectivity-based clustering (Hierarchical Clustering) Centroid-based Clustering (k-means clustering) De...

Posted by Lucius on March 6, 2023

k-Medoids 聚类系列算法：PAM, CLARA, CLARANS, Trimed, BanditPAM

$k$-Means 作为一种经典聚类算法，相信大家都比较熟悉，其将簇中所有的点的均值作为簇中心，整个过程采用欧式空间中的距离度量。不同于 $k$-Means，$k$-Medoids 将距簇中所有点距离之和最小的点作为簇中心，如下所示： $$ \operatorname{medoid}(C):=\underset{x_i \in C}{\arg \min } \sum_{x_j \in C...

Posted by Lucius on March 4, 2023

变分推断 (Variational Inference) 解析

变分推断在贝叶斯方法中，针对含有隐变量的学习和推理，通常有两类方式，其一是马尔可夫链蒙特卡罗法 (MCMC)，其通过采样来近似估计后验概率分布；其二是变分推断，通过解析的方法近似计算后验概率分布。假设联合概率分布 $p(x,z)$，其中 $x$ 是观测变量，即数据，$z$ 是隐变量，目标是学习后验概率分布 $p(z\mid x)$。由于 $p(z\mid x)$ 通常非常复杂，难...

Posted by Lucius on March 1, 2023

O(1) 的离散概率分布采样方法 - Alias Method

Alias Method 给定一个离散概率分布 $p=[0.3 \ 0.2\ 0.4\ 0.1]$，现要对该分布进行采样，最直接的方法是随机一个 $[0,1]$ 之间的数 $v$，从左往右比：若 $v\leq 0.3$，则采样类别 $A$；若 $v>0.3$，则和 $0.5=0.3+0.2$ 对比，若比 $0.5$ 小，则采样类别 $B$； ...

Posted by Lucius on February 27, 2023

哈希函数的学习算法整理

概述哈希函数学习的两个步骤：转为二进制编码：可以先降维成实数，再转为二进制，也可以直接学习一个二进制编码；学习哈希映射函数：基于二进制编码设计或学习哈希方式，使得相似元素靠近，不相似元素远离。根据哈希函数性质，可做如下分类：数据无关的方法 (Data-Independent Methods) 特点：哈希...

Posted by Lucius on February 23, 2023

最大化内积搜索相关研究 (Maximum Inner Product Search, MIPS)

MIPS 问题即在一个向量集合 $\mathcal{S}$ 中，找到一个与查询向量 $q$ 内积最大的向量 $z$，即： $$ z=\mathop{\arg \max}\limits _{x \in \mathcal{S}} x^\top q. $$ 这是一个非常困难的问题，本文罗列了部分与其相关的资料。 Background 首先介绍一下局部敏感哈希 (Locality Sen...

Posted by Lucius on February 22, 2023