leetcode 4 — Median of Two Sorted Arrays

之前做过一道类似的题目,是卜老师算法课作业中的一题,那个题目与此题唯一的不同之处在于此题的两个数组的长度不同。在之前的问题,由于长度相同,每次都可以很好的找到数组的切分点(直接选取两个数组中间的数)。但对于长度不等的两个数组,找到合适的切分点成了关键的问题。

因为要找的是中位数,所以最后的切分一定满足

partitionA+partitionB = (lengthA + lengthB + 1) / 2。

partition是划分位置,也代表左边的数字个数。

分子的+1保证的是左边的数字个数多于右边数字的个数(不加一的话是右边比左边多一个)。由于这个条件,在确定partitionA的情况下,计算partitionB,为保证partitionB不为负,A的长度需要小于B的长度。

既然已经有了一个条件需要满足,那么只要确定partitionA的值,partitionB也随之确定。所以对partitionA的赋值为:

partitionA = (Astart + Aend) / 2

Amin和Amax是两个下标,用于查找对于A的合适划分位置。

Astart的初始值为0,Aend为lengthA。计算出A,B的划分位置之后,开始判断划分位置是否满足条件,并作出适应的调整。

因为第一个条件的控制,左右两边的数字个数是没有问题的,偶数长度情况下两边相等,奇数长度情况下左边多一个数字。

另一个需要判断的条件是大小的判断。左侧的最大值需要小于右侧的最小值,因为数字是分在两个数组中,对于同一个数组,因为是排好序的,所以左侧一定小于右侧。所以判断任务明确了:

max_left(A) < min_right(B)

max_left(B) < min_right(A)

如果第一个条件不满足,则说明A的左侧有不满足条件的数字,需要减小partitionA,将分割线左移。所以令Aend = partitionA – 1。然后更新partitionA继续判断。

如果是第二个条件不满足,则说明A的右侧有不满足条件的数字,需要增大partitionA,将分割线右移。令Astart = partitionA + 1。 然后更新partitionA继续判断。

两个条件都满足的时候就代表A,B的划分是正确的,然后只需要找中位数了。

如果两个数组长度之和为偶数,那么返回左边最大值和右边最小值的平均数即可。

如果两个数组长度之和为奇数,那么返回左边的最大值即可。

在实现的过程当中,需要考虑数组边界的问题。因为两个数组的长度不一样,可能会有partitionA为0或lengthA的情况,也可能是partitionB为0或lengthB的情况。如果不考虑的话,会出现数组越界问题。

leetcode 15–3sum

对于排序后的数组应充分利用顺序的性质,例如这一题需要在一个数组中找到和为0的三个数。因为是求和问题,首先排序可以方便查找。

在排好序后,由于需要找到三个数,首先确定最前面的也就是最小的数,写入for循环,后面的两个数需要通过双指针的方式就行一前一后的查找,结果大于0则后面的指针前移,小于0则前面的指针后移。

这种方法要快于用多层for循环,也算是充分利用了有序的性质。

由于题目要求找到所有的组合且不能有重复,所以在查找过程中每个位置遇到相同的数字,需要跳过。这样做不仅加快了执行速度,省去重复的时间,还保证了不会添加重复的组合。

最后的话,以后遇到排好序的数组,首先需要想到双指针法与折半查找法等,充分利用有序的性质。

User Diverse Preference Modeling by Multimodal Attentive Metric Learning

在该论文中,作者提出了MAML模型,是一种基于多模态信息的度量学习方法,通过该方法学习用户对于不同物品所具有的不同的偏好特征。

一、Related Work

首先,论文介绍了相关的工作,主要分为三个部分:1. 用户偏好建模;2. 度量学习;3. 多模态。

1. Diverse Preference Modeling

在第一部分中,作者将前人的相关工作划分为两组:

第一组是利用评论信息来分析每个用户对于目标物品的不同方面的注意力,并在获得注意力权重向量后将其集成于基于矩阵分解的推荐方法中。相关的模型有:ALFM,AFM,ANCF。

第二组,对于一个目标商品,利用最具影响力的物品/用户(基于目标商品选取)对当前物品/用户的向量做出适应性调整。相关的模型有CMN,MARS,DIN。

2. Metric-based Learning

在度量学习中,本文着重提到的模型为CML模型,该模型是通过欧式距离进行度量,最小化用户,物品之间的的距离(用户与物品是正向交互的)来学习各个用户、物品的向量。该模型取得很好的效果,在此基础上,作者提出的MAML模型针对CML模型中的一个问题(因为每个用户都具有很多的交互商品,每个商品都和很多用户具有交互,所以CML会倾向将所有向量映射到同一个点),提出了一个改进,在每一个用户物品对中加入一个权重向量(用于表示用户对于不同物品的偏好方向),进而也解决了CML中可能映射到同一个点的问题,因为权重向量会把用户向量,物品向量投影到另一个空间。

3. Multimodal User Preference Modeling

主要介绍的模型都是采用了多模态的数据,例如评论信息和物品的图片信息。

二、Proposed Model

在MAML模型中,主要的思路与CML类似,也是距离来度量学习结果,通过最小化加权的用户物品距离:如下图:

这个d(u,i)就是新的度量距离,基于新的距离标准,第一个损失函数为:

w ui为一个惩罚系数(后面会提到),m为safety margin(人为设置)
其中i为u喜欢的物品,k为u不喜欢的物品

之后作者解释了权重向量的训练,模型中采用了两层的神经网络进行学习,公式如下:

得到的权重向量需要是用softmax进行归一化,但如果直接归一化后直接使用权重向量会得到很差的结果,是因为权重向量的每一维度的值都很小,而且用户向量和物品向量都做了正则化限制在一个单位球面中。这样的情况下,两个很小的值相乘会更小导致每一个维度的值偏差都不大,从而无法很好地学习用户的不同偏好特征。所以作者对权重向量的归一化进行了修改:

a为人为设置的值,f为权重向量的维数
通过a将权重向量的值进行了放大

再下一部分,作者介绍了物品特征的计算。对于每一个物品都使用了评论信息和物品图片信息。评论信息的特征通过PV-DM模型进行提取,图像特征通过Caffe reference model进行提取。

Ft,i Fv,i分别为文本特征向量和图像特征向量
最后的ZL为融合的向量

Ranking Loss Weight(这部分没有看太明白,好像是根据采样排序对学习的结果进行惩罚)

在WARP模型中,可以看到rank_d(u,i)的计算过程。

接下来就是正则化:一共列出两个正则化项,分别为:

第一个正则化项的想法是,在提取物品的多模态特征向量后,物品的表示应该和多模态向量表示相近(物品贴合自己的图像特征,评论特征,这很真实)。

第二个正则化项是协方差正则化,防止在特征空间中每一个维度具有冗余信息。

最终得到的目标函数如下所示:

三、个人感悟

感觉MAML主要是针对CML的一个改进,通过添加权重参数表示用户的不同偏好,加入多模态信息更好的表示物品特征。最后的结果对比中,MAML的结果普遍优于CML,但感觉没有预想的多,可能还可以进行一些改进。其中WARP模型部分还没有搞清楚,还需要再看相关论文。