CA——Feature-Hashing

Posted on

论文贡献

  • 给出了一种高维数据降维方法，特征哈希(Feature Hashing)
  • 严格证明了特征哈希的可用性

背景

  • 一种构造组合特征的方法是笛卡尔乘积
  • 计算广告领域往往有数十亿的高维特征
  • 一种表达方式是使用词表法，对每个特征从词表里面进行查询
    • 缺陷一：拓展问题，每次拓展词表时难度较大(难以进行模型升级，因为特征维度在变化)
    • 缺陷二：无法处理词表中不存在的特征(Unknown特征)
  • 一般的降维方法容易带来特征表达能力的损失

特征哈希

  • 哈希函数定义(参考自博客：https://blog.csdn.net/qjf42/article/details/82387559)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def feature_hashing(features, m):
    	"""
    	Args:
    		features: 输入特征序列，可以是数字，字符串(本质还是数字)
    		m: 输出的特征维度，通常是2**26(vw),2**20(scikit-learn)
    	Returns:
    		m维的（稀疏）向量
    	"""
    	# 这里的x一般是稀疏表示的（如：scipy.sparse.csr_matrix），这里是为了方便说明
        x = np.zeros(m)
        for feature in features:
        	# hash_func_1保证散列尽量平均且散列速度快
            idx = hash_func_1(feature) % m 
            # 这里在原始论文中
            sign = hash_func_2(feature) % 2
            if sign == 1:
                x[idx] += 1
            else:
                x[idx] -= 1
        return x
    • 输出特征维度一般为\(m = 2^24\)等，是一个认为给定的数字

  • 与词表法比较：

    • 解决了模型升级时的特征拓展问题(增加新特征时，特征的维度不会变化)
    • 解决了Unknown特征问题(个人理解：因为hash函数不管是什么特征，都可以一视同仁)
    • 无需查表，节省了查表的时间(个人理解：其实查表时一般实现方式也是用哈希表构建索引，所以这里不能算是优势)
    • 完成了降维(这里是把字典法里面对邮件或者文档的id也算作一个特征，这个特征one hot表示一下将会造成数据维度变得非常大？但是id算做特征有什么意义吗？)

一些说明

  • 冲突总会发生，也就是说不同一个特征总有一定的概率被映射到同一个维度(即两个不同特征的idx值可能相等)上
  • Paper中的垃圾邮件过滤模型实验证明：冲突造成的损失漏召率在\(m=2^22\)时影响约为1%，接近不做hash时的效果(特征维度在不做hash约为\(2^{25}\))且在\(m=2^{18}\)时为1.12%，也只升高了一点点
  • 另外：无论如何，总有特殊情况，比如重要的特征如用户的性别特征“男”和“女”二者可能被映射到同一个维度上
    • 这里编码时是男:(1, 0), 女(0, 1)这样的，所以如果二者映射到同一个维度上，那么这两个特征丢失了原本的表达能力
    • 真实环境中如果遇到这些问题将会很难调试，如果找到了相关的问题，可以通过修改映射函数的输入参数字符串等方式来错开两个特征
  • 特征哈希本身可以类比于机器学习中的核技巧,所以特征哈希也称为哈希技巧

一些理解

知乎用户

  • 参考Ainika Peng的博客：https://www.zhihu.com/question/264165760/answer/279676705
  • 一般而言这类技术是为了解决两个问题：
    • 一是将categorical的特征编码为模型可理解的格式, 这是个基础问题。One-Hot Serializing就可以达到这个效果，例如将训练样本中出现过的的每个deviceid按顺序递增编号（比如deviceid@xxx:1 -> feature@10000:1）。
      • 缺点1：这个映射表需要传递给引擎端，在prediction的时候照着再查一遍，数据量大且数据结构设计不好的时候很费时间；
      • 缺点2：有些频次很低的特征置信度不高，单独出现对模型无益（甚至over-fitting）。这时候可以使用按频次截断技术进行降维。比如微软在deep crossing中提到的特征工程方法：只保留曝光最多的10k个campaign id编码为0-9999，其余的id全部编码为10000，但辅以poCTR等连续特征作为辅助。事实上这是一种手工的Hashing方法。
    • 二是尽可能在保留有效信息的基础上降低训练和预测过程的时间复杂度
  • 自动Hashing方法的好处是：
    • 只要训练和预测时使用的hashing方法一致，对同一个特征的编码结果即一致，因此引擎预测或提供数据dump的时候无需查找编码表。所以其最大优点在于数据一致性和速度提升，这在极大规模特征和在线学习中至关重要。
  • 我们说的Hashing算法一般而言均特意设计为低碰撞率。
    • 因此一般hashing算法本身不会大幅降低特征维度，自然也不会大幅损失特征信息。真正可能存在问题的是hashing之后的降维过程。
    • 一个非常常见的陷阱是string哈希到int64后取模m，试图将特征压缩至m维one-hot空间。在这种情况下，对于不知情的随机hashing过程，不同特征的碰撞率为1/m。举个例子，对于“性别”特征，将male哈希为一个int64，female哈希为另一个int64，很难发生碰撞；但如果你试图使用mod2将其压缩，如果你的算法哈希出的这两个int64奇偶性相同，则会导致特征失效。在你有很多feature需要哈希而又不清楚hashing算法细节的情况下，这在概率意义上是很容易发生的。
      • 这里的mod2是极端举例，其实m的取值小于原始维度的情况下都有一定概率造成冲突
  • 因此我们会更倾向于所谓的embedding算法
    • 例如将70万维的userid通过weight embedding到32维的连续值特征上（不同于传统hashing的低维离散值特征）。这意味着训练过程更加复杂（有更多的weight需要optimize）；但对于预测过程，其特征性能十分良好且时间复杂度得以降低。同时，由于连续值特征空间的表达能力大幅高于离散值特征空间，整个模型的表达能力并不会明显下降，也基本不会发生离散hashing的碰撞问题。
    • 当然，如果是FM这类倾向于接受离散值的模型，手工serializing+精心设计的hashing是较好的选择。
  • 优点：
    • 训练和预测的时间复杂度大幅降低；
    • 数据的一致性强，不存在同一个特征今天编码成这个、明天编码成那个的情况，便于跟踪单特征效果；
    • 对new feature可以直接编码并加入训练，无需等待编码表统计并反馈；
    • 降低feature space大小，（精心设计可以）降低over-fitting的几率。
  • 缺点
    • 在不清楚hashing function细节的情况下，容易导致特征碰撞失效，且难以排查；
    • 难以通过hashing出的特征反推源特征；
    • embedding会降低模型的可解释性。