FAQ: Alan Turing

以下はブレッチリー・パークのサイトで公開されている アラン・チューリングに関するFAQその日本語訳 です。

原文は以下で掲載されています。

bletchleypark.org.uk


Turing FAQ

Pre-war

No QA Desc.
1. Q When did Alan start to figure out that he liked mathematics and coding?
1. A He seemed to be generally interested in the way things work from a very early age. He is often described as a ‘polymath’, which is someone whose interests and expertise span a wide variety of subjects. It may be that Turing discovered that mathematics was a great framework for investigating all the many and varied things that he was interested in. He became interested in codes and ciphers as a child, solving and creating related puzzles and problems for fun.
2. Q What projects was Alan working on before World War Two?
2. A Before the war, Turing was working on the Entscheidungsproblem (“decision problem” in German), which is what his paper On Computable Numbers was about. The problem looks at mathematical statements and asks if it’s possible to find a technique that will allow someone to work out if any given statement is provable or not. Turing proved that there was no such technique. Building on this, Turing began to work on what is often now referred to as a Turing machine. This was a hypothetical computing machine that could give a result from set of variables, following a list of rules. This is similar to the idea of a computer programme today. A machine that could do this did not exist in 1936, and it would be another nine years before technology had developed enough to test his ideas.
3. Q Did Alan ever give up on any projects or machines he was working on?
3. A In 1939 he was working on a machine that was designed to solve problems related to the Riemann Hypothesis (one of the Millennium Problems). It was called the Zeta-Function Machine and was partially constructed but abandoned due to the outbreak of war.


At Bletchley Park

No QA Desc.
4. Q Which building at Bletchley Park did Alan Turing work in?
4. A He famously headed Hut 8 at Bletchley Park, but he didn't work there for the whole war. He designed the Bombe in the spring of 1940 while part of Dilly Knox’s Enigma Research Section, based in Cottage 2. Hut 8 was completed in early 1940 and Turing took on the running of it in 1941. In 1942, he visited America to work with them on their Bombe design, liaising with them on the U-boat Enigma problem. In 1943, he began working at Hanslope Park, which isn't far from Bletchley Park, developing a speech decryption programme known as Delilah.
More about Hut 8: http://bit.ly/Wiki_Hut8
5. Q What was being done to crack Enigma before Turing?
5. A Three Polish mathematicians made breakthroughs in the mid-1930s, developing a machine (known as a Bomba) to help break the codes. Much of the early work on breaking Enigma focussed on repetition of the message key (specifically starting positions of the rotors) as well as several key phrases used in messages (known as “cribs”). Vital intelligence was passed to the Polish cryptanalysts and Marian Rejewski was able to deduce the internal wiring of the Enigma rotors, meaning the Polish could build a replica Enigma machine. They passed what they had achieved to Bletchley Park just before WWII began, but by this time Germany had upgraded its Enigma usage procedures. It is likely that the Polish codebreakers, after having escaped to Paris, made the first wartime break on 17 January 1940, with Turing present. The first team at Bletchley Park to break into an Enigma encrypted message was Gordon Welchman’s team in Hut 6 , with John Jeffreys overseeing use of the punched sheets utilised for the task.
See the Polish Memorial at Bletchley Park: http://bit.ly/Maps_PolishMemorial
More about Polish work on breaking Enigma: http://bit.ly/Wiki_PolishContribution
More about Bomba: http://bit.ly/Wiki_Bomba
More about breaking Enigma: http://bit.ly/Wiki_BreakingEnigma
6. Q How did Alan Turing contribute to cracking Enigma?
6. A It’s important to note that Turing was not the first person to break Enigma (see Q.5). Turing improved the processes for breaking various versions of Enigma by developing more efficient codebreaking techniques, such as Banburismus. He also contributed to the breaking of other ciphers, such as his method for unpacking part of the Lorenz cipher, known as Turingery.
His most famous achievement was to design a machine, the Bombe, that would perform some of these codebreaking techniques quicker than a human could. The German Navy’s “M3” Enigma machines were unbreakable at this time due to more secure message key procedures, so Turing started working on this version of the cipher. Later in the war, when the German Navy started using an updated version of Enigma (the M4) and Bletchley Park couldn’t read the Naval messages any more, he took on the responsibility of developing techniques that would work on this new machine.
More about Banburismus: http://bit.ly/Wiki_Banburismus
7. Q Who did Alan Turing work with to crack Enigma?
7. A Turing worked as part of a large organisation of people working on breaking Enigma, so the people he worked with were many and varied. At the beginning of the war, Turing worked directly with the Poles in France which fed into his ongoing codebreaking work. His design for the Bombe machine was no doubt inspired by an earlier version, called the Bomba, that was built by the Polish Codebreakers (see Q.5). He worked alongside Gordon Welchman who devised an improvement to the Bombe machine (his addition was known as the “diagonal board”, which reduced the number of false results). Turing also spent some time in America, working with American cryptanalysts on various things, including a US Naval version of the Bombe. During his time at Bletchley Park he worked as part of a team in Hut 8 to break Naval Enigma.
Find out more about Gordon Welchman: http://bit.ly/BP_GordonWelchman
Find out about other people who worked in Hut 8: http://bit.ly/BP_Hut8Personnel
Find out more about the US Bombe machines: http://bit.ly/Wiki_USBombe
8. Q What contribution did Turing make towards World War Two?
8. A Turing made many contributions towards the war, but there are five advances that Turing made in the field of cryptanalysis that are particularly notable:
1. Designing the Bombe (see the Enigma and the Bombe document in this series).
2. Deducing the German Navy’s indicator procedure.
3. Making Bombe machine use much more efficient with a technique called Banburismus (see Q.6).
4. Devising a procedure (known as “Turingery”) for working out the cam settings on Lorenz machine wheels.
5. Working towards the development of a portable voice-scrambling system called Delilah[1]. This was never finished, but his work undoubtedly informed later developments.
Find out more about Turingery: http://bit.ly/Wiki_Turingery
9. Q What did Alan Turing do to pass the time whilst he was outside Bletchley Park?
9. A Turing was interested in a great many things, including long distance running for which he was very nearly in an Olympic team. He also played chess (although he wasn’t as good as some of his fellow Codebreakers, like Hugh Alexander) and liked to conduct chemistry experiments in his home, though perhaps not whilst he was working at Bletchley Park. A notebook written by Alan Turing during his time as a Codebreaker, however, does demonstrate that he was spending much of his free time continuing his own studies in Mathematics.
Read a transcript of part of an interview with the secretary of an athletics club of which Turing was a member: http://bit.ly/TuringasaRunner
10. Q How significant was Turing’s contribution and the Bombe to winning the war?
10. A Many historians believe that Allied victory was inevitable; it was just a matter of how long it would take. Turing contributed significantly to the work being done at Bletchley Park and his Bombe machines did undoubtedly speed up the breaking of certain types of enemy ciphers (See Q.6). His work specifically on decrypting German Naval Enigma contributed to the Allies’ success in the Battle of the Atlantic, allowing vital supplies to arrive in Britain from North America in time for D-Day in 1944. It's important to note that the same is true of a great many people who worked at Bletchley Park during World War II: brilliant minds and hard work came together to solve a seemingly insurmountable problem.
Find out more about the Battle of the Atlantic: http://bit.ly/BBC_BattleoftheAtlantic


Post-war and Legacy

No QA Desc.
11. Q What did Turing do after the war?
11. A Turing was given an OBE in 1945 for his wartime services, and led the design of the Automatic Computing Engine (ACE) at the National Physical Laboratory. In 1949 he was given a position at the University of Manchester as the Deputy Director of the Computing Company. He turned his attention to the issue of artificial intelligence in his paper, Computing Machinery and Intelligence (1950), which he outlines a method to determine if a machine is intelligent or not. He referred to it as the “imitation game”, but it is better known as the “Turing test”.
Find out about the The Imitation Game, the movie based on aspects of Turing’s life: https://www.imdb.com/title/tt2084970/
12. Q How has Alan Turing influenced the modern world?
12. A Much of Turing’s work has had a massive influence on technology which has become a pivotal part of the modern society. During the war, he made a lot of contributions towards cryptanalysis with new methods to approach codebreaking such as ‘Turingery’. This is still relevant today because cryptography underpins internet security and data protection. Turing is also considered one of the fathers of computer science: Before the war he was working on an idea which he called a ‘universal machine’ which is similar to a computer. His Bombe machine also proved that machines could be used to make problem solving easier and quicker. His work on artificial intelligence has also influenced research into this field and his proposed assessment for computer intelligence is now referred to as “the Turing test”.
13. Q Do you believe that historians tend to belittle Turing’s impact on the course of the war in terms of his efforts?
13. A Not at all: Turing has been idolised as the main driving force behind codebreaking at Bletchley Park. He was undoubtedly a brilliant mathematician who made many contributions to the codebreaking effort during the war; however, he was just one person amongst almost ten thousand who were all playing their part. Some of these people made developments that were just as important as Turing’s and also deserve recognition. For example, Gordon Welchman made improvements to Turing’s design for the Bombe which improved its efficiency. Harold Keen, an engineer for the British Tabulating Machine Company, was responsible for taking Turing’s design and engineering and building the first Bombe. As well as Enigma, the Germans had another machine, called Lorenz, that was an arguably harder cipher to break. John Tiltman made the first breaks into that and Bill Tutte and his team figured out the structure of the machine so that it could be reproduced (the resulting machine was called ‘Tunny’). This led to the inception of Colossus, which some people think of as the world’s first programmable electronic computer, designed and built by Tommy Flowers and his team. This does not in any way diminish the work done by Turing: his work was brilliant and ground-breaking, and made a big difference at Bletchley Park. He's a figurehead for the story, and that will hopefully lead a few other important names from Bletchley Park's history into the light. What is often overlooked, however, is Turing’s work both before and after World War 2 which has arguably had just as important an effect on history.
Read entries for John Tiltman, Bill Tutte and Tommy Flowers in Bletchley Park’s Roll of Honour:
http://bit.ly/BP_JohnTiltman
http://bit.ly/BP_BillTutte
http://bit.ly/BP_TommyFlowers
14. Q What do you think is Turing’s greatest achievement?
14. A Turing made many achievements which would be classed as significant. During the war, his contribution towards the breaking of the German Naval Enigma was very important as it aided Allied ships to evade German U-boats attempting to stop supplies arriving from North America. Much of his work has also contributed to the development of the field of computer science.
15. Q Is there an area of research today that might ultimately become as significant as Turing’s work?
15. A Yes, the work of Turing and other Bletchley Park codebreakers pushed various fields forward, such as the development of computers, which has allowed others to develop upon their work and advance the field even further. Developments in cryptography and cryptanalysis have continued to develop and modern ciphers such as RSA, which is supposedly unbreakable, are used in modern computers to protect individuals’ data. The next great development in cryptography may well be enabled by the development of quantum computers, which could see ever more complicated ciphers being created in order to overcome the development of computers able to break previous ciphers.
Find out more about RSA: http://bit.ly/Wiki_RSA


Homosexuality and Death

No QA Desc.
16. Q When did Turing’s homosexuality become a public fact (was he openly gay)?
16. A It seems that Turing was not bashful about his homosexuality, nor that he seemed to struggle with being gay, but neither did he make a point of telling people, as homosexuality was a criminal offence. In 1941, he proposed to his colleague and fellow mathematician and cryptanalyst Joan Clarke, but broke off the engagement shortly afterwards, telling her that he was homosexual. She was apparently unfazed by the revelation. It appears that Turing was generally understood to be homosexual, but it was not publicly spoken about.
In January 1952, Turing started a relationship with Arnold Murray and on 23rd January Turing's house was burgled. Murray told Turing that he knew the burglar. Turing reported this to the police, and in the course of the investigation admitted that he and Murray were in a relationship. Both men were charged with ‘gross indecency’. Turing pled ‘guilty’ in the trial on 31st March 1952 and was given a choice of imprisonment or probation (the latter included a course of hormonal treatment). Today, Turing is often used as a figurehead for the rights of gay people. He’s a relatively well-known person and is used to highlight the mistreatment of homosexual men in the past.
17. Q How and why did Alan commit suicide?
17. A Alan was found on the 8th June 1954 by his housekeeper, having died from cyanide poisoning. It is widely believed that he committed suicide by eating a contaminated apple, possibly because of his conviction and hormonal ‘treatment’. It has been suggested that the apple was a reference to the poisoned apple from Snow White, which was a favourite story of his.
His death has become a topic of contention as it has also been suggested that it may have been accidental, with some of his chemistry experiments in his home producing the cyanide that poisoned him.


Note:

At the time of Turing’s death suicide was a crime, so the phrase committed suicide was commonly used. Suicide was not decriminalised in England until 1961 when gradually society had recognised that such actions may occur as a result of illness and not a crime. Contemporary society has a more compassionate understanding towards mental illness and individual circumstances, preferring to use the word ‘suicide’ or the phrase ‘taken their own life’. It is recognised that mental pain can be very distressing, and in society we need to care for both our mental and physical health.



Turing FAQ日本語訳

戦前

番号 QA 説明
1. Q アランはいつ頃から自分が数学やコーディングが好きだと気付き始めたのですか?
1. A 彼は、幼い頃から物事の仕組みに興味を持っていたようです。彼はよく「ポリマス」と表現されますが、これは様々な分野に興味や専門性を持っている人のことです。チューリングは、自分が興味を持っている多種多様なことを調べるのに、数学が素晴らしい枠組みであることを発見したのかもしれない。彼は子供の頃から暗号に興味を持ち、関連するパズルや問題を解いたり作ったりして楽しんでいました。
2. Q 第二次世界大戦前、アランはどのようなプロジェクトに取り組んでいたのでしょうか?
2. A 戦前、チューリングが取り組んでいたのは、『計算可能な数について』という論文の内容である「Entscheidungsproblem」(ドイツ語で「決定問題」)だったといいます。この問題は、数学の記述に注目して、ある記述が証明可能かどうかを判断する技術を見つけることができるかどうかを問うもので、チューリングはそのような技術は存在しないことを証明しました。これを受けて、チューリングは、現在チューリング・マシンと呼ばれている研究を始めました。チューリング・マシンとは、一定のルールに基づいて変数から結果を得ることができる仮想的な計算機です。これは、現在のコンピュータプログラムの考え方に似ています。1936年当時、このような機械は存在しておらず、彼のアイデアを試すのに十分な技術が開発されるまでには、さらに9年を要することになりました。
3. Q アランが取り組んでいたプロジェクトや機械をあきらめたことはありますか?
3. A 1939年、彼はリーマン仮説(ミレニアム問題のひとつ)に関連する問題を解決するための機械に取り組んでいました。「ゼータ関数マシン」と呼ばれるこの機械は、部分的に構築されたものの、戦争の勃発により放棄されました。


レッチリーパークにて
番号 QA 説明
4. Q アラン・チューリングはブレッチレイ・パークのどの建物で働いていましたか?
4. A 彼はブレッチレイ・パークの Hut 8 を率いていたことで有名ですが、戦争中ずっとそこで働いていたわけではありません。彼は1940年の春、ディリー・ノックスのエニグマ研究セクションの一員として、Cottage 2 を拠点に Bombe を設計しました。Hut 8 は1940年初頭に完成し、チューリングは1941年にその運営を担当しました。1942年、彼はアメリカを訪れ、 Bombe の設計に協力し、Uボートエニグマ問題についてもアメリカと情報を交換しました。1943年には、ブレッチリー・パークからほど近いハンスロープ・パークで作業を開始し、Delilah と呼ばれる音声解読プログラムを開発しました。
Hut 8についての詳細:http://bit.ly/Wiki_Hut8

5. Q チューリング以前にエニグマを解読するために行われていたことは?
5. A ポーランドの3人の数学者が1930年代半ばに画期的な成果を上げ、暗号を解読するための機械(Bombaと呼ばれる)を開発しました。エニグマを解読するための初期の研究では、メッセージ・キーの繰り返し(特にローターの開始位置)と、メッセージに使われているいくつかのキーフレーズ(「クリブ」と呼ばれる)に焦点が当てられていました。重要な情報はポーランドの暗号解読者に伝えられ、マリアン・レジェフスキはエニグマのローターの内部配線を推測することができ、ポーランドエニグマのレプリカ機を作ることができました。第二次世界大戦が始まる直前に、彼らはその成果をブレッチレイ・パークに伝えましたが、その時までにドイツはエニグマの使用方法を改良していました。ポーランドの暗号解読者たちは、パリに逃れた後、1940年1月17日に、チューリングが立ち会って、戦時中の最初の暗号解読を行ったと考えられます。ブレッチリーパークで最初にエニグマの暗号化されたメッセージを解読したチームは、Hut 6 にいたゴードン・ウェルチマンのチームで、ジョン・ジェフリーズがこの作業に使用されたパンチシートの使用を監督していました。
レッチリーパークのポーランド人記念碑:http://bit.ly/Maps_PolishMemorial
ポーランド人によるエニグマの解読:http://bit.ly/Wiki_PolishContribution
Bombaの詳細: http://bit.ly/Wiki_Bomba
エニグマの解読についての詳細:http://bit.ly/Wiki_BreakingEnigma
6. Q アラン・チューリングエニグマの解読にどのように貢献しましたか?
6. A 重要なのは、エニグマを最初に解読したのはチューリングではないということです(Q.5参照)。チューリングは、バンブリズム(Banburismus)などの更に効率的な暗号解読技術を開発することで、さまざまなバージョンのエニグマを解読するプロセスを改善しました。また、ローレンツ暗号の一部を解読する方法(Turingery)を開発するなど、他の暗号の解読にも貢献しました。
彼の最も有名な業績は、これらの暗号解読技術の一部を人間よりも早く実行できる機械「Bombe」を設計したことです。ドイツ海軍の「M3」エニグマ・マシンは、より安全なメッセージ・キー手順を採用しており、この時点では解読できませんでした。そこでチューリングはこのバージョンの暗号から取り組み始めました。戦後、ドイツ海軍が最新版のエニグマ(M4)を使い始め、ブレッチリーパークが海軍のメッセージを読めなくなったとき、彼はこの新しい機械で使える技術の開発を担当したのです。
バンブリズム(Banburismus)の詳細: http://bit.ly/Wiki_Banburismus
7. Q アラン・チューリングは誰と協力してエニグマを解読したのですか?
7. A チューリングは、エニグマを解読するための大規模な組織の一員として働いていたため、一緒に働いていた人は多岐にわたります。開戦当初、チューリングはフランスのポーランド人と直接仕事をしており、それが彼の継続的な暗号解読の仕事につながりました。彼が設計した Bombe マシンは、間違いなくポーランドの暗号解読者が作った Bomba と呼ばれる初期のバージョンに触発されたものでした(Q.5参照)。彼はゴードン・ウェルチマンと一緒に仕事をしていましたが、ウェルチマンは Bombe マシンの改良型を考案しました(彼の改良型は「ダイアゴナル・ボード」(diagonal board)と呼ばれ、誤った結果の数を減らすことができました)。チューリングアメリカにも滞在し、アメリカの暗号解読者と一緒に、アメリカ海軍版の Bombe を含むさまざまな作業を行いました。ブレッチリーパークにいた頃、彼は Hut 8 のチームの一員として海軍のエニグマを解読していました。
ゴードン・ウェルチマンの詳細: http://bit.ly/BP_GordonWelchman
Hut 8で働いていた他の人々の詳細:http://bit.ly/BP_Hut8Personnel
アメリカの爆撃機の詳細:http://bit.ly/Wiki_USBombe
8. Q チューリング第二次世界大戦にどのような貢献をしましたか?
8. A チューリング第二次世界大戦に多くの貢献をしましたが、暗号解読の分野でチューリングが行った5つの進歩は特に注目に値します。
1. ボンベの設計(本連載の「エニグマとボンベ」を参照)
2. ドイツ海軍の指示方法の解明
3. バンブリズムと呼ばれる技術でボンベの機械使用を大幅に効率化(Q.6参照)
4. ローレンツマシンのホイールのカム設定を計算するための手順(「チューリングリー」(Turingery)と呼ばれる)を考案。
5. Delilah」と呼ばれる携帯型のボイススクランブルシステムの開発に取り組む[1]。これは完成しませんでしたが、彼の仕事が後の開発に役立ったことは間違いありません。
チューリングリー(Turingery)の詳細:http://bit.ly/Wiki_Turingery
9. Q アラン・チューリングはブレッチレイ・パークの外にいる間、何をして時間を過ごしていましたか?
9. A チューリングは多くのことに興味を持っていました。たとえば、オリンピックチームに入りそうになった長距離走です。また、チェスをしたり(ヒュー・アレクサンダーのような暗号解読者の仲間ほどではなかったですが)、自宅で化学実験をするのが好きですが、ブレッチレイ・パークで仕事をしているときにはあまりしなかったかもしれません。しかし、暗号解読者として働いていた頃のアラン・チューリングが書いたノートには、彼が自由時間の多くを数学の研究に費やしていたことが記されています。
チューリングが所属していたアスレチックスクラブの幹事へのインタビューの一部:http://bit.ly/TuringasaRunner
10. Q チューリングの貢献と Bombe は戦争に勝つためにどれほど重要でしたか?
10. A 多くの歴史家は、連合国の勝利は必然であり、あとはどれだけ時間がかかるかの問題であったと考えています。チューリングは、ブレッチリーパークで行われていた研究に大きく貢献し、彼が開発した Bombe マシンは、敵のある種の暗号の解読を間違いなく速めました(Q.6参照)。特にドイツ海軍のエニグマを解読したことで、連合国が大西洋の戦いで成功し、1944年の「D-Day」に間に合うように北米から英国に重要な物資を届けることができたのです。第二次世界大戦中、ブレッチレイ・パークで働いていた多くの人々も同じように、優秀な頭脳と勤勉さが一体となって、乗り越えられないと思われた問題を解決したのだということを忘れてはなりません。
大西洋の戦いについてはこちらをご覧ください:http://bit.ly/BBC_BattleoftheAtlantic


戦後とレガシー

番号 QA 説明
11. Q 戦後、チューリングは何をしていたのですか?
11. A チューリングは1945年に戦時中の功績が認められてOBEを授与され、国立物理学研究所で自動計算エンジン(ACE)の設計を指揮しました。1949年には、マンチェスター大学のコンピューティング・カンパニーの副所長に就任しました。彼は人工知能の問題に目を向け、論文「Computing Machinery and Intelligence」(1950年)の中で、機械が知的であるかどうかを判断する方法を概説しました。彼はこれを「イミテーション・ゲーム」と呼びましたが、「チューリング・テスト」としてよく知られています。
チューリングの生涯を描いた映画「イミテーション・ゲーム」についてはこちらをご覧ください:https://www.imdb.com/title/tt2084970/
12. Q アラン・チューリング現代社会にどのような影響を与えましたか?
12. A チューリングの業績の多くは、現代社会で重要な役割を果たしているテクノロジーに大きな影響を与えています。戦時中、彼は「チューリングリー」(Turingery)などの暗号解読のための新しい手法を用いて暗号解読に多大な貢献をしました。これは、インターネットのセキュリティやデータ保護を支える暗号技術として、今日でも重要な意味を持っています。また、チューリングコンピュータサイエンスの父の一人とも言われています。戦前、彼はコンピューターに似た「ユニバーサル・マシン」と呼ばれるアイデアに取り組んでいました。また、彼の Bombe マシンは、マシンを使用して問題解決をより簡単かつ迅速に行えることも証明しました。人工知能に関する彼の研究は、この分野の研究にも影響を与えており、彼が提案したコンピューター知能の評価は、現在「チューリングテスト」と呼ばれています。
13. Q 歴史家は、チューリングの努力が戦争の行方に与えた影響を軽視する傾向があると思いますか
13. A 全くありません。チューリングはブレッチリーパークでの暗号解読の主な原動力として偶像化されています。彼は間違いなく優秀な数学者であり、戦時中の暗号解読作業に多くの貢献をしましたが、彼は1万人近くがそれぞれの役割を果たした中の1人に過ぎなかったのです。しかし、彼は1万人近い人々の中の1人に過ぎず、その中にはチューリングと同様に重要な開発を行った人々もいて、それらの人々も評価されるべきである。例えば、ゴードン・ウェルチマンは、チューリングが設計した Bombe に改良を加え、その効率を高めました。また、イギリスの集計機会社の技術者であるハロルド・キーンは、チューリングの設計と技術を取り入れて、最初の Bombe を作った責任者です。ドイツ軍はエニグマだけでなく、ローレンツと呼ばれる別の機械も持っていましたが、これは間違いなく解読が難しい暗号でした。ジョン・ティルトマンが最初の解読を行い、ビル・タットとそのチームが再現できるように機械の構造を解明しました(出来上がった機械は「Tunny」と呼ばれました)。これは、トミー フラワーズと彼のチームによって設計および構築された、世界初のプログラム可能な電子コンピュータだと一部の人が考えるコロッサスの始まりにつながりました。これは、チューリングが行った仕事を決して弱めるものではありません。彼の仕事は素晴らしく、画期的なものであり、ブレッチリー パークで大きな違いを生みました。彼は物語の代表者であり、うまくいけば、ブレッチリー・パークの歴史に登場する他のいくつかの重要な名前に光を当てるでしょう.しかし、見過ごされがちなことは、第二次世界大戦前後のチューリングの業績であり、歴史に同じくらい重要な影響を与えた可能性があります。
http://bit.ly/BP_JohnTiltman
http://bit.ly/BP_BillTutte
http://bit.ly/BP_TommyFlowers
14. Q チューリングの最大の功績は何だと思いますか?
14. A チューリングは、重要とされる多くの功績を残しました。戦時中、ドイツ海軍のエニグマの解読に貢献したことは、北米からの物資の到着を阻止しようとするドイツのUボートを連合軍の船が回避するのに役立ち、非常に重要でした。また、彼の業績の多くは、コンピュータサイエンスの分野の発展にも貢献しています。
15. Q 今日の研究分野で、最終的にチューリングの研究に匹敵するような意義を持つものはありますか?
15. A はい、チューリングや他のブレッチリー パークの暗号解読者の仕事は、コンピューターの開発など、さまざまな分野を前進させ、他の人が自分の仕事を発展させ、その分野をさらに発展させることができました。暗号化と暗号解読の開発は継続しており、RSA などの最新の暗号は解読できないとされていますが、個人のデータを保護するために最新のコンピューターで使用されています。暗号における次の大きな発展は、量子コンピューターの開発によって可能になる可能性があり、以前の暗号を破ることができるコンピューターの開発を克服するために、これまで以上に複雑な暗号が作成される可能性があります。
RSAについての詳細はこちら:http://bit.ly/Wiki_RSA


ホモセクシャルと死

番号 QA 説明
16. Q チューリングの同性愛が公の事実となったのはいつですか?
16. A チューリングは自分の同性愛について恥ずかしがり屋ではなかったようで、同性愛であることに苦労しているようにも見えませんでしたが、同性愛は犯罪であるため、人々に話すことを怠ったわけでもありません. 1941年、彼は同僚で数学者で暗号解読者のジョーン・クラークにプロポーズしましたが、すぐに婚約を解消し、自分は同性愛者であると彼女に告げました.彼女は明らかにその啓示に動じなかったようです。チューリングは一般的に同性愛者であると理解されていたようですが、公には語られませんでした。
1952年1月、チューリングはアーノルド・マレーとの関係を開始し、1月23日にチューリングの家が盗難に合いました.マレーはチューリングに、泥棒を知っていると話しました。チューリングはこれを警察に報告し、捜査の過程で彼とマレーが交際していたことを認めました。 2人は「重大なわいせつ行為」で起訴されました。チューリングは1952年3月31日の裁判で「有罪」を認め、懲役または保護観察の選択肢を与えられました (後者にはホルモン療法のコースが含まれていました)。今日、チューリングはゲイの人々の権利の象徴としてよく使われています。彼は比較的有名な人物であり、過去の同性愛者の虐待を強調するために利用されています。
17. Q アランはどのように、そしてなぜ自殺したのですか?
17. A 1954年6月8日、アランはシアン化物中毒で死亡し、家政婦によって発見されました。彼が汚染されたリンゴを食べて自殺したのは、おそらく彼の信念とホルモンの「治療」のためだと広く信じられています。リンゴは白雪姫の毒リンゴにちなんだものであることが示唆されており、これは彼の好きな話でした。
彼の死は、彼の自宅での化学実験のいくつかが彼を毒したシアン化物を生成したため、偶然である可能性も示唆されているため、論争の的になっています.


注意:

チューリングの死の当時、自殺は犯罪だったので、自殺という言葉がよく使われました。 1961 年まで、英国では自殺は非犯罪化されていませんでした。1961 年に、社会は、そのような行動が犯罪ではなく病気の結果として発生する可能性があることを徐々に認識していました。現代社会は、精神疾患や個々の状況に対してより思いやりのある理解を持っており、「自殺」という言葉や「自分の命を奪った」という言葉を好む傾向にあります。精神的な痛みが非常に苦痛であることは認識されており、社会では精神と身体の両方の健康に気を配る必要があります。






Word Mover's Distance(6)fastWMDの実行環境を整える

Word Mover's Distance (6) Prepare the execution environment for fastWMD


2021/06/03
藤田昭人


本稿では、 前回 紹介したwikiPageSelectorを使って、fastWMDの入力となる 3種のデータファイルを生成するスクリプト wiki-xml-to-txt.py の動作を確認したいと思います。

タイトルを「fastWMD の実行環境を整える」としましたが、 fastWMD ではWMDおよびその派生アルゴリズムの エラー率と実行時間に着目しているため、 Word Mover's Distance に本来必要な 文字列処理(トークン化やストップワードの除去など)を 評価プログラムの外に追い出しています。 なので、fastWMD のコードをベースに Word Mover's Distance のAPIを実装するとなると、 付属スクリプトの処理内容も理解しておく必要があります。


Wikipedia のダンプファイルからデータを抽出する

まずは 前回 と同様に wikiPageSelector を使って Wikipedia のダンプファイルからデータを抽出します。 前々回 紹介した トリプレット・データ を使って必要なページデータを選択できます。

ここでは wikipedia-hand-triplets-release.txt を使う 次のスクリプトを書きました。

$ cat ../run

../wikiPageSelector/wikiPageSelector \
../triplets-data/wikipedia-hand-triplets-release.txt \
~/Wikipedia/enwiki-20210420-pages-articles-multistream.xml > wikipedia-triplets-dump-20210420.xml
$ time ../run
real    111m21.582s
user    110m12.387s
sys 1m3.588s
$ 

手作業で作成されたはずの wikipedia-hand-triplets-release.txt は定義されている URL は比較的少数なのですが、 スクリプトが実行を終えるのに2時間弱かかりました。


スクリプトの実行

次に付属スクリプトwiki-xml-to-txt.py を実行しますが、 その前にちょこっと準備が必要です。

スクリプトを修正する

まず、スクリプトの入力となる3つのデータファイルの定義を修正します。 修正箇所は次のとおりです。

$ diff -u ../wiki-xml-to-txt.py.orig ../wiki-xml-to-txt.py
--- ../wiki-xml-to-txt.py.orig  2021-06-01 00:09:11.000000000 +0900
+++ ../wiki-xml-to-txt.py   2021-06-01 00:22:53.000000000 +0900
@@ -8,7 +8,7 @@
 import xmltodict

 filepaths = [
-   'hand/wikipedia-triplets-dump-20190918203353.xml'
+   'wikipedia-triplets-dump-20210420.xml'
 ]


@@ -66,7 +66,7 @@
 embeddings_batch = []
 embeddings = []
 old_tid2new_tid = dict()
-word_embeddings_path = "<PATH-TO-EMBEDDINGS>/GoogleNews-vectors-negative300.bin"
+word_embeddings_path = "GoogleNews-vectors-negative300.bin"

 # REFERENCE TO READ WORD2VEC BINARY FILE: https://gist.github.com/ottokart/4031dfb471ad5c11d97ad72cbc01b934
 FLOAT_SIZE = 4
@@ -117,7 +117,7 @@
        fp.write("%s %d\n" % (token, idx))

 # DUMP TRIPLETS IN INDEX FORMAT
-with open("hand/wikipedia-triplets-release.txt") as fp, open("wikipedia-triplets.txt", mode='w') as fp_out:
+with open("../triplets-data/wikipedia-hand-triplets-release.txt") as fp, open("wikipedia-triplets.txt", mode='w') as fp_out:
    for line in fp:
        if not line.strip() or line.startswith('#'):
            continue
$ 
実行に必要な Python パッケージをインストールする

次に wiki-xml-to-txt.py が使用している Python パッケージの nltk, numpy, xmltodict をインストールします。

$ pip install nltk
$ pip install numpy
$ pip install xmltodict
$ 

Python パッケージのインストール方法については 他の文献を参考にしてください。

スクリプトを実行する

スクリプトが正常に実行されると 次のように表示されます。

$ python ../wiki-xml-to-txt.py
FILE:  wikipedia-triplets-dump-20210420.xml
NUMBER OF URLS: 448
NUMBER OF TEXTS: 448
NUMBER OF TOKENS (RAW): 217549
NUMBER OF TOKENS (EMBEDDINGS): 128391
NUMBER OF TOKENS (EMBEDDINGS): 128391
NUMBER OF PAPERS: 448
$ ls
GoogleNews-vectors-negative300.bin
wikipedia-embeddings.txt
wikipedia-papers.txt
wikipedia-tokens.txt
wikipedia-triplets-dump-20210420.xml
wikipedia-triplets.txt
$ 

これでwikipedia-hand-triplets-release.txtに対応する データセットが生成できました*1


まとめ

以上、本稿では fastWMD を実行する環境を追ってきました。

文書間距離計算のエラー率と実行速度に注目する fastWMD 論文 の性質上、ベンチマークの核となる fast_wmd コマンドには 文書間距離計算のみが実装されているように見えますが、 Word Mover's Distance アルゴリズムは本来 比較する2つの文書(文字列)を引数に取り 文書間距離を返す関数として実装されるべきです。 fastWMD の実装において文書そのものを取り扱う処理は 付属するスクリプト wiki-xml-to-txt.py で実装しているように見えます。

Wikipedia ページを対象にした wiki-xml-to-txt.py の処理内容は概ね次のようです*2

  1. Wikipedia のダンプデータ(XML)からページデータを抽出しトークン化を行う
  2. トークン毎、ユニークなローカル ID を割り振る
  3. 既存の Word2Vec 学習済みデータからアクティブなトークンのベクトルのみ抽出して wikipedia-embeddings.txt に出力する
  4. アクティブなトークンの ID とトークンの対応表を wikipedia-tokens.txt に出力する
  5. トリプレット・データを読み込み URL → ID 変換を行なって wikipedia-triplets.txt に出力する
  6. Wikipedia ページデータをトークン → ID 変換を行なって、ID列を wikipedia-papers.txt に出力する


都合6回を費やし、ようやく fastWMD 論文 に伴う実装をひと通り把握することができました。 次回からは fastWMD の実装を流用して、 対話システムへの WMD の適用に挑戦したいと思います。

以上

*1:前々回 も紹介したように Dropbox からダウンロードできるのは トリプレット・データ wikipedia_2014_09_27_examples.txt から生成したデータセットのみです。

*2:次のページでは 一般的な自然言語処理における前処理について解説してます。

qiita.com

ご参考まで。

Word Mover's Distance(5)Wikipedia の Page データを抽出する

Word Mover's Distance (5) Extracting Page Data from Wikipedia XML Dump


2021/05/22
藤田昭人


前回 はトリプレットを紹介しました。 でも、実際に fastWMD を実行する際には トリプレット・データを取り込んでいるように見えないことに お気づきの方も多いかと思います。

本稿ではそのあたりのカラクリを説明した上で、 その前処理のために必要な Wikipedia のバックアップから Page データを抽出するツール wikiPageSelector を紹介したいと思います。


付属スクリプトで生成される4つのファイル

前回紹介した triplets コマンドの実行スクリプトを再掲します。

#!/bin/sh -x
../build/triplets \
--trip ../dataset/triplets/wikipedia/wikipedia-triplets.txt \
--docs ../dataset/triplets/wikipedia/wikipedia-papers.txt \
--emb ../dataset/triplets/wikipedia/wikipedia-embeddings.txt \
--verbose false --num_clusters 289 --max_iter -1 --func cosine --r 16

オプション trip, docs, emb として triplets, papers, embeddings の 3つのデータファイルがコマンドに引き渡されてますが、 いずれも数字が羅列されているテキストファイルです。 この3つのデータファイルと tokens ファイルは fastWMD のリポジトリに付属するスクリプト wiki-xml-to-txt.py で生成することができます。

このスクリプトを読んでみたところ、 次の4つの処理を実行していることがわかりました。

  1. 解析対象となるWikipediaページ(あるいは論文)をトークンに分解
  2. 句読点と意味のないトークン、いわゆるストップ・ワードを除外
  3. トークン毎にユニークな ID を設定
  4. トリプレットデータ、解析対象データ、埋め込みデータについて、トークンを ID に差し替えたファイルを生成

Wikipediaデータセットについて各ファイル毎に説明すると…

wikipedia-triplets.txt は 前回紹介したトリプレット・ファイルを ID に置き換えたファイルです。 トリプレット・ファイルは1行に3つの Wikipedia ページの URL を定義していますが、 各々のタイトルをトークンとする3つの ID に置き換えられています。

wikipedia-papers.txt は対象となる文章を ID 列に置き換えたもので、 各 Wikipedia ページの記述が使われています。 ストップ・ワードが除外されているので トークン列に逆変換しても意味不明でしょうが。

wikipedia-embeddings.txt は埋め込みデータ、 すなわち Word2Vec の学習済みデータです。 元データはトークン毎にベクトルが定義されていますが、 トークン部分が ID に置き換えられています。

wikipedia-tokens.txt は ID とトークンの対応表で、 fastWMD の実行には使われません。 このファイルを使うと ID からトークンへの逆変換が可能です。

この一連の手順は自然言語処理では 典型的な前処理だと思います。 本来 WMD では二つの文章を入力とするAPIが 用意されることが多いと思うのですが、 敢えてトークンにIDを割り当てて ベンチマーク・プログラムの外へ追い出してるのは、 文章間距離の計算速度に注目する fastWMD では 文字列操作によりコストのかかる前処理を 評価から除外するためなんじゃないかと想像してます。


スクリプトに埋め込まれている暗黙のデータ

コードに埋め込まれているので わかりにくいのですが、スクリプト wiki-xml-to-txt.py を実行するにはトリプレット・データ以外に 更に2つデータを用意する必要があります。

ひとつ目はWord2Vecの学習済みデータです。 スクリプトには次のような記述があります。

word_embeddings_path = "<PATH-TO-EMBEDDINGS>/GoogleNews-vectors-negative300.bin"

このファイル名を見れば ピンと来る方もいらっしゃるでしょ😁 これはオリジナルのWord2Vecのページで 紹介されている学習済みデータです。 以前 Word2Vecの記事 で紹介した次の Google のサイトから入手できます。

code.google.com

このページの Pre-trained word and phrase vectors あたりを見てください。 ダウンロードの方法が記述されています。

ふたつ目は解析対象となる文章データです。 スクリプトには次の記述を見ると Wikipediaのダンプファイルを そのまま取り込めるように見えます。

filepaths = [
    'hand/wikipedia-triplets-dump-20190918203353.xml'
]

そこで、Wikipedia英語版の 最新バックアップをダウンロードして来て 試してみたのですが… サイズが大き過ぎてズッコケました*1。 改めてWikipediaのダンプファイルを見てみると…

$ ls -l enwiki*
-rw-r--r--@ 1 fujita  staff  83108609305  5  6 23:25 enwiki-20210420-pages-articles-multistream.xml
-rw-r--r--@ 1 fujita  staff  19517540474  5  6 23:25 enwiki-20210420-pages-articles-multistream.xml.bz2
$ 

圧縮状態でも18.2GB、 解凍するとなんと77.4GBにもなる 超巨大ファイルです。 もちろん気づいてなかった訳ではないのですが、 内心「Python だからシレ〜っと動くかも?」 との淡い期待を抱いたのです。 期待はあっさりと打ち砕かれました。


Wikipedia のダンプファイルから Page データを抽出する

この種の、いわゆるビッグデータ処理は ある意味今どき感のあるプログラミングなんですけども、 例えて言えば「大型トラックで市街地をドライブする」ようなもので、 プログラミングは「曲がり角のたびに立ち往生する」といった感じになります*2。 やはり過去の経験どおり ベーシックなアプローチでないと乗り越えられないようです。

という訳で wikiPageSelector なる単純なCプログラムを書きました。 ソースコードgithub に置きましたので、 次のページからダウンロードしてください。

github.com

このプログラムは Wikipedia のダンプファイルから、 必要なPageデータだけを抜き出し、 サブセットの xml 形式として標準出力に出力させるだけのプログラムです。 「必要な Page データ」は「トリプレット・データに登場するページ 」と解釈しました。 第1引数にトリプレット・データ・ファイルのパスを、 第2引数に解凍後の Wikipedia のダンプファイルのパスを 指定します。

次に 最新のWikipedia英語版のダンプファイル を対象に time コマンドを噛ませて 抽出処理に要する時間を計測した例を示します。

$ time ./wikiPageSelector \
../triplets-data/wikipedia_2014_09_27_examples.txt \
~/Wikipedia/enwiki-20210420-pages-articles-multistream.xml 
・・・
21150000(99%): Still Life with Jupiter Tonans

real    344m41.938s
user    342m45.742s
sys 1m25.288s
$ time ./wikiPageSelector \
../triplets-data/wikipedia_2014_09_27_examples.txt \
~/Wikipedia/enwiki-20210420-pages-articles-multistream.xml 
・・・
21150000(99%): Still Life with Jupiter Tonans

real    339m57.163s
user    337m54.073s
sys 1m22.468s
$ 

ご覧のとおり、1回目が5時間44分、2回目が5時間39分かかりました。

標準出力をリダイレクトしてファイルに落とすと…

$ ls -l enwiki*
-rw-r--r--  1 fujita  staff  712146936  5 19 15:42 enwiki-20210420-pages-selected-1.xml
-rw-r--r--  1 fujita  staff  712146936  5 20 06:15 enwiki-20210420-pages-selected-2.xml
$ 

いずれも680MB程度の xml ファイルになりました。


まとめ

本稿では fastWMD 論文の評価実験を再現するための道具立てを調べて、 Wikipedia の Page データを抽出するツール wikiPageSelector を紹介しました。

正直、僕も論文の評価実験を再現すること自体には あまり意味を感じている訳ではないのですが、 明文化されてない評価実験のための準備作業の手順を追っていくことで、 WMDビッグデータを必要とするアルゴリズムであり、 その処理には非常に時間を要することが再確認できました。

システム、特に対話的なシステムに WMD を取り込むためには いろいろ工夫をしなければならないことが明らかになって良かったと思っています。 先端研究の成果を実用システムに応用するには 相応の二次的な研究開発が必要なんですねぇ。

以上

*1:実はこのあたりから雲行きが怪しくなって来ました😁

*2:これがブログの執筆スケジュールを破綻させた要因だったのですが😀

Word Mover's Distance(4)トリプレット(triplets)

Word Mover's Distance(4) triplets


2021/05/10
藤田昭人


本稿から数回に分けて トリプレット(triplets) について紹介します。

トリプレット(triplets) は fastWMD 論文の評価実験に登場します。 対話システムのコーパスとして 既存の書籍の文面を活用しようとしている僕には これ、非常に興味深い評価実験で 使用しているデータセットなど さらに深掘りしようと考えています。


fastWMD論文の2つの評価実験

一般に、 機械学習の研究では「データを学習」することが前提なので、 提案されているアルゴリズムのロジックを追うだけでは 妥当性の確認は難しいような気がしています。通常 「このデータにはこのアルゴリズムが有効」 といったようにデータとアルゴリズムがセットで提案されます。 それ故、この種の研究論文ではアルゴリズムのロジックの記述だけでなく 評価実験にはデータセットの詳細が記されています。

くだんの fastWMD 論文を再掲します。

arxiv.org

この論文では高速化WMDの評価として次の2つの実験結果を示しています。

Document classification via k-NN(K近傍法による文書分類)

この K近傍法 による文書分類の評価は
WMDのオリジナルである kusner論文 の実験を踏襲しています。

DATASET WCD WMD RWMD(S) RWMD(L) REL-RWMD(L)
20NEWS 1.87 6,244 842 68.0 13.4
AMAZON 0.30 351 71.7 22.1 4.47
BBCSPORT 0.01 21 3.72 1.38 0.27
CLASSIC 0.24 213 45.6 10.8 2.26
OHSUMED 0.47 1,002 158 25.1 5.20
RECIPE 0.09 106 27.6 2.13 0.55
REUTERS 0.27 181 47.7 10.9 1.67
TWITTER 0.04 3.32 1.23 0.43 0.18

実験ではkusner論文と全く同じデータセットを使用して、 同じようにエラーレートを評価していますが、 さらに各データセット毎にアルゴリズムを変えた実行時間の計測を追加しています。

Identifying related documents(関連文書の識別)

もうひとつの評価実験では Dai論文 の評価方法を踏襲しています。Dai論文は Paragraph Vector、すなわち 文書の分散表現 を評価した研究論文で、次の WikipediaarXiv の2つの文書類似性データセットを評価実験に用いています。

http://cs.stanford.edu/~quocle/triplets-data.tar.gz

Dai論文では Paragraph Vector を生成するアルゴリズムとして Le と Mikolovの論文、 いわゆる doc2vec を想定していたようですが、 そのライバルと目される WMD を使って Dai論文と同様の評価を行なったのが fastWMD 論文ということなのでしょう。


トリプレットとは?

前述の「文書類似性データセット」のデータをダウンロードします。 このアーカイブには3種類の トリプレット と README が収録されています。

$ tar tvzf triplets-data.tar.gz
-rw-r-----  0 adai   eng       938  7 11  2015 README
-rw-r-----  0 adai   eng       535  7 11  2015 LICENSE
-rw-r-----  0 adai   eng   2024923  6 24  2015 arxiv_2014_09_27_examples.txt
-rw-r-----  0 adai   eng   2971663  6 24  2015 wikipedia_2014_09_27_examples.txt
-rw-r-----  0 adai   eng     22746  6 24  2015 wikipedia-hand-triplets-release.txt
$ 

README を覗いてみると、 次のような トリプレット(triplets) に関する簡潔な説明が確認できます。

This is a dataset for evaluating document similarity models. In each file, each line consists of a triplet of URLs, either all from Wikipedia or all from arXiv.org. The triplets in the file 'wikipedia-hand-triplets-release.txt' were hand generated whereas the other two files were generated automatically be examining Wikipedia and arXiv.org document categories. The content of URLs one and two should be more similar than the content of URLs two and three.

これはドキュメントの類似性モデルを評価するためのデータセットです。 各ファイルでは、各行は3つのURLで構成されており、すべてWikipediaからのURLか、すべてarXiv.orgからのURLです。 ファイル 'wikipedia-hand-triplets-release.txt' の トリプレット は手動で生成されましたが、 他の2つのファイルは、WikipediaarXiv.orgのドキュメントカテゴリを調べて自動的に生成されました。 URL1 と URL2 の内容は、URL2 と URL3 の内容よりも類似している必要があります。

補足すると…

例えば 'wikipedia-hand-triplets-release.txt'の(1行目はコメントなので) 2行目は(スペースで区切られて)次の3つのURLが定義されています。

各 URL は Wikipedia 英語版のページですが、 'Deep learning' と 'Machine learning' の関係の方が 'Deep learning' と 'Computer network' の関係よりも意味的に類似していますよね? このように「URLで指定される3つの文書の意味的な関係の定義」を Dai論文では トリプレット と呼んでいるようです。


fastWMD用の Wikipedia データセット

fastWMD では Dai 論文の「文書類似性データセット」から 4種類のデータファイルを生成して*1入力データとして使います。 もっとも、生成されたデータファイルは 以下の Dropbox のサイトからダウンロードが可能です。

www.dropbox.com

Wikipedia のデータセットは 'wikipedia.tar.gz' です。 その tarball の中身は次のとおり。

$ tar tvzf wikipedia.tar.gz
-rw-rw-r--  0 mwerner_local mwerner_local 337304  9 25  2019 wikipedia-triplets.txt
-rw-rw-r--  0 mwerner_local mwerner_local 6195900  9 25  2019 wikipedia-tokens.txt
-rw-rw-r--  0 mwerner_local mwerner_local 303509985  9 25  2019 wikipedia-papers.txt
-rw-rw-r--  0 mwerner_local mwerner_local 2609813322  9 25  2019 wikipedia-embeddings.txt
$ 

この4つのデータファイルがあれば、 前回 生成した triplets コマンドが実行できます。


triplets コマンドの実行

fastWMD用の Wikipedia データセットを使って 前回 ビルドした triplets コマンドを実行してみます。 fastWMD論文を参考に次のスクリプト triplets-cosine.sh を作成しました。

#!/bin/sh -x

../build/triplets \
--trip ../dataset/triplets/wikipedia/wikipedia-triplets.txt \
--docs ../dataset/triplets/wikipedia/wikipedia-papers.txt \
--emb ../dataset/triplets/wikipedia/wikipedia-embeddings.txt \
--verbose false --num_clusters 289 --max_iter -1 --func cosine --r 16

このスクリプトはビルドツリーを仮定してますが、 Github のfastWMDのビルドツリー にもスクリプトを追加しましてありますので参考してください。


まとめ

本稿では トリプレット(triplets) の解説を軸に、 Dai論文の「文書類似性データセット」、および それから生成された fastWMD 用データセットについて 紹介しました。

前述のスクリプトを実行すると、 実行時間が一番早いはずの cosine でも 実行終了まで結構待たされますが、 実は wikipedia-embeddings.txt は 以前紹介した Word2Vec の学習済みデータです。 大規模なベクトルデータなので ロードするのに時間がかかります。

以降、しばらくは Wikipedia 用データセットに注目して fastWMD の挙動を調べて行きたいと思います。

以上



*1:データファイルを生成するために、fastWMD では arXiv 向けの parser_arxiv_papers.py と、Wikipedia 向けの wiki-xml-to-txt.py の2種類のPythonスクリプトが用意されています。 詳細はのちほど。

Word Mover's Distance(3)fastWMD のビルド(後編)

Word Mover's Distance (2) Building fastWMD (Part 2)


2021/05/06
藤田昭人


前回 に引き続き fastWMD のビルドのサクッとした説明を続けます。

とりあえず Github の fastWMD のページを再掲しておきましょう。

github.com


build-project.shを実行する

前回の手順で Google OR-ToolsEigen3 はインストール済みであれば、あと1箇所修正すれば build-project.sh を実行できます。

CMakeLists.txt を修正する

修正が必要なのは CMakeLists.txt で、 コンパイル時のヘッダーファイルのパスに /usr/local/include/eigen3 を追加してやります。 次に fastWMD の CMakeLists.txt を示します。

cmake_minimum_required(VERSION 3.5)
project(fast_wmd)

set(CMAKE_CXX_STANDARD 11)

add_executable(fast_wmd src/main.cpp src/Tools.cpp src/Tools.hpp src/Clustering.cpp src/Clustering.hpp src/Distances.cpp src/Distances.hpp)

# Add ortools
find_library(ORTOOLS_LIB ortools)
target_link_libraries(fast_wmd "${ORTOOLS_LIB}")

# Enable parallelization
# set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fopenmp")

# Disable vectorize for fair comparison between distance methods
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fno-tree-vectorize -DEIGEN_DONT_VECTORIZE=1")

# Add optimization parameter
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O3")

見てのとおり非常に短いファイルです。 cmake を使ったことのない方には記法の違いに面食らうかもしれませんが、 よく見れば Makefile と同じ考え方で修正すれば良いようです。 ここでは fastWMD が無事コンパイルできるように 前述のヘッダーファイルのパスを追加する修正を示します。

$ diff -u CMakeLists.txt.orig CMakeLists.txt
--- CMakeLists.txt.orig 2020-07-23 09:10:25.000000000 +0900
+++ CMakeLists.txt  2021-05-04 18:02:12.000000000 +0900
@@ -16,4 +16,7 @@
 set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fno-tree-vectorize -DEIGEN_DONT_VECTORIZE=1")

 # Add optimization parameter
-set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O3")
\ No newline at end of file
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O3")
+
+# Add local include for eigen3
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -I/usr/local/include")

見てもらえばわかるように、コンパイル時のフラグを定義するマクロ CMAKE_CXX_FLAGS に '-I/usr/local/include' を追加してるだけです。

fastWMD のビルド

これで build-project.sh が正常に実行できるようになりました。 ビルドのログを次に示します。

$ sh -x build-project.sh
+ mkdir build
+ cd build
+ cmake ..
-- The C compiler identification is AppleClang 12.0.5.12050022
-- The CXX compiler identification is AppleClang 12.0.5.12050022
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: /Users/fujita/xtr/BookBot/WMD/WMD-3/fastWMD/build
+ make
[ 20%] Building CXX object CMakeFiles/fast_wmd.dir/src/main.cpp.o
[ 40%] Building CXX object CMakeFiles/fast_wmd.dir/src/Tools.cpp.o
[ 60%] Building CXX object CMakeFiles/fast_wmd.dir/src/Clustering.cpp.o
[ 80%] Building CXX object CMakeFiles/fast_wmd.dir/src/Distances.cpp.o
[100%] Linking CXX executable fast_wmd
[100%] Built target fast_wmd
+ cd ..
$ 

ビルド用の build ディレクトリを作成して、移動し、cmake を実行しています。 これで build ディレクトリ以下にコンパイル用の Makefile が生成されます。 あとは make を実行するだけ。無事 fast_wmd コマンドが生成されました。


kusner コマンドと triplets コマンドを作ってみる

前回も説明しましたが、fast_wmd コマンドは論文 "Speeding up Word Mover’s Distance and its variants via properties of distances between embeddings" の評価パートを書くために、用意されたデータに 文書間距離を計算するさまざまアルゴリズムを一括で適用して、 実行時間とエラーレートだけを表示するバッチ型のプログラムです。

アルゴリズム自体は Distance.cpp/Distance.hpp に実装されていて、 それを呼び出す独自のプログラムをいろいろ作りたいわけですが、 そのためのビルド環境は流用したいところ。 そこで試しに fast_wmd コマンドを2種類の評価実験の 各々に対応する kusner コマンドと triplets コマンドを 作成してみました。両コマンドのソースコード kusner.cpp, triplets.cpp を 含むビルドツリーは Github の次のページにアップしました。

github.com

ここでは CMakeLists.txt の修正点だけ示します。 add_executable と target_link_libraries を追加すると kusner コマンドと triplets コマンドがビルドされるようになります。

$ diff -u ../../fast-wmd/fast-wmd-master/CMakeLists.txt CMakeLists.txt
--- ../../fast-wmd/fast-wmd-master/CMakeLists.txt   2021-05-04 18:02:12.000000000 +0900
+++ CMakeLists.txt  2021-05-05 13:35:15.000000000 +0900
@@ -5,15 +5,22 @@

 add_executable(fast_wmd src/main.cpp src/Tools.cpp src/Tools.hpp src/Clustering.cpp src/Clustering.hpp src/Distances.cpp src/Distances.hpp)

+add_executable(kusner src/kusner.cpp src/Tools.cpp src/Tools.hpp src/Clustering.cpp src/Clustering.hpp src/Distances.cpp src/Distances.hpp)
+
+add_executable(triplets src/triplets.cpp src/Tools.cpp src/Tools.hpp src/Clustering.cpp src/Clustering.hpp src/Distances.cpp src/Distances.hpp)
+
 # Add ortools
 find_library(ORTOOLS_LIB ortools)
 target_link_libraries(fast_wmd "${ORTOOLS_LIB}")
+target_link_libraries(kusner "${ORTOOLS_LIB}")
+target_link_libraries(triplets "${ORTOOLS_LIB}")

 # Enable parallelization
 # set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fopenmp")

 # Disable vectorize for fair comparison between distance methods
 set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fno-tree-vectorize -DEIGEN_DONT_VECTORIZE=1")
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-writable-strings")

 # Add optimization parameter
 set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O3")


まとめ

本稿では CMakeLists.txt の修正法のトピックを 中心に fastWMD のビルド方法について紹介しました。

かつて、X Window System の imake や GNU の autoconf や automake のお世話になっていた 僕のようなオールドユーザーにとって cmake は、 マニュアル を眺めていると多機能ぶりに「ちょっと面食らう」ツールですが、 「基本は Makefile機械的に生成してくれるコマンド」 と理解すると、少し取っ付きやすく感じます。

次回は、せっかく作った triplets コマンドを使って、 もう少し WMD に踏み込んだトピックを紹介したいと考えてます。

以上

f:id:Akito_Fujita:20210503123933p:plain

Word Mover's Distance(2)fastWMD のビルド(前編)

Word Mover's Distance (2) Building fastWMD (Part 1)


2021/05/03
藤田昭人


前回、 概要を紹介したので、 続けて fastWMD のビルドについてサクッと手短に説明したいと思います。 実はいろいろ試行錯誤があったのですが、 そのあたりを端折って手順をつらつらと書き出してみたところ、 思いのほか長くなったので前後編に分けました。

実際、fastWMD の実装は論文の評価パートのためのコードのようで、 データ採りに必要最低限の内容しか含まれていない印象です。 README等で示されている手順に補足説明や追加作業を加えておきます。


まずはソースコードのダウンロード

fastWMD のソースコードGithub からダウンロードできます。

github.com

ちなみに Python のラッパーも収録されたバージョンは こちら をご覧ください。

インストール環境について

次に、インストール環境について。fastWMD の README.md によれば、次の環境で動作を確認したとのこと。

  • Ubuntu 16.04 and 18.04
  • Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz,with 8 GB of RAM

ちなみに以降の作業は次の環境で実行しました。

しかし Windows 等、他のプラットフォームでも 概ね同じ手順でインストールできると思います。 たぶん(笑)

インストールの手順を確認すると install_dependencies.shbuild-project.sh を順次実行するだけなのですが、 試してみたところ install_dependencies.sh でズッコケました。 本当に Ubuntu だけ インストールできる仕様になっているようです。


install_dependencies.sh の手順を手作業で実行する

確認したところ install_dependencies.sh では、fastWMD のビルドに必要な Google OR-ToolsEigen3 をインストールしているだけでした。 どうやらディレクトリ構成やセキュリティ・チェックなど 環境の違いがズッコケる原因のようなので、 パッケージを手作業でインストールします。

Google OR-tools

Google OR-tools はその名のとおり オペレーションズ・リサーチ関連、 以前紹介した lpSolve と同じカテゴリのパッケージのようです。 WMDに必要な最適輸送問題を解くアルゴリズムを 呼び出しているのでしょう。

このパッケージ、C++だけでなく、PythonJavaC# もサポートしているようですが、 必要なのは C++ です。実は当初はバイナリ配布のインストールを試みたのですが macOS Big Sur のセキュリティ・チェックで弾かれました。 (Google が配布しているので、今はこの問題を回避できるのかもしれませんが…) やむなくソースコードからインストールをしました。手順は以下のページです。

developers.google.com

この手順説明は macOS での C++ プログラムのビルド環境の 一般的な設定についても丁寧に説明しているので、 もし C++ プログラムを動かしたことがなければ ソースコードからのインストールの実行をお勧めします。 (どのみち fastWMD のビルドの際に設定をしなければなりません)

Eigen3

Eigenは、線形代数、行列およびベクトル演算、幾何学的変換、 数値ソルバーとそれに関連するアルゴリズムのための テンプレート・ヘッダーによる高水準 C++ ライブラリです。 おそらく fastWMD ではベクトル表現や基本演算のために使っているのでしょう。 ソースコードは次のページからダウンロードできます。

eigen.tuxfamily.org

で、ソースツリーを眺めていたら CMake 関連のファイルを見つけたので 「テンプレート・ライブラリなのに?」 と思っていたら Eigen の INSTALL メモには次のような記述がありました。

Eigen consists only of header files, hence there is nothing to compile before you can use it. Moreover, these header files do not depend on your platform, they are the same for everybody.

Eigen はヘッダファイルのみで構成されていますので、使用前にコンパイルする必要はありません。さらに、これらのヘッダファイルはプラットフォームに依存しません。プラットフォームに依存せず、誰でも同じものが使えます。

…ということなので、配布ファイルを展開して しかるべきヘッダーファイルのパスに入れることにしました。 実はちょっと試行錯誤があったのですが、 次の手順でOKなようです。

$ tar xzf eigen-3.3.9.tar.gz
$ sudo mv eigen-3.3.9 /usr/local/include/eigen3
$ 


まとめ

以上、fastWMD のビルドにまでは至ってませんが、 記事的な分量のキリが良いので、本稿はここまで。 間をあけずに後編をアップしますので、 よろしくお願いします。

以上



f:id:Akito_Fujita:20210503123933p:plain

Word Mover's Distance(1)fastWMD ー 高速化の試み

Word Mover's Distance(1) fastWMD


2021/04/29
藤田昭人


本稿では、論文 "Speeding up Word Mover’s Distance and its variants via properties of distances between embeddings" を眺めながら Word Mover's Distance (WMD) の高速化の試みをザックリと紹介したいと思います。


Word2Vec に思うこと

まずは Word2Vec について… 2013年に論文発表されたWord2Vec。 正直に告白すると当時は 「これ、いったい何に使えるんや?」 と思ったものです*1。 冒頭の論文では、Word2Vec の価値(そして意義)について次のように語られています。

数年前までは、意味的な関係(semantic relations)を取得する適切な方法がなかったので、 意味的な関係はほとんど利用されていませんでした。 それ故、研究者たちはこの問題を軽減する方法として、オントロジーを使用する決心をしましたが、 これはアプリケーションが外部の知識ベースに依存することを意味していました。 このシナリオが変わったのは,Word2Vec とその亜種が登場してからです。

この Word2Vec で分析できるとされる 「意味的な関係」が、 人工知能研究が始まって以来の命題である 「知能」に対する理解を 大きく変えつつあると僕は実感しています。

文章の類似性を測る WMD にとって その文章を構成する単語の類似性を測る Word2Vec は 必須のアルゴリズムですが、 同時に WMD は Word2Vec の有用性を 具体的に提示する重要なアプリケーション (のひとつ)でもあるように思います。


WMDの高速化の試み

実際「よく似た内容の文章を見つける」という 類似文書検索は日常的に役立つ アプリケーションでしょう。 その機能的な核となる文章間の類似度を 高い精度で計測できるWMDアルゴリズムは 需要が高い。それ故に登場した当初から 指摘されていた「分析に時間がかかる」という 課題には多くの研究者がチャレンジして来ました。 昨年(2020年)発表された冒頭の論文は、 WMD の Earth Mover's Distance (EMD) の部分、 すなわち以前紹介した最適輸送問題の解法に着目した高速化手法を扱っています。 参考文献には次の4本の先行研究も掲載されていて、 高速化はWMDが登場した2015年以来 毎年のように成果が発表される、 今もホットな研究領域のように見えます。

年号 論文
2015 From word embeddings to document distances
2017 Linear-complexity relaxed word mover’s distance with gpu acceleration
2018 Word mover’s embedding: From word2vec to document embedding
2019 Linear-complexity data-parallel earth movers distance approximations
2020 'Speeding up Word Mover’s Distance and its variants via properties of distances between embeddings'

そもそも高速化問題とは、 最適輸送問題の解法 が輸送元と輸送先の組み合わせを総あたりで計算することに起因します。 WMDに適用した場合には、その計算量は扱う語数の3乗に比例するそうで、 対象とする文書が大きい過ぎると「いつまで経っても終わらない」計算になります。

この問題は2015年のオリジナルのWMD論文でも指摘されていて、 WMDと同じ精度でもっと高速に計算する手法が提案されました。 冒頭の論文は2015年以来の先行研究を網羅した上で、 独自の手法を提案しています。


fastWMD ー C++ による WMD 実装

僕が、冒頭の論文に注目するもうひとつの理由は、 提案の評価に使われた(先行研究も含む) C++ による WMD 実装が Github で公開されていることです。

github.com

もちろん「実装コードがある」というのはありがたいことですが、 特に fastWMD では先行研究の成果であるアルゴリズムも実装されているので コードレベルで直接比較できることは大変ありがたいです。 ザッと調べてみたところ fastWMD に実装されているアルゴリズムは オリジナルの Word Mover ’s Distance (WMD) に加えて次の3つです。

  • Relaxed Word Mover ’s Distance (RWMD)
  • Linear-Complexity Relaxed Word Mover’s Distance (LC-RWMD)
  • Related Relaxed Word Mover ’s Distance (Rel-RWMD)

RWMD はオリジナルの論文で言及されていた高速化手法で、 最適輸送問題の制約条件をカットすることにより計算量を削減するアイデアです。 LC-RWMD は前処理を追加して計算量が語数に比例するように組み替えた高速化手法で、 並列化が容易になるよう配慮されている(?)反面、計算精度が低下するらしい。 Rel-RWMD は与えられた単語に対して 関連性がある単語グループと関連性がない単語グループに分ける 閾値を決めて計算の枝刈りをする高速化手法で、 Word2Vec では対象となるデータセット内での単語埋め込み間の意味的距離は 次のようなグラフを描く特性を活用しているそうです。

f:id:Akito_Fujita:20210429220216p:plain
Amazonのデータセットに含まれる全ての単語埋め込みから、単語 “cat” までの距離

Word2Vecを説明した記事 では distance コマンドを紹介しましたが、 その表示でグラフを描くとこのようなカーブを描くようですね。 Rel-RWMD の弱点は閾値は単語ごとに異なる可能性があることでしょうか?


まとめ

本稿では冒頭の論文を軸に fastWMD がサポートする WMDの高速化手法についてザックリと紹介しました。 この他にもWMDの高速化手法はたくさん提案されているようですが、 やはり実装がある fastWMD から手を付けるべきでしょう。

僕は対話システムへの応用を考えているので、 必ずしも大規模な文書が想定される訳ではないように思います。 いずれの手法が有効なのか?は対話システムの設計次第でしょう。 個々の高速化手法の詳細が気になるところですが、 以後、まずは fastWMD のビルド方法から説明することにします。

以上



*1:その僕がまさか 記事 を書くとはね。