2020-06-06

論文の読み方

論文

論文の読み方

こちらのyoutubeを見たメモ

youtu.be

どれくらいの論文を読むか

論文というのは、もちろんインターネット上に落ちている論文も含むが、mediumやblogの投稿などでも良い。
一つの分野について、実装をするだけなら5~20本の論文を読めばよい。50~100になればその分野への深い理解が得られるだろう。
最初に読む論文をリストアップする。リストアップした論文を少しずつつまみ食いしていく。その中で、読んだ方が良い論文が見つかり、その論文に絞って読み進めていく。そのあとに引用している論文でもいいし、他に途中まで読んだ論文を再開しても良い。

一つの論文の読み進め方

まずは、title/abstract/特徴的なfigures。
次に、intro/conclusions/figures。
- related workは無駄な部分や理解が難しいも多い。
数学の部分をスキップして読む。
全て読むが、理解できない部分はスキップする。
- どの部分が重要なのかわからないので、理解できない場合はそこに時間をかけなくて良い。

読み終わったらすること

次の質問に答えられるか？

著者は何を主張しようとしているか？
手法の重要な点はどこか？
自分は何を利用することできるか？
他のどのような論文を次に読みたいか？

情報収集

twitter
- Kian, Andrew Y NG
ML subreddit
NIPS/ICML/ICLR
friends

数学パートについて

読んで、そのあと自分で論文を読まずにアルゴリズムを導出できるか？
- 模写のようなもので、既存の数学から自分に活かせるものがたくさんあるはず。

コードについて

オープンソースのコードを走らせる。
スクラッチで組んでみる。

大事なこと

読み続けること。短期間に頑張りすぎないこと。

2020-06-04

AtCoder: ABC169-F Knapsack for All Subsets (600)

atcoder 数え上げ dp 集合競技プログラミング解法メモ

問題はこちら

atcoder.jp

長さ $N$ の正整数列 $A _ {1}, A _ {2}, ..., A _ {N}$ に対して、その部分集合 $T$ を考える。その部分集合に含まれる部分集合 $U$ の和が $S$ になるようなものの個数を求めよ。

考え方

集合単位でDPをしていくことを考える。部分集合に含まれる部分集合という考えが少し難しいが、入力例1を見れば概観が掴める。

dp[i + 1][j]：0-indexで $i$ 番目まで見たとき、和が $j$ となるような $U$ を含む $T$ の場合の数。
A[i] を $U$ に含めないとき、 $U$ の和は $j$ のまま。 $T$ に入れる or 入れないで二通りの可能性がある。よって、dp[i + 1][j] += dp[i][j] *2
A[i] を $U$ に含めるとき、 $U$ の和は $j + A _ {i}$ になる。よって、dp[i + 1][j + A[i]] += dp[i][j]

例えば、 $A$ が $\{4, 2, 1\}$ 、 $S=4$ のときを考えてみる。

dp[1][4]： $T = U$ で、 $\{4\}$ の1通り
dp[2][4]：dp[1][4] で題意を満たしているもの対して、 $T$ に 2を入れると $\{4, 2\}$ となる。入れないと $\{4\}$ となる。いずれも $U$ は $\{4\}$ のままなので題意を満たすが、dp[1][4] のときと違い、 $T$ に $2$ を入れる場合が増えるため、dp[2][4] += dp[1][4] * 2

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll mod = 998244353;

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main() {
    ll n, s;
    cin >> n >> s;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    vector<vector<ll>> dp(n + 1, vector<ll>(s + 1));
    dp[0][0] = 1;
    rep(i, n) {
        rep(j, s + 1) {
            dp[i + 1][j] += ((dp[i][j] * 2) % mod);
            dp[i + 1][j] %= mod;
            if (j + a[i] <= s) {
                dp[i + 1][j + a[i]] += dp[i][j];
                dp[i + 1][j + a[i]] %= mod;
            }
        }
    }
    cout << dp[n][s] << '\n';
    return 0;
}

Submission #13986313 - AtCoder Beginner Contest 169

2020-05-24

LeetCode: Max Dot Product of Two Subsequences (Hard)

競技プログラミング解法メモ dp LCS leetcode

問題はこちら

leetcode.com

二つの配列 nums1 と nums2 が与えられる。同じ長さの空でない部分列を nums1, nums2 から順序を変えずに選んだ時の内積の最大値を求めよ。

$1 \leq nums1.length, nums2.length \leq 500$
$-1000 \leq nums1 _ {i} , nums2 _ {i} \leq 1000$

考え方

DPの典型問題（解けませんでしたが... ）

LCSと関わりが深いので、こちらの記事でLCSについて勉強しておくと良いかもしれない。

hiramekun.hatenablog.com

全ての部分列を考慮する方法だと、 $\sum _ {i=1} ^ {500} {} _ {500} C _ {i} \times _ {500} C _ {i}$ 程度かかり到底間に合わない。

ここで注目したいのが、nums1[i1] と nums2[i2] を使用した時、次に使用するのはそれぞれ i1, i2 以降のindexになるということだ。つまり、 「index(i1, i2) という状態は、それ以前のindexからしか到達しない」 ということ。

ここまでわかると、DPで解けることがわかる。というのも、題意をみたすように index i1, i2 の状態に来るには、なるべく大きい値を取るようにして遷移してくればよいためだ。

よって、DPの遷移は以下のようになる

dp[i1][i2]: nums1 の $i$ 番目、 nums2 の $j$ 番目までの部分列における内積の最大値。
nums1[i1] と nums2[i2] を使用する時
- 題意では空でない部分列を求めるため、使用する場合は今までの値を使うか、それともこの場所から使用をスタートするかを選ぶことができる。
- dp[i1][i2] = max(dp[i1][i2], max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]
nums[i1] とnums2[i2] を使用しない時
- それぞれ、一つ隣のindexから遷移し、大きければ採用する。
- dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2])
- dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2])

解答

https://leetcode.com/submissions/detail/343972017/

class Solution {
public:
    int maxDotProduct(vector<int> &nums1, vector<int> &nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, INT_MIN));
        dp[0][0] = 0;
        for (int i1 = 1; i1 <= n1; ++i1) {
            for (int i2 = 1; i2 <= n2; ++i2) {
                dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1][i2],
                                 max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]);
            }
        }
        return dp[n1][n2];
    }
};

2020-05-17

『テストは何を測るのか - 項目反応理論の考え方』まとめ1

book 教育

項目反応理論のお勉強。公平な試験をどのように作っていくのか、理論的背景を学ぶ。

テストは何を測るのか―項目反応理論の考え方

作者:悠彦, 光永
発売日: 2017/02/01
メディア: 単行本

第1章試験という「道具」を理解する

第1章試験という「道具」を理解する

1.1 試験は「能力を測定するための道具=問題」の集合体

受験者間で比較可能な尺度を用意し、その尺度を用いて受験者の能力を表示する。
【構成概念】：一つの尺度で表すことができる対象。
試験の設計とは、測りたい対象を構成概念として定義しておき、多数の問題に対する受験者の反応を手がかりに、尺度を構成する手続きのこと。

1.2 試験と擬似性格検査とアンケート

能力をどうやって問うのか？

【擬似性格検査】：結果も重要視されないような性格検査のこと。（本書定義）
擬似性格検査は問おうとしている構成概念に対して、明確な定義を与える必要がある。
- 【概念的定義】：他の事象との関連性を列挙することで、抽象的概念を具体化していく定義の方法。
- 【操作的定義】：問題に正解できれば能力が高いとする定義の方法。
  - 【妥当性の検証】：概念的定義に基づいて操作的定義が成り立つのであり、操作的定義により作成された問題が、概念的定義に基づく「本当に測りたい内容」と一致しているのかどうか検討する必要がある。

1.3 単一の尺度のによる測定

何が測定される対象かということが重要な検討要素。全ての試験において、試験で測定しようとしている構成概念を統一する必要がある。

尺度は階層性を持つ（英語能力という上位尺度に対して、スピーキングが下位尺度、のように）。
統一された単一尺度を扱うことで、試験のスコアに具体的な意味づけをすることが可能。
学力の規準となる集団を定め、その集団と比較可能なように尺度を作ることが必要。
- 【標準化】：規準となる集団と比較可能なように尺度を構成する手続き。
多くの試験では、「スコアのでたは、今たまたま選ばれた受験者の実力を反映したものであり、その背景には多数の受験者が存在する。そして、それら多数の受験者の能力は、正規分布をしている」という仮定を置くことが一般的。
- テストを受けていないが存在を仮定することができる多数の受験者を母集団と呼ぶ。
- 実際に試験を受験したものをサンプルと呼ぶ。
【標準化テスト】：規準集団を決め、学力の尺度を規準集団上で表示する標準化の手続きを経た試験。
受験者の能力レベルに依存しない形の問題の難易度がわかれば、その難易度を調整することにより、複数の試験のスコアを比較することができる。→ 因子分析（後述）
問題にはそれ固有の特性（項目特性）がある。難易度、識別力等々。規準集団における原点と単位を定義し、続く試験の原点と単位を規準集団上に合わせる。
尺度得点の計算
- 規準集団の受験者が問題を解いた場合の、それぞれの問題に関する難易度の情報が必要。規準集団の受験者にとってどの問題がどの程度難しかったかがわかれば、試験の結果得られた受験者の正誤データを手掛かりに、受験者の能力が規準集団状でどこに位置するかを推測することができる。

1.4 ハイ・ステークスな試験のために：信頼性と妥当性の確保

「質の良い試験」とはなにか？そのためには「信頼性」と「妥当性」の観点からの議論が有用。

【ハイ・ステークスな試験】：受験者にとって結果が人生を左右するような試験。逆はロウ・ステークス
【信頼性】：常に受験者の能力の大小を言い当ててている。
【妥当性】：試験で問われている内容と、実際に測定されるべき能力とがマッチしている。
信頼性の確保
- 試験問題に対する正解・不正解が能力の大小によってばらつくかどうかの程度をテストの信頼性という。
- 同じ概念に対して複数の問題を出題し、正誤データに高い正の相関が見られた時 → 信頼性が高い。（問題を複数出すことで、問題によるばらつきを抑えていく）
- 信頼性の指標としては、試験問題の冊子全体に一つの値が与えられる。
  - 問題冊子全体の信頼性は、個々の問題文の信頼性の積み重ね。
妥当性の確保
- 構成概念妥当性がその試験にどの程度あるかが重要。
- ある集団の測定結果を基にした尺度が、他の集団に対しても適用できるか？などなど
- 数値的に表すことが難しい。
- 統一的な見解がなされていない。

2020-05-16

『教育の効果メタ分析による学力に影響を与える要因の効果の可視化』まとめ

book 教育

とっくのとうに読み終わっていたのですが、記事は途中なので随時更新します。まだ自分用のメモ程度です。

教育の効果: メタ分析による学力に影響を与える要因の効果の可視化

作者:ハッティ,ジョン
発売日: 2018/02/20
メディア: 単行本

学習者要因の影響
家庭要因の影響
学校要因の影響

学習者要因の影響

生涯にわたって15000時間を子供は学校で過ごすが、これは起きている時間の約3割が教師に委ねられているという計算になる。しかしながら、ここでは学校に入学する前にすでに子供に培われた要因について論じている。

過去の学力

過去の学力は大きな影響を持ち、2/3の学力の伸びを説明するという内容は恐ろしい内容だが、残りの1/3はそのあとに変わると考えると、意外と悲観することでもないかもしれない。

過去の学業成績は学習の習熟を最も予測する変数である。
過去の学力はその後の学力の伸びを68%説明する。逆に32％は過去の学力からは説明できない。しかしながら、就学前教育や遺伝的要因は入学後の学力をかなり左右する。
22ヶ月時点での能力が26歳時点の学力を十分に予測していたことが明らかとなった。

態度と気質

言われれば確かにその通りという内容が多いが、データとしてきちんと客観的に示されていることは大きい。動機付けをどのようにして促進していくかは教師にとって大事な能力であると感じた。

不安、独りよがりの傾向、外交性などと学力の関係はほぼ見られない。
自己効力、自己概念、動機付け、学業達成への粘り強さなどは学力と高い相関が見られる。
ビッグファイブ（神経症傾向、外交性、開放性、調和性、勤勉性）のうち、勤勉性以外は学力に与える効果は小さかった。
普段から幸福感を覚え楽しい気分でいる人は創造的で効率よく問題解決を行う傾向が見られる。
自己効力感（できる、したいといった信念）が、自己に対する認識の面では学力と一番関係が強い。しかしながら、自己効力感と学力はお互いに影響を及ぼし合っているので、単純な因果関係ではない。
学習者が有能さを感じている時、自律性を十分に感じている時、やりがいある目標を設定した時、適切な評価を得た時、そして他者から認められた時に、動機付けは最も高くなる。
学習は自己責任において行うものであると考えている度合いと学力のとの間には相関が見られる。
明確な学習目的と、わかりやすい到達基準があり、学習者にとって学習が見通しのあるものにすることが、学習者が学習に対して積極滝に取り組めるようにするためには必要不可欠。

就学前教育

新しいことに挑戦するという姿勢自体が、早い時期から育まれるべきものであるということは大事。

早期教育の全体的な効果は教師の効果を上回る。しかしこの効果は学校に上がって学年が進みにつれて減少する。
保護者が関与することで早期教育の効果が高まるということについてエビデンスはない。

家庭要因の影響

子供に伝わる保護者の後押しや期待は大きな影響を持つということについて語られている。

社会的な地位

学習者の学力に対して顕著な影響がある。
地位によって就学時点で語彙力が倍近く違った。
学習者の方が家庭の経済的・文化的背景に伴う違いによる不公平感を低く見積もる。
学校側から教育用語や学校とはどのような場であるかを親に知ってもらう取り組みが効果を上げている。
保護者自身の学習に対する働きかけも効果があった。

生活保護

目に見えるほどの差ではないが、優位に低い値が出ている。

家族構成

一番影響が大きいのは、子供に対して保護者が願望と期待をかけること。家庭条件よりもはるかに大きな影響をもたらす。

養子に入る年齢が遅ければ遅いほど、学力が下がる。
一人っ子である子供は、兄弟のいる子供と比べて学力と知能が高い。しかし効果は小さい。
母親としての子供との養育的な関わり、日課の多様性、適切な遊具の用意が学力をあげた。（しかし、父親に関しては言及されていない。）
テレビ視聴の適正時間は年齢が上がるに連れて短くなる。視聴時間が週に35-40時間を超えると負の効果量が大きかった。
テレビ視聴が社会的に良い行動に与える効果は、反社会的行動に対する効果を上回る。
保護者による勉強の監視は、思春期の学習者の希望や意欲に対して負の影響を与える。
保護者が期待をかけることは影響が大きい。
保護者は子供に読み聞かせをすることよりも、はるかに、読み方のコツを教えることが効果的である（10倍近くも...！）

学校要因の影響

マルチレベリング手法によって分析が行われてきた←要勉強。児童生徒の学力の分散は学校間要因よりも、学校内要因によって説明される部分が大きいことを明らかにした。

学校構成の効果

高校の学校規模が学力に与える効果は大きい。
学校に在籍する児童生徒が経済的に恵まれているほど適正となる集団規模は大きくなる。
学校外で行われる学習プログラムによってもたらされる学力の伸びは小さい。

学級構成の効果

学級規模が学力に与える効果は一貫して小さい。
学級規模が小さく変わっているのにも関わらず、それに合わせて授業の方法を大きく変えていないことが原因の一つとして考えられる。
能力別学習集団編制の効果は極めて小さく、また低学力集団の生徒に関してはより学習を遠ざけている。なぜなら、低学力の生徒に対して教師は何も期待しないからだ。
複数の学年の児童生徒が同一の教室で同一の授業を受けるシステムでも、効果は低かった（つまり、負の効果も与えなかった）。
小集団に対して課題を与え、自力で解決させる場合は、大学生に対する効果量が大きかった。

学級の風土

児童生徒に対して教師が敏感になること、適切な心構えを持つこと（これはなんだろう...）、規律的介入をすること、などなど...規則や行動規範を示すことも大事である。
一心に目標に向かおうとする態度、前向きな人間関係、社会的な支援が学習をより良いものにする。集団のまとまりは学力に大きな影響を及ぼす。

2020-04-27

AtCoder: ABC164-D Multiple of 2019 (400)

競技プログラミング atcoder 数え上げ累積和解法メモ数学

問題はこちら

atcoder.jp

1から9までの数字からのみなる、文字列 $S$ が与えられる。
次の条件を満たす整数の組 $(i, j)(1 \leq i \leq j \leq|S|)$ の総数を求めよ。

条件: $S$ の $i$ 文字目から $j$ 文字目までを10進法の整数としてみると、この整数は2019の倍数である。
制約: $1 \leq|S| \leq 200000$

考え方

はじめに

$i, j$ を二重ループで全ての通り試して、その数が2019で割り切れるかを試す方法が真っ先に思い浮かぶが、計算量が $O(n ^ {2} )$ となり今回は間に合わない。

桁を増やしながら何か数えることができれば、計算量が減りそうだと考える。そこで、桁を一つ増やすごとにどのように状態が変わるかに注目してみる。

簡便化のために、 $S$ の長さを $n$ 、 $S$ の右から $i$ 番目の数を $a_i$ とし、 $S$ を次のように表す。
$a _ {n} a _ {n-1} \cdots a _ {2} a _ {1}$

着目点

今回、「2019という数は10と互いに素な数になっている。なので、 $10 ^ {x} n$ が2019の倍数の時、 $n$ も2019の倍数になっている」ことがポイント。

例えば4038000(=2019*2*1000) を考えると、これが2019の倍数の時、4038が2019の倍数になっているということ。当たり前のように感じるが次のように役立つ。

4038333のような数が出てきた時、4038333 - 333 = 4038000 が2019の倍数だったならば、4038は2019の倍数となり、題意をみたす。
右からどこまでを0にするか？に注目しそうである（右からどこまでを引き算して0にしまうか？）
4038333 - 333 % 2019 == 0
4038333 % 2019 == 333 % 2019
余りの等しい連続する部分列のペアを取ってくれば良い！

言い換え

このことから、次のように言い換えることができる。

$a _ {l} a _ {l-1} \cdots a _ {r+1} a _ {r}$ が2019の倍数である。
$10 ^ {l - 1} a _ {l} + \cdots + 10 ^ {r -1} a _ {r}$ が2019の倍数である。（これを $X _ {l, r}$ とおく。）
$X _ {l, 0} - X _ {r - 1, 0}$ が2019の倍数である。（→累積和と似たような考え方になる。）
$(X _ {l, 0} - X _ {r-1, 0})\%2019=0$
$X _ {l, 0} \%2019=X _ {r-1, 0} \%2019$

同じ余りとなる $l, (r-1)$ のペアを探せば、題意を満たす整数の組になるということがわかる。

これは右の桁から順に数字を見ていき、2019で割った余りを $m$ とすると、map[m]++するなどして管理し、最後に各余りについて、二つ取る組み合わせを計算して足し上げれば良い。注意として、余りが0の数の場合、他の数とペアにしなくてもその数だけで題意を満たすため、map[0]=1 と初期化しておくことで他の場合と同じように計算ができる。

計算量は、 $O(Nlog(2019))$ となり、間に合う。（unordered_mapを使うとlogが取れる。）

この一連の求め方は、A - Zero-Sum Ranges でも同じような流れを踏むので見ておくと良いかもしれない。また、E - Divisible Substringでも似たような問題だったらしいがまだ解いていない。

解答

文字列だと右側から見ていく必要があるために、最初に文字列をreverseしてindexを扱いやすくしている。

また、桁数が非常に大きいため、桁数については別途modを取るようにしている。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define each(i, mp) for(auto& i:mp)

int main() {
    string s;
    cin >> s;
    map<ll, ll> mp;
    mp[0] = 1;
    reverse(s.begin(), s.end());
    ll now = 0, ten = 1;
    each(e, s) {
        now = (now + (e - '0') * ten) % 2019;
        ten *= 10;
        ten %= 2019;
        mp[now]++;
    }
    ll ans = 0;
    each(e, mp) {
        ans += e.second * (e.second - 1) / 2;
    }
    cout << ans << '\n';
    return 0;
}

Submission #12407239 - AtCoder Beginner Contest 164

2020-04-05

AtCoder: ABC161-D Lunlun Number (400)

atcoder 競技プログラミング解法メモ数え上げ数学

問題はこちら

atcoder.jp

以下の条件を満たす正の整数 $X$ のうち、小さい方から $K$ 番目のものを求めよ。

$X$ を10進数で表した時、隣り合うどの二つの桁の値についても、差の絶対値が1以下。

考え方

基本的に解説放送を聞いて自分の言葉に直しただけ。

www.youtube.com

まずは桁ごとに考えてみる。すると、今までに列挙した数の後ろに、条件を満たすような数を付け加えていけば良いということに気づく。

1 -> 10, 11, 12
10 -> 100, 101
11 -> 110, 111, 112
12 -> 121, 122, 123

今まで条件を満たしていた数 $x$ の一の位 $x_1$ は $x \% 10$ 。
よって、次に条件を満たす数は $x$ を10倍した数に、次に条件を満たす $x_1, x_1 + 1, x_1 - 1$ をつけたものになる。

これを全列挙しても $K$ 個程度までに答えが得られるので、間に合う。

解答

$K$ 個全列挙するため、桁ごとに列挙したものの数を減らしていき、 $K$ が列挙してある数よりも小さくなった時、値を出力する。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ll k;
    cin >> k;
    vector<ll> a;
    for (ll i = 1; i <= 9; ++i) a.emplace_back(i);

    while (k > a.size()) {
        k -= a.size();
        vector<ll> old = a;
        a = vector<ll>();
        for (ll x: old) {
            for (ll i = -1; i <= 1; ++i) {
                ll d = x % 10 + i;
                if (d < 0 || 9 < d) continue;
                ll nx = x * 10 + d;
                a.emplace_back(nx);
            }
        }
    }
    cout << a[k - 1] << '\n';
    return 0;
}

Submission #11557806 - AtCoder Beginner Contest 161

論文の読み方

どれくらいの論文を読むか

一つの論文の読み進め方

読み終わったらすること

情報収集

数学パートについて

コードについて

大事なこと

問題はこちら

考え方

解答

問題はこちら

考え方

解答

第1章 試験という「道具」を理解する

1.1 試験は「能力を測定するための道具=問題」の集合体

1.2 試験と擬似性格検査とアンケート

1.3 単一の尺度のによる測定

1.4 ハイ・ステークスな試験のために：信頼性と妥当性の確保

学習者要因の影響

過去の学力

態度と気質

就学前教育

家庭要因の影響

社会的な地位

家族構成

学校要因の影響

学校構成の効果

学級構成の効果

学級の風土

問題はこちら

考え方

はじめに

着目点

言い換え

解答

問題はこちら

考え方

解答

第1章試験という「道具」を理解する