终于把微软BING搜索-SPTAG算法的原理搞清了
作者 | beyondma
转载自 CSDN 博客
近日，微软在GitHub上开源了其BING的搜索算法SPTAG，github地址：https://github.com/microsoft/SPTAG。这个算法笔者简单看了一下，的确是很有价值可以看大家介绍下，这种称为SPTAG （Space Partition Tree And Graph）目前的翻译多称为“空间分区式的树和图”，其实个人认为这种说法不太准确，其实这里的图与图论中的图意思一致，表示的是连接关系，并不是图像的意思，，而且我们一会仔细也会发现其算法中还带有平衡（balance)的概念，感觉译为”高维空间平衡树“更为准确。
SPTAG能做什么
微软在github上的介绍中给出的官方解释如下“This library assumes that the samples are represented as vectors and that the vectors can be compared by L2 distances or cosine distances. Vectors returned for a query vector are the vectors that have smallest L2 distance or cosine distances with the query vector. "
简单解释一下，就是微软认为图像、声音文字都能被表示为向量，而且可以用L2距离及余弦距离（cosine distances）表示其关系。这段我给读者解释一下，什么叫可以用余弦距离表示向量之间的关系。
图1.北京地图
图2.中国地址
图3.华盛顿特区地图
图4.美国地图
那么如果我把上述这四个图都转化为了向量，那么会有
vec图2-vec图1=vec图4-vec图3
也就是说在图片转化为向量后，向量的位置关系保留了其图片含义所代表的逻辑关系。这就是”L2距离及余弦距离（cosine distances）表示其关系“的具体解释。
不过这次微软并没有公开把图片、声音及文字转化为向量的技术，目前文字转化为向量的主要技术是word2vec算法，图片转化为文字的技术，读者也可以通过Facebook前些时候公开的Pytorch-Biggraph算法来了解，具体可参考我之前的博客https://blog.csdn.net/BEYONDMA/article/details/90114016
那么说到现在我们可以了解SPTAG算法工作的前提就是将已经将用户搜索的要素转化为了正确位置上的向量，SPTAG就是要找到这个向量在空间上的最近邻，说到这读者是否对SPTAG的工作方式有了更进一步的认识了呢。
SPTAG工作原理简述
对于搜索算法有了解的同学可能都会了解，搜索算法中一般有索引（index)和查寻(search)两个重要部分组成。SPTAG的索引（index)算法是基于kd-tree的。
kd-tree听起来很高大上，其实他在于一维空间上的情况就是”平衡二叉树“，在高维空间上kd-tree会用第k维的大小来决定一个元素应该插入左子树还是右子树，同时为保持tree的平衡，剩余未进入tree的元素除第k维外方差最小。SPTAG正是以此来加速算法的速度。
kmeans其实就是一种自动聚类的方法，算法先随机指定选取K个点做为初始聚集的簇心,分别计算每个样本点到 K个簇核心的余弦距离，找到距离最近的核心点，将它归属到对应的簇，所有点都归属到簇之后， M个点就分为了 K个簇。之后重新计算每个簇的重心，将其定为新的“核心”，重复上述步骤直到新核心不再改变为止或者改变距离达到一定值后中止。那么最终的K个簇就是最终的聚类结果。
SPTAG 正是集合了kd-tree 和 kmeans 两种算法的精华，才允许用户利用深度学习模型在几毫秒内搜索数十亿条信息。
原文：https://blog.csdn.net/BEYONDMA/article/details/90578111
（*本文为 AI科技大本营转载文章，转载请联系作者）
◆
公开课精彩推荐
◆
本次课程将会介绍如何利用TensorRT加速YOLO目标检测，课程将会着重介绍编程方法。本次课程还会涉及到 TensorRT 中数据类型，流处理，多精度推理等细节的展示。本次课程特色是讲解+示例分享。本次课程中，QA也是一个非常精彩的环节。
推荐阅读
拍照技术烂？实时在线AI构图模型VPN，让你变身摄影大神！
继往开来！目标检测二十年技术综述
阿里巴巴杨群：高并发场景下Python的性能挑战
为Python回测代码提升10倍性能，具体做了哪些？
鸿蒙将至，安卓安否？
面试阿里，我还是挂在了第四轮……
独家对话V神! 质疑之下的以太坊路在何方?
那些去德国的程序员后来怎么样了？
你点的每个“在看”，我都认真当成了喜欢相关文章：
把握每天的第一个钟头
当我十七岁的时候，我读到一段话，它是这么说的：“如果你把每天都当做最后一天来活着，那么有一天你将会是对的。”这句话让我留下了深刻的印象，从那时候开始，过去的 33 年来，我每天早上都对着镜子…
向量叉积计算法
如果向量A为{a, b, c}，向量B为{m, n, p}，如何计算向量A与向量B的叉积呢？ 用行列式： |i j k| |a b c| |m n p| (bp-cn)i (mc-pa)j (an-bm)k 例如用matlab实现两个向量的叉积： a [1 2 3]; …
你是个成熟的C位检测器了，应该可以自动找C位了
作者 | 李翔转载自视说AI（ID:techtalkai）写在前面C位是近年网络上一个比较热门的词，最早来源于DOTA等游戏领域，是核心位置（Carry位）的简称，代表的是能够在游戏前中期打钱发育并在游戏后期带领队…
Data Artisans发布支持ACID事务的流式处理框架Streaming Ledger
data Artisans宣布推出Streaming Ledger，它扩展了Apache Flink，提供了跨表、键和事件流执行可序列化ACID事务的功能。这项正在申请专利的技术是Flink的专有附加技术，超越了当前一次只能在一个键上实现一致性的标准。\\在发布Streaming Ledger…
The Life Cycle of a Servlet
为什么80%的码农都做不了架构师？>>> Servlet的生命周期由Servlet容器管理，包含如下几个步骤： 1. 装载Servlet类; 2. 创建Servlet的实例; 3. 调用Servlet的init()方法; 4. 调用Servlet的service()方法; 5. 调用Servlet的destroy()…
矩阵奇异值分解
转自：http://www.madio.net/forum-redirect-goto-nextnewset-tid-47409.html 奇异值分解是线性代数中一种重要的矩阵分解，在信号处理、统计学等领域有重要应用。定义：设A为m*n阶矩阵，AHA的n个特征值的非负平方根叫作A的奇异值。记…
智课雅思词汇---十、pend是什么意思
智课雅思词汇---十、pend是什么意思 一、总结 一句话总结：【词根含义】：悬挂,垂;称量;支付 词根：-pend-, -pens- 【词根含义】：悬挂,垂;称量;支付 【词根来源】：来源于拉丁语动词pendeo, pendere, pependi, - (悬挂,下…
新技术“红”不过十年，半监督学习为什么是个例外？
作者 | 严林来源 | 授权转载自知乎（ID:严林）这一波深度学习的发展，以2006年Hinton发表Deep Belief Networks的论文为起点，到今年已经超过了10年。从过往学术界和产业界对新技术的追捧周期，超过10年的是极少数。从深度学…
常用Linux路由命令(route、ip、ifconfig等等）
第一组命令： ifconfig, ifup, ifdown 1) ifconfig 作用：手动启动、观察与修改网络接口的相关参数，包括IP地址以及MTU大小等。 例1.1：暂时修改IP地址 # ifconfig eth0 192.168.100.100 例1.2：修改IP地址、掩码和MTU # i…
洛谷P1074 靶形数独（跳舞链）
传送门 坑着，等联赛之后再填（联赛挂了就不填了233） 1 //minamoto2 #include<iostream>3 #include<cstdio>4 #include<cstring>5 using namespace std;6 #define getc() (p1p2&&(p2(p1buf)fread(buf,1,1<<21,…
直播写代码｜英伟达工程师亲授如何加速YOLO目标检测
NVIDIA TensorRT是一种高性能深度学习推理优化器和运行时加速库，可以为深度学习推理应用程序提供低延时和高吞吐量。通过TensorRT，开发者可以优化神经网络模型，以高精度校对低精度，最后将模型部署到超大规模数据中心、嵌入式平台或…
OpenCV的cvLoadImage函数
转自：http://lijian2005lj.blog.163.com/blog/static/2569113720091111104856644/ 一直不太懂得cvLoadImage的第二个参数，今天知道，原来第二个参数是指定读入图像的颜色和深度。 指定的颜色可以将输入的图片转为3信道(CV_LOAD_IMAGE_COLOR)也…
DX11 preprocessor Dynamic shader linkage
（参照例子DXSDK sample：DynamicShaderLinkage11） 一、preprocessor 实现shader静态分支的经典方法，代码示例如下 shader中(如果显卡不支持DX11，则STATIC_PERMUTE为True)： #if !defined( STATIC_PERMUTE )iB…
OpenCV中与matlab中相对应的函数
1、matlab中的imread相当于OpenCV中的cvLoadImage(imageName, CV_LOAD_IAMGE_ANYDEPTH | CV_LOAD_IMAGE_ANYCOLOR)：读出的图像信息保持了原有图像的信息(包括通道信息和位深信息)； rgb2gray相当于cvLoadImage(imageName, CV_LOAD_IMAGE_GRAYSCALE)&…
AI假新闻满天飞，打假神器GROVER帮你看清一切
最近AI换脸术与AI假新闻叠加在一起，造成了不少乌龙事件，比如最近美国的议长南希佩洛西就的一段醉酒视频就在Facebook上流传甚广，视频中的议长明显是状态晕沉，醉意十足，不过这后来被证明是一段是由deepfake生成的假视频…
NYOJ 93
汉诺塔（三） 时间限制：3000 ms | 内存限制：65535 KB难度：3描述在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝…
C/C++中二维数组作函数形参时，调用函数时，可传递的实参类型的小结
转自：http://blog.163.com/tianhityeah/blog/static/165747821201052195212719/ #include<iostream>using namespace std;int fun(int a[][3],int n) // 其中二维数组形参必须确定数组的第二维的长度，第一维长度可以不定//int fun(int (*a)[…
打破欧美垄断，国防科大斩获“航天界奥林匹克”大赛首冠
整理 | Jane责编 | 一一出品 | AI科技大本营（id：rgznai100）近日，第十届国际空间轨道设计大赛（GTOC X）结束并公布最终成绩，中国参赛队国防科技大学与西安卫星测控中心联队（NUDT&X…
Hive 中的变量
Hive的变量前面有一个命名空间，包括三个hiveconf，system，env，还有一个hivevar hiveconf的命名空间指的是hive-site.xml下面的配置变量值。system的命名空间是系统的变量，包括JVM的运行环境。env的命名空间，…
你必须非常努力，才能看起来毫不费力
有一群人，他们积极自律，每天按计划行事，有条不紊；他们不张扬，把自己当成最卑微的小草，等待着人生开出花朵的那天。他们早晨5点多起来健身，你在睡觉；7点开始享受丰盛的早餐࿰…
cvGetSubRect与cvMul用法
1、对于cvGetSubRect(mat1, mat2, rect)，当用cvGetSubRect函数时，不能事先对mat2申请内存，否则会产生内存泄漏。 只要这样定义mat2即可：CvMat *mat2; mat2 cvCreateMatHeader(imgHeight, imgWidth, CV_64FC1); 2、对于cvGetSubR…
浅谈WPF的VisualBrush
原文:浅谈WPF的VisualBrush首先看看VisualBrush的解释，msdn上面的解释是使用 Visual 绘制区域，那么我们再来看看什么是Visual呢？官方的解释是：获取或设置画笔的内容，Visual 是直接继承自DependencyObject，U…
AI换脸技术再创新高度，DeepMind发布的VQ-VAE二代算法有多厉害？
作者 | beyondma转载自CSDN网站近日DeepMind发布VQ-VAE-2算法，也就是之前VQ-VAE算法2代，这个算法从感观效果上来看比生成对抗神经网络（GAN)的来得更加真实，堪称AI换脸界的大杀器，如果我不说，相信读者也很难…
cisco设备常用命令
router> enable 从用户模式进入特权模式 router# disable or exit 从特权模式退出到用户模式router# show sessions 查看本机上的TELNET会话router# disconnect …
opencv图像处理梯度边缘和角点
转自：http://blog.sina.com.cn/s/blog_4b9b714a0100c9f7.html 梯度、边缘和角点 Sobel 使用扩展 Sobel 算子计算一阶、二阶、三阶或混合图像差分 void cvSobel( const CvArr* src, CvArr* dst, int xorder, int yorder, int aperture_size3 ); src 输入图像. dst …
性能全面超数据库专家，腾讯提基于机器学习的性能优化系统 | SIGMOD 2019
腾讯与华中科技大学合作的最新研究成果入选了国际数据库顶级会议SIGMOD的收录论文，并将于6月30日在荷兰阿姆斯特丹召开SIGMOD 2019国际会议上公开发表。入选论文的题目为“An End-to-End Automatic Cloud Database Tuning System Using Deep Reinforcement Learning…
swift 语言评价
杂而不精，一团乱麻！模式乱套，不适合作为一门学习和研究语言。 谢谢 LZ 介绍，看完之后更不想用 Swift 了。从 C那里抄个 V-Table 来很先进嘛？别跟 C一样搞什么 STL 就好了，整这么复杂，入个门都需…
Creative Web Typography Styles | Codrops
Creative Web Typography Styles | Codrops. 非常好的文字效果
OpenCV 图像采样 插值 几何变换
转自：http://hi.baidu.com/xiaoduo170/blog/item/6eefc612c9f8e9c6c2fd786f.html InitLineIterator 初始化线段迭代器 int cvInitLineIterator( const CvArr* image, CvPoint pt1, CvPoint pt2, CvLineIterator* line_iterator, int connectivity8 ); image 带采…
centos 6.* 修改时间
一、查看Centos的时区和时间 1、使用date命令查看Centos时区 [rootVM_centos ~]# date -R Mon, 26 Mar 2018 19:14:03 0800 2、查看clock系统配置文件 [rootVM_centos ~]# cat /etc/sysconfig/clock ZONE"Asia/Shanghai" 3、查看系统的硬件时间，即BIOS时间…