リコメンデーションのための相関係数１

ユーザーに対して類似のアイテムを推薦すること、いわゆるリコメンデーションを機械にさせるのが、浸透している。リコメンデーションのアルゴリズムというのは興味深い。

	item A	item B	item C	item D
user 1	2	0	2	1
user 2	3	0	1	3
user 3	2	1	3	1
user 4	2	2	4	X

４人のユーザーと４個のアイテムがあったとして、それぞれのユーザーが各アイテムに上の表のような評価を与えているとする。user4のitem Dに対する評価は不明で、今これを推定したいとする。

アプローチとしては２つあって、

1. ユーザーの相関をとるアプローチ、
2. アイテムの相関をとるアプローチ

がある。

今回は１について。

ユーザーごとの相関を計算には、ビアソンの相関係数がもっとも基本的な形だ。

user a, item b との相関係数は以下で計算できる。

ここで、 P はアイテムの集合であり、 r_i, j は user i のitem j に対する評価であり、 \bar{r_i} は user i のアイテムの評価の平均値である。

相関係数なので[-1, 1]の範囲を取り、1に近いほど類似度が高いことを示している。

今回は user 4 に似たユーザーを知りたいので、 user 4 と user 1, 2, 3 の相関係数を求める。 user 4 には item D の値がないので、 P = {A, B, C} です。

計算してみると、

C(A, D) = 0.50
C(B, D) = - 0.19
C(C, D) = 0.87

となり、user A は user D と高い相関があることが分かる。

user a の item p に対する評価の予測値は、以下の式から求められる。

ここで、Nは最近傍ユーザーの集合である。

user C を user D の再近傍ユーザーとすると、 user D の item 4 に対する評価の予測値は、

r_pred(D, 4) = 2.67 + 0.87 * (1 - 2.0) / 0.87 = 1.67

となる。

寄付と投資

歳をとったのか世のため人のために多少は貢献できないかなと思うようになった。手っ取り早い手段は寄付をすることだ。世の中にはお金で解決できる問題は多い。ただお金を出すだけで世の中のためになるなら楽なものだ。金は命よりも重いが、負担にならない程度のお金はほとんど痛みもない。時間だとか労力だとか精神力を負担する方のはやはり大変だ。

駅前を歩いていると、しばしば学生団体と思しき若者が寄付を募っている。立派だと思う。ただ、街頭募金を募っている学生は、必要な人に金を届けるルートを持っているのかと疑問がわく。演説を聞いていると、日本赤十字社などのNPOを経由して送金するようだ。

それなら直接そのNPOに送金したほうが確実だと思う。街頭募金の演説がきっかけで、NPOへの直接の寄付が行われるなら、街頭募金を募る活動にも意義はある。ただ、それだと街頭募金の活動の成果が彼らには見えないので、街頭募金を募る人を応援する意味で彼らを信用して彼らを通して寄付を行うのもありうるだろう。

いずれにしても寄付をするならどこかの団体を経由するしかない。集めた寄付金をどのように使うかの判断は任せたい。誰がどれだけ困っているかなんて、なかなか知りようがない。少額の寄付に対して、それを調べるエネルギーは割けない。NPOが適切に寄付金を使ってくれることは、信用するしかない。

そのため、寄付が集まる団体は権威があるところになる。赤十字社だとかユニセフだとか。無名な慈善団体には寄付をしようとはなかなか思わないものだ。慈善事業は志さえあれば誰でもできそうだが、現実には商業と変わらず権威があるところが有利だ。

これは別に決して悪いことではない；お金が本当に困った人の助けのために効果的に使われるのであれば。しかし、実際のところどうなのだろうと疑問に思っている。ただ、私は赤十字社やユニセフよりも有意義な金の使い方を知っているわけでないので、答えはない。

権威のある団体よりも、寄付すべき団体があるのかもしれないが、それも知りようがない。

困っている人が、クラウドファウンディングみたいな形で直接寄付を募れるようにしたらどうだろうと思ったが、これは良くない。クラウド乞食にしかならないし、困っている人が収支報告なんて出せるわけもなく、余計な混乱を招くだけだ。また、そのマッチングを行う場所の運営費用は誰が負担するのだという話になる。ショバ代なんて当然取れない。

なんかうまい方法があるのではと考えて見たが、寄付は一種の投資なので、それが解決できたら投資の問題なんてすべて解決できてしまう。どうも解決する方法はなさそうだ。

『Who Gets What』

アルビン・E・ロス著『Who Gets What――マッチメイキングとマーケットデザインの新しい経済学』を読んだ。本の内容とは別に考えたことを記す。

Who Gets What (フー・ゲッツ・ホワット) ―マッチメイキングとマーケットデザインの新しい経済学

マーケットデザインというのは経済学・ゲーム理論の応用して効果的なマーケットの制度を設計しようというものである。経済学という学問は、数学の一分野に過ぎなくて、ほとんど数字遊びで現実に存在する問題の解決には全く貢献しない時代が長かったが、近年では経済学の知見を工学的に利用して現実の問題の解決することに成功している。現実に困っている人がいて、その問題の解決ができるということに私は面白さを感じる。

マーケットというのは、２つの集合――例えば、売り手と買い手、男と女、企業と求職者、大学と受験者――のそれぞれの要素を結びつけるシステムのことだ。２つの異なるクラスに属するものを結びつけることをマッチングという。マーケットというのははっきり誰かが定義していると限らない。誰かが何かを探し始めたら、マーケットというのは自然発生する。

しかし、皆が別々の場所・時間でマッチング相手を探していたら効率が悪いので、出会いの場所というのが設置される。*1このマーケットは人工的なもので、そこでのルールとかは設計の余地がある。設計が悪くてマッチングされる組み合わせが適当でなかったり、そのためにマーケットの外で取引が行われたりする。そうすると、みんなが幸せにならない。どのようにマーケットの制度を設計すると、参加者の全員が幸せになるのかを考えるのがマーケットデザインである。経済学というのは皆が幸せになる方法を探求する学問である。

世の中には証券市場に代表とされるような人工的なシステム化されたマーケットも多いのだけれど、そのようになってないマーケットの方が多い。何かと何かを結びつけることは、システムを介さずに行われているものがほとんだ。しかしながら、場所がないところでのマッチングというのは非常にコストがかかるものだ。仲介業というマッチングを行うための専門の業種が存在するほどである。

社会に存在する職業のうち相当部分は、仲介業である。例えば、営業職をしている人って労働人口のうちのかなりの割合を占めている。彼らは何も生み出しているわけではないにも関わらず、こんなにいるのはおかしい；マッチングを効率化する仕組みを作れば生産的な仕事に人口を割くことができる――という見方もできる。あるいは、マッチングというのはそれ自体がそれほどに価値を生み出すものだから、こんなに多くの人を養うことができる――という見方もできる。いずれにせよ、社会で行われている活動のほとんどはマッチングだというのは事実であろう。

今よりももっと高速に安価にマッチングを行うでも、今よりも適したマッチングを行うのでも、どちらのアプローチをとってもマッチングを効率化するようなマーケットを作るというのは、社会的に意味があることだろう。

さて、今私の前にあるコンピュータはインターネットにつながっているわけだが、インターネットというのはこれ以上ないほどにマッチメイキングを行うのに適した装置である。ほとんど全世界の個人が常に接続しているのだ。インターネットのいろいろな使い方が日々考案されているわけだが、何かと何か引き合わせるというのはインターネットの使い方として最も効果的な使用法なのではないかと思う。

インターネットを介したマッチングを行うサービスというのは既に多くあって、ヤフオク、メルカリ、楽天市場、Amazonマーケットプレイス、リクナビ、等々いくらでも挙げることができる。これらを使うことで、インターネット以前には仲介業者が必要だったり、あるいはインターネットがなければ成立しなかったマッチングというのが達成できるのだ。場所を提供するビジネスモデルをプラットフォームビジネスというそうだが、あたればでかい商売である。

インターネット上のマーケットというのはまだまだ可能性があると思う。本にあるようなゲーム理論をマーケットの設計に活用するアプローチというのは、有効な手法な気がしているのだ。昔、Gale-Shapleyアルゴリズム（受け入れ保留アルゴリズム）に基づいて最適なマッチングを作るという合コン用のAndroidアプリを作った。むき出しの理論のままでは全然使えないけれども、どうにかこのコンセプトを現実に適用できる形に落とし込めないかと未だに思っている。最大多数の最大幸福を実現するような仕組みが世の中に受け入れられると私は信じているし、それが実現した社会がどういうものなのかを見てみたいのだ。

*1:ナンパスポットのように自然に場所ができることもある。

出版業は市場データで効率化できるはず

Amazonは手に入りにくい本が簡単に手に入るのでよくお世話になっている。特に便利だと思うのは、中古本のマーケットプレイスというシステムだ。欲しい本が予め決定しているときに、Bookoffに行くことはない。非常によく出ている本はBookoffで探せば見つかるが、そうでない本がたまたま店舗にある可能性は低い。新本で流通している本は、実店舗で注文することは可能だ。しかし、絶版の本で欲しい本を手に入れるのはマーケットプレイスがなければ難しかっただろう。日本中の中古本がマーケットプレイスで流通しているのだ。かなり珍しい本でない限り、絶版本であってもマーケットプレイスで手に入れることができる。

マーケットプレイスで本を調べていて面白いなと思うことは、中古本の市場がオープンになっていることで、需要と供給で価格が決まっている様子が観察できることだ。マーケットプレイスがあることで、中古本市場の効率性というのが大きく向上しているのだろう。欲しがる人が多くて流通数が少ない本は価格が高いし、逆にベストセラーと言われるような本は数が出ているので価格が低い。

株式市場とかは参加者がグルグル回し合っているからなのか、内部的な運動が大きくて、全く均衡している状態とは思えないが、中古本の市場は投機的な取引がないからなのか単純な需給関係で価格が決まっているように見える。本は状態の差はあれど、中身は同じなので、コモディティであることも市場原理が働く理由なのだろう。新本の価格は再販制度で守られているから、市場というものを感じないが、中古本の価格は市場のリアリティがある。

さて、奇妙だと思うのは、古書とか希少本と呼ばれるようなコレクター性があるものではなくても、まれに絶版本で価格が非常に高いものがあることだ。需要があるにも関わらず、流通数が少ないためだ。何が奇妙だと思うのかというと、出版社はどうして再版しないのかということだ。印刷すれば確実に売れるのに。そういう本を一種類だけ再販しても利益にはならないと思うけれども、数を集めれば結構な利益になるはずだ。

しかし、出版業の商習慣を詳しくは知らないけれども、原稿のデータや出版権を集めてきて、売り出すというのはなかなか難しいことだから実現していないのだろう。インターネット上の公開データという形ではっきりと需要があることが可視化されているにも関わらず、供給ができない現状というのは歯がゆいものがある。出版業は斜陽産業だとずっと言われているが、データに基づいて、工夫すれば延命ぐらいはできそうなのに。

また、街の本屋に関しても、新刊ばっかり入荷して在庫を新鮮な状態に保つのもいいのだけれど、どういう本に需要があるかというのが公開されているのだから、それを利用しない手はない。

中古本の出品数や市場価格を分析したら、いろいろ面白いことが見えて来そうだ。例えば、新刊で発売してから、中古市場に出回るまでのタイムラグが分かれば、新刊が新鮮な状態である期間が分かるだろう。あるいは、出品数が多いにも関わらず、高い価格で推移している本は、きっと新本でも売れるだろう。

また、極端かもしれないが、カスタマーレビューが高い本にウェイトを置いて入荷するという作戦も考えられる。本屋で本を買う行為は、習慣性が強いと思っている。ふらっと入って面白そうなら買う。顧客のロイヤリティっていうのか、一度そういう習慣がついたらなかなか抜けない。本屋で本を買ってそれが面白かったという条件付けができれば、固定客を作れる気がする。

街の本屋からしたら、Amazonは商売敵なのかもしれないが、そこで公開されているデータから、いろいろ試せそうだ。利用できるものは何でも利用したらいいと思う。

Amazonという会社は有益なデータを管理しやすい形で保持していると思うが、そこにアクセスすることは残念ながらできない。どこかにマーケットプレイスのデータを集めて整理して公開しているようなとこはないのだろうか？

コード型ログ(4) Initialization-on-demand Holder

前回：　コード型ログ(3) privateなメソッドのテスト - 超ウィザード級ハッカーのたのしみ

---

必要なときにインスタンスを作ったら、メモリ効率がよくないかと思って変なことをしてしまう悪い例。

class BadSingleton1 {
  private static BadSingleton1 instance;

  // 他の人が勝手にインスタンスを作らないように private にする。
  private BadSingleton1() { };

  static BadSingleton1 getInstance() {
    // 同時に２つのスレッドが null チェックをするとユニークでなくなる。
    if (instance == null) {
      instance = new BadSingleton1();
    }
    return instance;
  }
}

上のようなことをしたければ排他を取る必要がある。しかし、これでは遅い。

class NotBadSingleton1 {
  private static NotBadSingleton1 instance;

  private NotBadSingleton1() { };

  // ユニーク性は保証されるが、同期コストがかかる。
  synchronized static NotBadSingleton1 getInstance() {
    if (instance == null) {
      instance = new NotBadSingleton1();
    }
    return instance;
  }
}

だから、以下のDouble-checked lockingというものが考案された。しかし、実は正しく排他されていないことが知られている。この場合はインスタンス変数がないが、ある場合にはスレッドが競合したときに、getInstance()で返ってくるインスタンスのインスタンス変数が初期化されていない可能性がある。

class BadSingleton2 {
  private static BadSingleton2 instance;

  private BadSingleton2() { };

  static BadSingleton2 getInstance() {
    // instance != null だとしても、インスタンスの初期化が終わっていない
    // 可能性が実はある。
    if (instance == null) {
      synchronized (BadSingleton2.class) {
        if (instance == null) {
          instance = new BadSingleton2();
        }
      }
    }
    return instance;
  }
}

初期化を遅延させたかったら、Initialization-on-demand Holderという名前がついている以下の書き方をする。

class GoodSingleton1 {
  private static class Holder {
    private static GoodSingleton1 instance = new GoodSingleton1();
  }

  private GoodSingleton1() { };

  static GoodSingleton1 getInstance() {
    // Holder クラスが初めて呼ばれたときに、instance は生成され
    // ユニークであることは保証される。
    return Holder.instance;
  }
}

しかし、凝ったことをせずに普通に書いたらいい。

class GoodSingleton2 {
  private static GoodSingleton2 instance = new GoodSingleton2();

  private GoodSingleton2() { };

  static GoodSingleton2 getInstance() {
    return instance;
  }
}

Initialization-on-demand Holderを覚えたからと使いたがる人のコードなんて読みたくない。（私もきっとそういうことをやってるけれども……使わないと覚えないし……）

コード型ログ(3) privateなメソッドのテスト

前回：　コード型ログ(2) staticな変数の排他にはsynchronized(*.class) { } を使う - 超ウィザード級ハッカーのたのしみ

---

privateなメソッドは、ユニットテストがしにくい。

対処法は２つで、

1. テストしないか、
2. Reflectionで頑張るか、
3. スコープをpackage pririveteに広げるか、

である。

呼び出しものの入出力からテストができるのであれば、無理してテストをする必要はない。

しかし、わざわざ別のメソッドに分けたということは、入力と出力の対応が明確な単位になっているはずなので、テストしたい。

Reflectionで頑張る場合は、例えば

class Add {
  private static int add(int a, int b) {
    return a + b;
  }
}

を呼ぶには、

  static int invokeAdd(int a, int b) {
    Method m = null;
    try {
      // getMethod では private メソッドは取得できない。
      m = Add.class.getDeclaredMethod(
          "add", int.class, int.class);
    } catch (NoSuchMethodException | SecurityException e) {
      throw new RuntimeException(e);
    }

    // メソッドにアクセスできるようにする。
    // false の場合は、invoke した際に IllegalAccessException となる。
    m.setAccessible(true);

    int r;
    try {
      // インスタンスメソッドの場合は、第一引数はインスタンスとなる。
      r = (int)m.invoke(null, 1, 1);
    } catch (IllegalAccessException | IllegalArgumentException
        | InvocationTargetException e) {
      throw new RuntimeException(e);
    }

    return r;
  }

というような private メソッド呼ぶためのメソッドを作っておいて、そのメソッドの入出力をテストする。このメソッドは読めないので、何をしたいのかはコメントしておくこと。

これが面倒だという場合は、privateにするのは諦めて、アクセス修飾子をdefault (pacakge private)にして、テストから見えるようにする。その際は、テストの時だけ呼び出して良いことを@VisibleForTestingなどで明記しておく。

VisibleForTesting (Guava: Google Core Libraries for Java 19.0 API)

static, final, private なメソッドはメソッド呼び出しのオーバヘッドをなくすためにインライン展開されることが期待できるが、private なインスタンスメソッドを default にしてしまうとこの効果は期待できなくなってしまうので、final をつけるようにするのがよいかもしれない。効果のほどは未検証。privateとfinalが同じ戦略でインライン展開されるかは疑わしい。

privateであっても、テストの時だけは見えるようになってくれれば良いのだけれど。

public ClassnameTest tests Classname {

とか

@TestFor(Classname.class)
public ClassnameTest {

と書いたら、privateメソッドが見えてくれれば便利なのになあ。

コード型ログ(2) staticな変数の排他にはsynchronized(*.class) { } を使う

他の人が書いていたら読めるけれども、知らなきゃ書けない定型文をあつめたコード型ログを作っている。今回は２回目。

前回： コード型ログ(1) スレッドを止めるにはinterruptを使う - 超ウィザード級ハッカーのたのしみ

---

いい設計とは言えないかもしれないが、staticな変数の排他を取りたい時がある。この場合には、synchronized(*.class) { }を使用する。Classオブジェクトは基本的にはstaticでユニークな、つまりシングルトンなオブジェクトである。*1

package org.example.katalog;

public class SynchronizedClass {
  static int count = 0;

  public void run() {
    Thread[] ts = new Thread[5];
    for (int i = 0; i < ts.length; i++) {

      // count変数の値をプリントして、カウントアップすることを10回繰り返す。
      Thread t = new Thread() {
        @Override
        public void run() {
          for (int j = 0; j < 10; j++) {

            // SynchronizedClass クラスのロックを取る。
            synchronized (SynchronizedClass.class) {
              System.out.println(count);
              count++;
            }

          }
        }
      };

      t.start();
      ts[i] = t;
    }

    for (Thread t : ts) {
      try {
        t.join();
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  }

  public static void main(String[] args) {
    new SynchronizedClass().run();
  }
}

悪い例は、ロック用のオブジェクトを作ることである。

public class SynchronizedClassBad {
  // ロックオブジェクト
  private static final Object LOCK_OBJ = new Object();
  static int count = 0;

  public void run() {
    Thread[] ts = new Thread[5];
    for (int i = 0; i < ts.length; i++) {

      // count変数の値をプリントして、カウントアップすることを10回繰り返す。
      Thread t = new Thread() {
        @Override
        public void run() {
          for (int j = 0; j < 10; j++) {

            // SynchronizedClass クラスのロックを取る。
            synchronized (LOCK_OBJ) {
              System.out.println(count);
              count++;
            }
// 以下略

なお、staticメソッドにsynchronizedをつけたもの

synchronized static void method() {
  // 処理
}

は

static void method() {
  synchronized (this.getClass()) {
    // 処理
  }
}

と等価である。

*1:ClassLoaderでややこしいことをしたら別。