Joeの精進記録

旧：競プロ練習記録

卒論を書きました

前回の投稿から一ヶ月以上空いてしまったので何か書こうかなと思いまして、先日無事書き終えた卒論を振り返ってみようと思います。

TLDR;

卒論を提出しました。

ほんとこれだけ。あとの内容は通学/通勤電車とかで暇な人がみるとよいかも。 急ぎなら後半を読むと切迫感があって面白いかもしれません（適当）

読者層

B3以下→機械学習の研究分野の紹介 or 卒業研究の流れの紹介だと思って読むとよさそうです。専門用語少なめにしているのでご安心ください。

B4→おつかれさまです。

M1以上/教員→B4の苦悩を見るなり、自分の過去と照らし合わせるなりしてください。教員氏、優上をくれ。

9月下旬

大学のAセメスターが始まりました。うちの学科ではこのタイミングでやっと研究室配属が行われ、2/1の卒論締切までを期限として卒業研究をすることになります。

ICPC Programming Boot Camp at Barcelonaに行く

研究室の教員曰く、理想的なペースは、9月10月にいろいろ論文を読んでテーマを探し、11月から研究を始められたら最高。12月から始めてもまあ大丈夫、というペースでした。これならさすがに9月は競プロしかしなくても大丈夫そうと思って、競プロ中心の生活をしていました。バルセロナは普通に楽しかったです。

10月前半

テーマ探しスタート

バルセロナから帰国します。うちの機械学習系のメジャー学会をいくつか知り、ICML, NIPS, ICLRなどのpaper一覧という便利なサイトが存在することを教えられます。とりあえずいくつか楽しそうなものを探してみました。この時点ではあまりにやりたいことが決まっていないためタイトルがかっこよさそうなものを選びました。めっちゃ多いのですが、自分のメモの最初の10個を列挙すると

  • Quickshift++: Provably Good Initializations for Sample-Based Mean Shift
  • Active Testing: An Efficient and Robust Framework for Estimating Accuracy
  • Synthesizing Robust Adversarial Examples
  • Nonconvex Optimization for Regression with Fairness Constraints
  • On the Relationship between Data Efficiency and Error for Uncertainty Sampling
  • $D2$: Decentralized Training over Decentralized Data
  • Network Global Testing by Counting Graphlets
  • Adversarial Attack on Graph Structured Data
  • Learning Memory Access Patterns
  • Noise2Noise: Learning Image Restoration without Clean Data

などに目をつけました。10月上旬はこれで終わりです（今思うと何もやってねぇ〜）

10月後半

アイデア出し

データ圧縮

なんかニューラルネットで破損したデータを復元するような研究ってどれぐらいあるのかということに興味を持って、とくにうまく復元できるようであれば、データ容量を大幅に落としてデータを管理できるんじゃないかと思いました。ICML, NIPSで関連研究を調べると皆無だったのでキターーーーーーと思いましたが、教員に相談したところ別学会を紹介され、「あっはい、、」という気分になりました。

  • Data compression and prediction using machine learning for industrial IoT
  • Enhanced Intra Prediction with Recurrent Neural Network in Video Coding
  • Research of image deblurring based on the deep neural network
  • Lossless Image Compression Using Reversible Integer Wavelet Transforms and Convolutional Neural Networks
  • Joint Source-Channel Coding with Neural Networks for Analog Data Compression and Storage

こんな感じの関連研究がいくつかありました。今思うと、これを進めても全然よかったかなとは思います（具体的なフォーマットに絞って研究すると、かぶってないのもありそうだし、普通に実用性あるんじゃ）。しかし、当時は「はい被った〜〜〜〜〜〜〜」みたいな意識があまりに強くて、さらにリサーチ序盤だったので無理そうなやつは深入りする前に早めに切ろうと思っていたので深入りせずに終わってしまいました。

組合せ問題を解く

これは演習３とよばれる研究室巡りの授業で、自分がちょっと触れた分野だったのでとっつきやすかったです。

  • Artificial Neural Networks that Learn to Satisfy Logic Constraints
  • Near-optimal linear decision trees for k-SUM and related problems

ここで紹介する論文とはかなり内容が異なりますが、研究室同期で最終的にこの分野を選んだ人はいました。

異常検知

これも有名な分野ですね。個人的にはプログラムの不備を検知してsuggestionしてくれるAIとかは自分がコーディングする上でもほしかったので、この研究をしてみたいと思いました。

これも面白そうではあるんですが、深入りせずに終わってしまいました。

GAN

GANというものをここに来て初めて知ります。知らない人向けに説明すると、GANとはgenerative adversarial networksの略で、生成ネットワークと識別ネットワークとよばれる２つのネットワークを組合せたネットワークです。画像生成とかによく使われますが、画像を生成するネットワークと、生成された画像と本物の画像を区別するネットワークを並列して学習させることでお互いの精度をあげる、という構図になっています。

うちの研究室では、GANで何かをやる！というよりかは理論保証を与えたりする流れだと思うので、GANがどういう条件のときに収束するか、などを研究しようと思ったりしていました。

それと、GANで超高解像度の画像を生成しようとしても莫大な時間がかかってしまうので、機械学習アルゴリズムで画像の解像度をあげる研究とかないのかなってのも検索していました。

学習限界

これはもしかしてそんなに研究されていないかもしれませんが（あんまり耳に入らない）、ある分布に従うある量のサンプルが与えられたときに、どこまで精度をあげられるか/どこまで情報を抽出できるか、ということに素で疑問をもって、調べようと思いました。さすがに先行研究が無限にありそうですけどね。

オンライン学習

  • Online Learning with a Hint

という論文があって、わりと解析的なことをしていて楽しそうだなと思いました。

という感じで、10月後半はわりと下調べはしたものの、自分の方針自体は何も決まりませんでした。こうやって書くとかなり調べてそうに見えますが、作業時間は3日ぐらいで、ほかはずっと競プロをしていた気がします。

11月上旬

当初教員が「11月から始められれば良い方」と言っていたので、「ふぁ〜悪い方になっちゃったか〜〜」とか思いながら研究内容を決めようとする。しかし、実際にはまだそれほど焦っていなかったりする。

テーマを決める（１）

ディープラーニングの研究全般がものすごい学習時間を要するのが嫌いだったので（実験に手間がかかるし、人によってかける時間が違っていて、特に大企業とかが圧倒的計算資源で殴っている感じがしてhogeだったので）、ディープラーニングの計算量を少なくする研究をしようと思いました。

具体的には行列はそこまで密でなくてもネットワークは十分複雑になるはずなので、疎行列からなるネットワークや、必要に応じて、密度を変化させる（疎→密）ネットワークについて考えていました。

  • Sparse Deep Neural Network Exact Solutions
  • Learning Sparse Neural Networks Through L0 Regularization
  • Deep Rewiring: Training very sparse deep networks

数日間これをやっていましたが、教員氏に、「最近のTPUとかは密行列の計算にすごく最適化されていて、疎行列よりむしろ速い」という本質的な指摘を受け、やる気が0になります。まあCPU環境だとたしかに強いと思うけどそういやぁディープラーニングは全然CPU環境じゃなかったですね、、、、、、

アイデア出し（２）

いろいろな構造のネットワーク

ぼくはデータ構造が好きなのでディープラーニングにももっと多様な構造がほしいなあと思って行列ガリガリ以外のディープネットワークを調べました。 Deep Random Forestとかに興味を持ちましたが、深入りせずに終了

ディープラーニング界隈は細かいdivisionが多すぎて全部に詳しい人は本当に永遠に論文をチェックしているんだなあという気分になる。

Adversarial attackから守る

専門用語かもしれないので解説すると、ディープネットワークをある微分可能な関数としてみると、入力を微変動させると出力もそれに従って変動します。出力を誤った方向にシフトさせるように、もとの入力に一見酷似するようなノイズ付き入力をネットワークに与える攻撃をadversarial attackといいます。ディープネットワークでは入力のベクトルの次元が数百とか数千になることがざらにあるので、各要素ごとに調整することで、要素ごとのノイズを小さく抑えたまま、ネットワークの出力を大幅に変えることができます。

研究室の先輩がこれをやっていてかなり第一人者っぽいし、演習３ではこれをやったのでわりと最初からアンテナは張っていました。 ネットワークの枝を学習時にランダムに切る、dropoutという手法は過学習を防ぐ上でメジャーですが、推論時に切るのはあまり見たことがなかったのでそれをやってみようと思いました。よさそう！という反応をしてくれた人もいましたが、なんかそこまで熱中できなくて終了してしまいました。

11月下旬

CODE FESTIVALに参戦したり駒場祭してたりしました。ポケモンの新作が想像以上に楽しかったです。

初日にイーブイの色違いを捕まえて多少バズりました。

テーマを決める（２）

もうこれアイデア出しと厳密な区切り目がないので（２）なのかどうかもわかりませんが、雑な区切りめとして、一週間近く以上同じものをやり続けた場合、テーマの方に分類しようと思います。 今回は凸最適化をやろうと思ったわけなんですが、なんかDeepMindから - Hamiltonian Descent Methods というすごい論文が出てて、話題だったし、わりと好きな分野だったので読もうと思いました。しかし、ページ数が80ページ近くある上に、 凸最適化問題における双対とかいう概念とか知らないことが多すぎて、25ページぐらいまで追ったあたりで、絶対に卒論期間に間に合わないと見切り、諦めることにしました。研究室の先輩とご飯にいくと、みんな口を揃えて「あれはやばい」とか「卒論でやるのはさすがに無理そう」というので「まあ。。。。」みたいな気分でした（語彙力）。

12月上旬

abstの締切が12/14だったので上旬になんとかしなければ！という気持ちになってきます。 さすがに危機感を多少覚えてきました。それまでアイデア等はSlackの自分とのDMに書いてきたのですが、膨れ上がってきたので自分でチャンネルを作ることにしました（↑のメモはたいていそこから）。

この頃、ツイッターのユーザ名を”Joe@卒論RTA”にしました。

テーマを決める（３）

上の画像の最後に書いていますが、複素数パラメータのネットワークを考えることにしました。実数パラメータのネットワークが中心ですが、複素数に拡張しようとするのはすごい自然だと思って、数日間取り組んでいました。

  • Deep Complex Networks

を読むが、複素数のメリットが皆無でhogeだった。なんかよくよく考えればわかりますが、実数ベクトルの次元を2倍にしただけでは？という気分になる。本人も複素数を用いているメリットを説明できていないし、open reviewを読むと同じ指摘がされていて厳しい。 個人的に複素数に興味を見出したのは、実部虚部という分け方以外に絶対値と偏角という分け方があって、後者はたとえば分類問題を考えるときに偏角の方向をターゲットのクラスに対応させられるのでは？と思ったけど、よくよく考えるとちょっとむずかしい。

調べると似たような話があった。

  • Complex-valued unsupervised convolutional neural networks for sleep stage classification.

関連論文を調べると他にも

  • A Fast Learning Complex-valued Neural Classifier for real-valued classification problems
  • Complex-valued convolutional neural networks for real-valued image classification
  • A mathematical motivation for complex-valued convolutional networks
  • Complex-valued neural network using magnitude encoding technique for real-valued classification problems & time series prediction
  • Orthogonality of decision boundaries in complex-valued neural networks

などが見つかる。これらは割と古い論文で、ディープではなく1層だけになっているものとかもある。

他に興味を持った点として、複素数演算の演算結果の実部と虚部は独立ではないので、実部で学習し、（実部となんらかの相関をもつ）虚部をチェックに使えないかなと思った。パリティチェック的な。パリティじゃないけど。

これをしばらく考えるが、そもそもadversarial attackを弾こうと思っても、adversarial attackは通常、学習時にはまったく経験しないタイプのinputがくるわけで、これをいきなり弾くのは直感的にむずかしそうという気分になる。見たことない入力時に出力をしないdeep abstain networkというのもあるが、deep abstain networkの論文ではadversarialについては考えていなく、通常の学習時に、判断できなそうなものをスルーする学習手法だったので、adversarialを学習時に判別させるのは話が違いそう。

結果、しばらく複素数ネットワークをやってみるも、それ複素数でなくても実数で実現できる、という結果にすべて帰着されてしまう（量子コンピュータならアレだけどいまのコンピュータなら複素数演算は全部実数でそりゃ置き換えられるし）ので厳しい気持ちになる。↑の複素数の研究をした人は一体どういうモチベでやったんだろうか。

テーマを決める（４）

突然天才的なアイデアがひらめく。adversarial noiseが入った入力に対して、それを更にごちゃごちゃにするぐらいの強いノイズをかけて、その上でネットワークに投げると逆に精度あがるんじゃないかと思った。さすがに実装が容易なのですぐに実験する。

全体の精度は下がるがadversarialをかなり守れるのでうれしい。アイデアもシンプルで実験もしやすいしさすがに優勝したんじゃないかと思う。理論保証は直感的にはすぐ思い浮かばないが、解析しやすそうな形をしているので、微積を鬼のようにすればなんとかできるんじゃないかと思った。

ちょっと話はそれるが、ノイズってなんだろうと考えたりする。ガウシアンノイズは簡単に弾けるが、adversarial noiseは全然規則正しいノイズではない。波うっていたり、斜め線の模様になっていたり、要は他の特徴量だと間違えられるような模様のノイズになるわけで、でもこういう模様みたいなノイズを一律して弾こうとすると本来の特徴量も弾いてしまうことになるので難しい。まあでも、ノイズを全体に散りばめてadversarialなノイズをかき消すのは、解析して見る価値がありそうだとは思う。

  • Adversarial-Playground: A Visualization Suite Showing How Adversarial Examples Fool Deep Learning

では、adversarialノイズがどういうニセの特徴量を埋め込んでいるかがビジュアライズされていて楽しい。

調べてみると、ノイズを混ぜることによる正則化の研究は昔からわりとある。 - Adding noise to the input of a model trained with a regularized objective - Training with Noise is Equivalent to Tikhonov Regularization - Robustness and Generalization - Robust Large Margin Deep Neural Networks わりとニアミス感があるが、まだ被っていないと信じていた・・・

被る

いろいろ研究を追っていると

  • Towards Robust Neural Networks via Random Self-ensemble

という論文ともろ被りしていることに気づく。2018年8月なので4ヶ月前・・・・・・。ネットワークの各レイヤーの前にノイズを入れるレイヤーを加えることによって正則化する論文だった。理論保証も自分が途中まで考えたものの後半を完璧にやってくれていて完全敗北する。

無理矢理でも新規性を付け加えようとする

ノイズを入れたあとにnoiseを取るとadversarial noiseも薄くなるのではと思う。ノイズを除去するにはFourier変換やWavelet変換が有名で、これも手元で実験すると普通にうまくいく。各層の前にnoise層とwavelet層みたいなのを用意するといいんじゃないかと思うが、wavelet neural networkみたいなものを勉強してもいまいちピンとこないし、理論保証的な側面でもどうやって進めればよいか全然ピンとこなくて、hogeみたいな卒論になってしまいそうと危惧する。

教員にキレる

この辺で不機嫌さがピークに達しており、それなりにこれまでも下調べをしてきているのにテーマが決まらない焦りと、数日後に迫ったabst締切に挟まれて、教員にメールをしてアイデアの評価やフォローを欲していたにもかかわらず、ためになるアドバイスがまったく得られなかったのでメールでちょっと怒ってしまいました。後日聞くと研究室で広まってて草

まあこれは、それまでのミーティングや研究室メンバーとのコミュニケーションを軽視してabst締切直前まで一人でやってきて、でもそれが無理だということに気づいて突然教員に絡みだしたわけですから、教員側からするとかなり「！？」という感じでぼくにも全然非はあるわけですが、一応名目上は指導教員なわけですし、もう少し内容のあるアドバイスがほしいなあと思っていた感じでした。

アイデア出し（３）

このタイミングでアイデア出すのやばすぎるな〜と思いながらアイデアを出そうとふんばります。あまりにもテーマを変えすぎているせいで教員と面談をすると第一声が「テーマは以前と同じですか？」になります。やめてえ〜〜〜〜〜

画像のrotateに不変なCNNネットワークとかを見たので、すごそうと思ってちょっと追ってみました。画像のアフィン変換についてロバストなやつでも考えるか〜という気持ちになるんですが、論文が被ったショックで深入りできず。病む。病むと他人を食事に誘いがちなんですが、これわかりますか？研究室の先輩と食事にいっていろいろ相談しました。

先輩の話だとやっぱり、無からいきなりテーマを見つけようとするのは至難の業。自分はこれまでを振り返っても、ある特定のテーマ一本で調べて、画期的な改善をすることを望みすぎていた感がありました。先輩は複数の分野の研究を融合するような研究をして、普通に国際学会に通す論文を生成したので、すごいなあと思いながら、先輩の研究分野の話も聞きつつ、アイデア出しを手伝ってもらいました。abstの締切までもう3日とかでした。

ぼくのもともとのアイデアであった、入力にノイズを加えるというやつも、入力がベクトルでない場合（たとえばグラフや集合など、ノイズが非自明である場合）のアプローチを考えるのはさすがに新規性では？みたいな話を聞いたりして、天才か？という気分になるなどしました。

さて、いろいろためになる議論をしたわけですが、ここで、transductive learningという言葉を初めて耳にします。transductive learningとは、データセットのうち一部だけにラベルがついていて、目標はデータセットのデータのうちラベルがついていないものにラベルを割り振ることです。一般の半教師あり学習と異なる点としては、未知なデータにラベルを振り分けることではなく、データセット内の他データのみをターゲットとすることです。

たいていこういう場合、要素の類似度に注目してデータのインスタンスを頂点とするようなグラフを作り、グラフ上でラベルを伝搬させていくという操作を考えます。

  • New regularized algorithm for transductive learning
  • Revisiting Semi-Supervised Learning with Graph Embeddings

などには、YouTubeの動画サジェッションで使われるアルゴリズムである、Adsorptionアルゴリズムや、その改良版のMADアルゴリズムが紹介されており、この路線でやっていくことにしました。当初のアイデアとして、伝搬させると同時に、ランダムに選んだノードのラベルを削除することで、より安定するのではないか？と思って、とりあえず暫定的に卒論のabstとタイトルはそれっぽいことを書いて提出しました。

12月下旬

さすがにそろそろ本気をださねばと思い、ツイッターを卒論仕様にしました。

これすごくたくさんのいいねをもらって応援していただきました。精神を安定させる上で本当に助かりました。フォロワーの皆様本当にありがとうございます。

テーマ決定（５）（嘘）

とりあえずabstをこれで出してしまったわけですし、先行研究を追うことにしました。 adsorptionアルゴリズムは、あまりにヒューリスティックスの塊で、ハイパーパラメータを適当に選んだり、収束性が謎すぎるなどして、ちゃんと理論的に追うべき箇所はたくさんありました。MADアルゴリズムに関する論文で、adsorptionアルゴリズムは、ある目的関数を最小化するようなアルゴリズムになっていないことが指摘されていたので、自分的にはある目的関数を最小化するようなアルゴリズムを提案しようと思いました。

adsorptionアルゴリズムをもう一度紹介しておくと、グラフが与えられ、いくつかの頂点にラベルが付いているとき、同じラベルを持つ頂点同士が重みの大きい辺で繋がれるように、ラベルがついていない頂点にラベルを伝搬させていくアルゴリズムです。adsorptionではこれをランダムウォーク的に行います。

勘のいい方はもうお気付きかもしれませんが、これは実質グラフの頂点に関するクラスタリングを考えているようなものですね。これまでぼくも何度か課題でクラスタリングを実装しましたが、それは実数ベクトルで表されるデータ（つまりユークリッド空間上の点）のクラスタリングであり、グラフのノードのクラスタリングを考えるのは初めてでした。グラフのクラスタリングって他にどういう手法があるんだろうと思っていくつか調べてみました。

そうすると

www.slideshare.net

などのスライドに出会うんですが、グラフのクラスタリングはグラフラプラシアンとよばれる量の固有値問題と深い関係があって、たいていグラフラプラシアンを固有値分解することに寄って解かれることがわかりました。

グラフラプラシアンの固有値問題は、実はRatioCutとよばれるある目的関数を最小化する問題と等価になるんですが、この目的関数がいまいち直感に反するというか、「ほんとにそれ最小化して、良いクラスタリングできるの？」という感じがしました。まあRatioCutを最小化する手法は、定式化のしやすさから非常に意味があると思いますが、結果のクラスタリングが納得行くものかといわれると微妙だと思いました。

そもそも、何を最適化クラスタリングとするかは当然目的関数によって異なっていて、なのでぼくはこれよりも良さそうな目的関数を作ろうと思いました。

そこで次のような目的関数を考えることにしました。

グラフをいくつかのクラスタにわけてクラスタ間の辺の重みと、クラスタ間の辺の重みを考え、前者は大きければ大きいほどよく、後者は小さければ小さいほど良いので、（前者マイナス後者）を目的関数としてはどうだろうか、と考えました。かなり自然ですね。

しかし、しばらく離散数学をするとこの最適化問題がNP-hardであることに気付かされます。しかしまあ大抵の最適化問題はNP-hardなのでここで諦めるには早すぎて、近似アルゴリズムを考えることにしました。

ここの流れを細かく書くだけでも一部の読者は非常に楽しんでくれそうですが、今回の記事の目的とは大きく離れてしまうのでながれをざっと書くことにします。 ぼくの目的関数は、グラフにおけるmax-cut問題と関連付けることができて、max-cut問題には実は0.87856近似アルゴリズムが存在します。

  • Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming

要は、本来の最適解をMとするときに、0.87856M以上のcutを保証するようなグラフの分割を計算できるアルゴリズムです。しかも元論文では、ランダムグラフではこれよりずっとよい近似率を実験的に確かめた、ということが書いてあって、これだーーー！！と思いました。

で、ぼくの目的関数を同様に近似して最適解することを目指したんですが、どうしても頂点数 Nに対して O(N^3)の計算量がかかってしまいます。

指導教員に相談したところ、面白そうだけどそこまで計算量がかかっちゃうとね〜〜〜〜という感じでした。ぼくはまあでも最悪卒論の内容にはなるかなと思って久しぶりにちょっと一息していました。このタイミングでツイッターのアカウント名をJoe@卒論★★☆☆☆に変えた気がします。

1月上旬

年末年始はいろいろイベントがあったので卒論を忘れて人生を楽しみました。昨年度は研究室のミーティング等にまったく参加しなかったのでその反省として2019年は全参しようと思って意気込みました。

ぼくの当面の課題としては、まあ適当に論文を書きつつ、 O(N^3)という計算量をなんとか下げられないかなと思っていました。 O(N^3)は競プロでは完全に行列積だったりワーシャルフロイドだったりで激遅アルゴリズムの部類なので、うーーーんといいながら作業していました。

・・・・？

ワーシャルフロイド・・・？

距離じゃん

そういやK-means（ユークリッド空間のデータ点のクラスタリングアルゴリズム）も距離ベースで最適化行うな・・・

O(N^3)で全頂点対距離求まるならそれを求めてK-meansを同じことをやっても計算量変わらんってことか・・・

ん？それ全頂点対求める必要ある？

ダイクストラ数回やればよくない？

え？普通に速そうだしよさそう

テーマ変更（真）

1/10ぐらいでした。卒論締切までは3週間程度でした。とりあえず手元で雑にダイクストラを書いて実験します。さすがに競プロで無限回書いたので実験はテストケース生成等も含めて30分程度で終了しました。結果、よい！！！！！！！！！

とりあえずこれベースで論文を書くことにしました。本来、アカウント名は定義からするとJoe@卒論★★☆☆☆のままなんですが、明らかな進捗なのでJoe@卒論★★★☆☆にしました。

ちょっと研究を進めていくうちに、K-meansの理論保証付きアルゴリズムである派生版の存在も知りました。その理論保証を今回の場合に拡張できるかは定かではなかったですが、まあ頭に余裕があればやろうという感じで考えていました。

新年初の教員面談で案の定「前回とテーマは同じですか？」から始まり、ぼくも「いえ、変わりました」と答えて面談がスタートします。 教員もすごく興味をもってくれて、キターーーーーーーー！！！！！！と思いました。教員に理論保証はつくの？と聞かれて、何も証明していないのに「はいつきます」と雑に答えてしまいました（おかげでやらなければというモチベにつながったんですが）

その後1週間ぐらいは理論保証をやっていました。理論保証に関する論文を読むと、その中に現れるいくつかの不等式を自分の設定の場合でも示せたので、同様のロジックで示せそうだということがわかりました。

さすがに残り半月なので、いそいで論文を書くことにします。なんか当初語数が足りないと散々脅されていたので、めちゃくちゃ丁寧に書きました。グラフの定義、次数とは何か、隣接行列とは何かなど・・・

一応やったこととしてはK-meansを拡張するということですが、グラフのクラスタリング手法（12月下旬にいろいろ調べていたもの）とせっかくだから比較しようということになって、それらの説明もグダグダ書いているとすごい語数が膨れ上がってしまいました。

半分ぐらい書いたところで、証明があまりに長いので語数を気にする必要がないことを気づきます。 なんかグラフの定義とかも書き出すとキリがないし、競合アルゴリズムを詳細に解説したところでべつにそれを発展させるわけではないのでただただ読みにくさが増してるだけな気がしてきました。なので全部イチから書き直すことにしました。

とりあえず実験のチャプターまで書いて、教員に提出してレビューを待つことにしました。このときJoe@卒論★★★★☆にしました。待つ間数日暇なので、ちょっと気になっていた、上述したものとは異なる別アプローチの理論保証も今回の提案手法の場合に成り立たないかを考えてみることにしました。

直感的にはこれまた成り立ちそうなんですが、なんせアプローチが１つ目の証明と全然違うため、証明に苦戦します。

2/1締切ですが、写真は1/26の画像ですね・・・今思い返してもよく頑張ったと思います。

この日の夜にやっとその手法についても理論保証が与えられることが証明できました。理論保証がゆるすぎたので次の日に多少評価を改善するなどして、残された数日で論文を書ききることになります。

CodeforcesでDiv1にあがる

ちょっと時系列が前後しますが、実は1/23にこどふぉでDiv1にあがりました。これが本当に助かって、なぜなら2019年の目標をratedこどふぉ全参にしていたため、ここでDiv1に上がっていないと、卒論締切最後の週にある3回のDiv2（うち1回は締切前日深夜）に参戦することになって、明らかに卒論がやばいです。

1/27（締切5日前）

２つ目の証明を書く。これがかなり長い。一日中書いていた。実験のチャプターとconclusionを雑に生成してとりあえず最後まで書ききって教員に送る。

1/28（締切4日前）

やっと教員のレビューを読む時間ができたので、これまで溜まっていた（それほど溜まっていなかった）レビューを元に前半を校正する。校正し終えたところで、実験のチャプターの内容があまりに薄いので全部やり直そうと思う。

1/29（締切3日前）

実験プログラムを拡張しやすいように全部書き換える。レポジトリを公開するのに読みやすいようにかなりきれいに書き直した。また、もともとバグらせたままにして未実験になっていたやつなどをデバッグして直した。データ生成を自分でやったが、生成するグラフのパラメータを毎回手で調整するのが大変だったので自動化スクリプトを書いて、コマンド一つで論文の実験結果を再現できるようにしようと思った。これがかなり重い。

1/30（締切2日前）

実装を終わらせ、実験を全部やり直す。それまでは数値だけの表だけで、一切visualizeしていなかったのでpythonでもろもろのvisualizeをする。 さらに添削が返ってきたので、それを校正するなどする。

夜に実験部分を書き直し、校正も反映させて再提出

1/31（締切前日）

教員の添削がほぼほぼ英語なので、自分でも読み直して全部校正しようと思う。夜になってやっと英語の校正が完了する。それまで図表のキャプションは雑に書いていたが図表にもちゃんと説明文を入れることにした。

Conclusionが雑だったのでしっかり書いた。

同期３人が研究室に泊まることになったので景気づけにお寿司

こどふぉDiv1なおかげで深夜のDiv2コンテストを華麗にスルー

2/1（締切当日）

とりあえず自分の論文は全部読み直したし、教員からの校正も数箇所だけのレベルになったので、あとでもう一度読み直そうと思って、そのかわり教員のレビューがまったく進んでいなかった学科同期残り２名の論文をかわりに添削する。

一応初提出しておく（上書き提出が可能）

このためのbigEnter!!!!!!!

正直間に合うと思っていたのでちょっと他人に時間を割く。

当然徹夜。自分の論文２周めを読む。１週目ではアルゴリズム記述部分などはスルーしていたので、今回はちゃんとそこも追う。するとかなりfontなどに関する誤植が見つかって大忙しになる。また、先輩が、文献はbibtex丸コピだと、secondと2ndみたいに統一されてない箇所があってきれいではない、みたいな話も聞いて、そこも全部調整し直す。他にも、オーダー記法のbigOのフォントや、もろもろの細かい指摘を聞いて全部直す。普通に忙しすぎる。

指導教員が締め切り朝に、提案手法の名前おかしくね？みたいなメールを送ってきて、「！？！？！？！？！？！？！？！？！？！？！？」となる。このタイミングで言わないでくれーとなるが、研究室の先輩に相談すると、「ああ、よくあるよくある、俺も同じこと締切当日に言われた」みたいな反応を受けれぽかーんとなる。

さすがにアレなので、教員にあとで部屋にきて口頭でディスカッションしましょうみたいなメールを返信して自分の添削に全神経を傾ける。

教員がそのうち入ってきて、やっと教員が引っかかっていた点を理解したので直す。しかし、締切が近すぎて、もうレビューしてもらう時間がない！

締切18分前

結局ギリギリまで直して1分30秒前に最終盤を提出し、卒業研究が終了しました。

さいごに

長々しい文章を最後まで読んでくださってありがとうございます。なんか、いろいろありましたが、とりあえず形になる論文がかけてよかったかなと思います。研究室の先輩方にはいろいろ本当にお世話になりました。来年はつらそうな後輩がいたら声をかけてあげるやさしい先輩になろうと思っています。 指導教員の先生方もありがとうございました。優上をください（２回め）

文章を読み直していないのでかなり文体とかがごちゃごちゃになっていると思います。お許しください