BigQueryで配列をヒストグラム用のデータに加工するUDFなど

なに？

簡単な処理はBigQueryでさくとやってしまおう、ただしSQL UDFでJSより速いらしい？
可読性が落ちるのは仕方がない。

ヒストグラム

集計したい配列ARRAY<FLOAT64>とヒストグラムのビンの個数INT64を受け取って配列を区分けしその区分と個数を返す

CREATE TEMP FUNCTION HISTOGRAM(list ARRAY<FLOAT64>, bins INT64) 
RETURNS ARRAY<STRUCT<lower FLOAT64, upper FLOAT64, N INT64>> AS ((
WITH min_max_width AS (
  SELECT AS STRUCT
    MIN(i) AS min_i,
    MAX(i) AS max_i,
    (MAX(i) - MIN(i)) / bins AS w
  FROM UNNEST(list) AS i
),
division AS (
  SELECT AS STRUCT
    min_i + b * w AS l,
    -- 最後だけ誤差が出るので場合わけ
    IF(b = bins-1, max_i, min_i + (b+1) * w) AS r,
    b = bins-1 AS flg_last
  FROM UNNEST(GENERATE_ARRAY(0, bins-1)) AS b, min_max_width
)
SELECT ARRAY_AGG(STRUCT(
  l AS lower,
  r AS upper,
  -- 最後だけ両側を含む
  IF(flg_last,
    (SELECT COUNT(*) FROM UNNEST(list) AS i WHERE l <= i AND i <= r),
    (SELECT COUNT(*) FROM UNNEST(list) AS i WHERE l <= i AND i < r)
  ) AS N
))
FROM division
));

-- Box-Mullerで正規乱数を生成
WITH n_rand AS (
  SELECT ARRAY_AGG(SQRT(-2 * LN(RAND())) * COS(2 * ACOS(-1) * RAND()))
  FROM UNNEST(GENERATE_ARRAY(1, 10000))
)
SELECT *, 
  N / SUM(N) OVER () / (upper - lower) AS normed_hight
FROM UNNEST(HISTOGRAM((SELECT * FROM n_rand), 10))

実行結果

行	lower	upper	N	normed_hight
1	-3.846461812	-3.088727823	8	0.001055779
2	-3.088727823	-2.330993833	111	0.01464894
3	-2.330993833	-1.573259844	463	0.061103238
4	-1.573259844	-0.815525854	1498	0.197694708
5	-0.815525854	-0.057791865	2609	0.344316084
6	-0.057791865	0.699942125	2896	0.382192173
7	0.699942125	1.457676114	1722	0.227256534
8	1.457676114	2.215410104	554	0.073112729
9	2.215410104	2.973144094	122	0.016100637
10	2.973144094	3.730878083	17	0.002243531

サンプル数に対してビンが少ない気もしますが、だいたい標準正規分布っぽいので成功です。

nDCG

ランキングを改善するタスクを行なった時に使った並び順のスコアを評価する永続UDFです。
そういえばいつの間にか、TEMPを消してFUNCTION名に保存先を指定することで永続化することができるようになってました。

CREATE FUNCTION `project.data_set.NDCG`(rels ARRAY<INT64>) 
RETURNS FLOAT64 AS ((
WITH discount AS (
  SELECT
    IF(i = 0, rel,  rel / LOG(i+1  ,2)) AS r,
    IF(i = 0, rel_rev,  rel_rev / LOG(i+1  ,2)) AS n
  FROM UNNEST(rels) AS rel WITH OFFSET AS i
  LEFT JOIN UNNEST((SELECT ARRAY_AGG (rel ORDER BY rel DESC) FROM UNNEST(rels) AS rel)) AS rel_rev WITH OFFSET AS i
  USING (i)
)
SELECT SAFE_DIVIDE(SUM(r), SUM(n))
FROM discount
));

順序が進むほど(ランキングが下がるほど？)$\frac{1}{\log_2i+1}$でディスカウントして足し合わせて正規化するだけです。

呼び出し

SELECT data_set.NDCG([3,3,3,3,3,0,0,0,0,5])
-- SELECT `project.data_set.NDCG`(...)

同プロジェクトならproject名を省略できるのはテーブルと同じ。

行	f0_
1	0.8804360184094202

ちなみに...
@$k$以下の要素に対して評価したい場合は引数k INT64を追加して、discout時にWHERE i < kをしてやればいい

余談

ヒストグラムの実装はゴリ押しになってしまった。

いまいちSQLのインデントわからん。あんまりJOINをインデントするのはなんか好きじゃない気持ち。
あと改行もいまいちわからない。