algorithm - 使用 Map/Reduce 计算自举算法

Question

这道题原本是我的作业，但是我的答案是错误的，我很好奇这道题的最佳解法是什么。

目标是使用 4 个 map reduce 步骤计算“推荐系统引导算法”的关键方面。我的问题出在第 3 步，所以我只会提供它的详细信息。

input: records of the form:
1. (population id, item, number of rating users, sum of ratings, sum of ratings squared)
2. (population id, splitter item, likers/dislikers, item, number of rating users, sum of ratings, sum of ratings squared)

第二种形式与第一种形式非常相似，但每个形式都有一个记录(拆分器、喜欢者/不喜欢者)——其中喜欢者/不喜欢者是一个 bool 值。

这意味着(我认为)有 2^|items| records of the seconds form for each record from the 1st form...(很多同学做错了(又一次，我认为..)假设有相同数量的 1st 和 2nd form 记录)

任务描述:

This step will compute, per splitter movie, the squared error (SE) induced by each movie.

• 输出:形式的记录(人口 ID、拆分器项目、项目、在拆分器上拆分的项目的平方误差)。

提示:

assume that there exists a string that precedes (in the system’s sort order) any splitter movie id.

这必须在一个 mapreduce 步骤内完成!

其他背景:
这是在“The Netflix Challange”的背景下了解到的

SE 定义:

编辑:有关该问题的其他 Material [关于 netflix 挑战的一些描述和有关该问题的数学信息] 可以在 this link 中找到。 [特别是幻灯片 12-24]

EDIT2:请注意，由于我们使用的是 map/reduce，因此我们不能假设任何有关 ORDER 记录的信息都会被处理 [在 map 和 reduce 中]。

Answer 1

我不确定我是否理解您的问题。

您最终想要的是 SE(U)。在幻灯片 23 和 24 的一些数学细节之后，它是“简单地”用\sum_{i} SE(U)_i

计算的

您自己已经了解，9 月 4 日和最后一个是 map reduce 以获得此总和。

第三步是map reduce得到(LaTeX风格)

SE(U)_i = \sum_{u in U_i} (r_{u,i} - r_i)^2

• reduce 函数对 U_i 中的 u 求和
• map函数拆分要求和的项

在 Python 中这可能是这样的:

def map(Ui):
    ''' Ui is the list of user who have rated the film i'''
    for user in Ui:
        results.append((user,(r_{u,i} - r_i)^2))

def reduce(results):
    ''' Returns a final pair (item, SE(U)_i ) '''
    return (item, sum([value for user,value in results]))

编辑:我原来的回答不完整。让我再解释一下。

您最终想要的是每个分离器的 SE(U)。

步骤 a 准备一些关于项目的有用数据。发出的条目定义为:

key = (population_id, item)
value =
    number: |U_i|,
    sum_of_ratings: \sum_{u \ in U_i} r_{u,i} 
    sum_of_squared_ratings: \sum_{u \in U_i} r_{u,i} ^2

• map 函数分解了项目的统计信息。
• reduce 函数计算总和。

现在，对于任何给定的分割电影 M:

U_M = U_{+M} + U_{-M} + U_{M?}

步骤 b 显式计算每个 split 器 M 的小子种群 M+ 和 M- 的统计数据。

NB 喜欢/不喜欢不是 bool 值本身，它是子群体标识符“+”或“-”

每个拆分器项有 2 个新条目:

key = (population_id, item, M, '+') 
value = 
    number: |U_i(+)|
    sum_of_ratings: \sum_{u \ in U_i(+)} r_{u,i}
    sum_of_squared_ratings: \sum_{u \in U_i(+)} r_{u,i} ^2

Same thing for '-'

或者如果你更喜欢 dis/likers 符号

key = (population_id, item, M, dis/likers) 
value = 
    number: |U_i(dis/likers)|
    sum_of_ratings: \sum_{u \ in U_i(dis/likers)} r_{u,i}
    sum_of_squared_ratings: \sum_{u \in U_i(dis/likers)} r_{u,i} ^2

cf 幻灯片 24 的中间

注意如果你认为每部电影都可能是一个分离器，那么第二种形式有 2x |item|^2 个项目；那是因为 item -> (boolean, item, splitter) -- 这远远小于你的 2^|item|你还没有解释的评估。

步骤 c 为每个分离器 M 计算每部电影的估计 SE，即 SE(U_M)_i

因为总和可以分配给不同的成员:

U_M = U_{+M} + U_{-M} + U_{M?}

SE(U_M)_i = SE(U_M?)_i + SE(U_+M) + SE(U_-M)

使用 SE(U_{+M}) 使用此映射函数显式计算:

def map(key, value):
    '''     
    key = (population_id, item, M, dis/likers) 
    '''
    value = 
        count: 1
        dist: (r_u,i - r_i)^2

    emit key, value

def reduce(key, values):
    ''' 
    This function explicitly computes the SE for dis/likers
    key = (population_id, item, M, dis/likers)
    value= count, dist
    '''
    emit key, sum(count, sum(dist))

现在我们只需要SE(U_{M?})_i，这是幻灯片 24 中给出的“简单”计算:

SE(?)_i = \sum_{u \in U_i(?)}{r_{u,i}^2} - (\sum r)^2 / |U_i(?)|

当然，我们不会做这么大的加法，而是使用讲座上面的评论，以及步骤 a 中已经计算的数据(这是我从幻灯片 24 的最后 3 个等式中得出的结论)

SE(?)_i = \sum_{u \in U_i}{r_{u,i}^2} - \sum_{u \in U_i('+'/'-')}{r_{u,i}^2} - (...)/ (|U_i| - |U_i('+'/'-'))

所以这一步甚至不是 Map/Reduce，它只是最后一步:

def finalize(key, values):
    for [k in keys if k match key]:
        ''' From all entries get
        # from step a
        key = (population_id, item) value=(nb_ratings, sum_ratings, sum_ratings_squared)
        # from step b
        key = (population_id, item, M, '+') value=(nb_ratings_likers, sum_ratings_likers, sum_ratings_squared_likers)
        key = (population_id, item, M, '-') value=(nb_ratings_dislikers, sum_ratings_dislikers, sum_ratings_squared_dislikers)
        # from step c
        key = (population_id, item, M, '+') value=(se_likers)
        key = (population_id, item, M, '-') value=(se_dislikers)
        '''
        se_other = sum_rating_squared - sum_ratings_squared_likers  - sum_ratins_squared_dislikers - sum_ratings_likers / (nb_ratings -  (nb_ratings_likers)) - sum_ratins_squared_dislikers  - sum_ratings_likers / (nb_ratings -  (nb_ratings_likers))
        emit
            key: (population_id, splitter, item)
            value : se_likers + se_dislikers + se_other

步骤 d 最后，最后的步骤计算 U_M 的 SE。它只是先前条目的总和，以及一个简单的 Map/Reduce:

对于分离器 M:

SE(U_M) = \sum_i SE(U_M)_i = \sum_i SE(U_M?)_i + \sum_i SE(U_+M) + \sum_i SE(U_-M)