state = frontier.dequeue() explored.add(state) if goalTest(state): return SUCCESS(state) for neighbour in state.neighbours(): if neighbour not in frontier U explored: frontier.enqueue(neighbour) return FAILURE
DFS: Depth-first Search 縦型探索法、深さ優先探索法
空間計算量：O(bm)
時間計算量：O(b^m)
完全性：○（深さが有限の場合）
最適性：✖️
アルゴリズム function DFS (initialState, goalTest) returns SUCCESS or FAILURE:
while not frontier.isEmpty() state = frontier.pop() explored.add(state) if goalTest(state): return SUCCESS(state) for neighbour in state.neighbours(): if neighbour not in frontier U explored: frontier.push(neighbour) return FAILURE
while not frontier.isEmpty() state = frontier.deleteMin() explored.add(state) if goalTest(state): return SUCCESS(state) for neighbour in state.neighbours(): if neighbour not in frontier U explored: frontier.insert(neighbour) else if neighbour in frontier: frontier.decreaseKey(neighbour) return FAILURE
while not frontier.isEmpty() state = frontier.deleteMin() explored.add(state) if goalTest(state): return SUCCESS(state) for neighbour in state.neighbours(): if neighbour not in frontier U explored: frontier.insert(neighbour) else if neighbour in frontier: frontier.decreaseKey(neighbour) return FAILURE
while not frontier.isEmpty() state = frontier.deleteMin() explored.add(state) if goalTest(state): return SUCCESS(state) for neighbour in state.neighbours(): if neighbour not in frontier U explored: frontier.insert(neighbour) else if neighbour in frontier: frontier.decreaseKey(neighbour) return FAILURE
Local Search Hill Climbing Search(Greedy Local Search): 山登り法
空間計算量：
時間計算量：
完全性：
最適性：✖️
アルゴリズム function HILL-CLIMBING(initialState) returns State that is a local maximum initialize current with initialState loop do neighbour = a highest - valued successor of current if neighbour.value <= current.value: return current.state current = neighbour
4.1 Adversarial Search and Games
Adversarial Search(∽game)が今回のテーマです。Adversarial Searchは適切な訳が見つけられませんでした。
ゲームの特徴は我々がコントロールできない相手が存在することで、最適なソリューションは一連の行動ではなく、strategy(policy)となる。
Zero-sum Gamesの特徴
* Adversarial: Pure Competition
* Agents have different values on the outcomes
* One agent maximizes one single value, while the other minimizes it
4.4 Stochastic games
サイコロをなげる、カードをシャッフルするなどランダムな要素のあるゲーム
探索木にChanceノードというノードを追加し、ランダムな要素を組み込む
例：バックギャモン（バックギャモン、日本では一般的なゲームではないので、私としてはわかりにくい例です）
Week 4 Quiz: Adversarial Search and Games
前半は好調でしたが、後半間違いを重ねてしまい、得点はギリギリPassの60%でした。
ミニマックス法とα-β枝刈り法の設問は基本的なものが多かったものの、Utility/Eval functionに関するものや、Expectiminimaxに関する質問は該当の箇所の講義をしっかりと視聴していなかったため、得点できませんでした。
Week 4 Project: Adversarial Search and Games
Week 2と同様にPythonでのコーディングの課題です。やはり分量が多いので、どこかで時間を作ってWeek 2とまとめて取り組んだ方が良さそうですね。
2.1 Intelligent Agents 最初にAgentの定義が述べられています。 An agent is anything that can be viewed as: - perceiving its environment through sensors and - acting upon that environment through actuators
エージェントのタイプ Simle reflex agents (単純反射エージェント) - select an action based on the current state only ignoring the percept history - are simple but limited - can only work if the environment is fully observable, that is the correct action is based on the current percept only Model-based reflex agents (記憶をもつ反射エージェント) - handle partial observability by keeping track of the part of the world it can't see now - have internal state depending on the percept history (best guess) - have model of the world based on (1) how the world evolves independently from the agent and (2) how the agent actions affects the world Goal-based agents (ゴール主導エージェント) - are knowing the current state of the environment is not enough. The agent needs some goal information. - combine the goal information with the environment model to choose the actions that achieve that goal. - consider the future with "What will happen if I do A ?" - are flexible as knowledge supporting the decision is explicitly represented and can be modified. Utility-based agents (効率主導エージェント) - sometimes achieving the desired goal is not enough. We may look for quicker, safer, cheaper trip to reach a destination. - agent happiness should be taken into consideration. We call it utility. - a utility function is the agent's performance measure - because of the uncertainty in the world, a utility agent choses the action that maximizes the expected utility.
State spaceとsearch spaceの違い
State space: a physical configuration
Search space: an abstract configuration represented by a search tree or graph of possible solutions
探索木
- Root: initial state
- Branches: actions
- Nodes: results from actions. A node has: parent, children, depth, path cost, associated state in the state space.
探索空間は下記の三つに分類できる
1. Explored (a.k.a. Closed List, Visited Set) 探索済み
2. Frontier (a.k.a. Open List, the Fringe) 次に探索するもの
3. Unexplored: 未探索
Search strategies
* A strategy is defined by picking the order of node expansion
* Strategies are evaluated along the following dimensions:
- Completeness: Does it always find a solution if one exists ?
- Time complexity: Number of nodes generated / expanded
- Space complexity: Maximum number of nodes in memory
- Optimality: Does it always find a least-cost solution ?
* Time and space complexity are measured in terms of:
- b: maximum branching factor of the search tree (actions per state)
- d: depth of the solution
- m: maximum depth of the state space (may be infinite ) (also noted sometimes D).
そのため、一つ一つの数式については、説明が省略されているところもあり、「なぜ、そうなるのか」と疑問が残ったままになります。数学入門書系の本を読んでいて、「であるからして、〜になる」と説明されているときの、「であるからして」が全く知識がない人にとっても理解できる程に十分にstep by stepに分解されていないと、このように「なぜ、そうなるのか」と理解できないケースが多いのですが、本書にもそのような箇所はあります。
別途、吉田洋一・赤攝也『数学序説』も読み進めているのですが、こちらでは、step by stepの説明の分解の粒度がかなり細かくなっており、時間はかかるものの「であるからして」の流れが明瞭に理解できるようになっています。
RegTech is a sub-set of FinTech that focuses on technologies that may facilitate the delivery of regulatory requirements more efficiently and effectively than existing capabilities. https://www.fca.org.uk/publication/feedback/fs-16-04.pdfより
金融危機により、金融商品の開発、トレーディング、金融機関の IT オペレーションなどに関わってきた人材が大量に流動化し、ICT 産業やベンチャー企業に流入している。ある意味では、金融業界から他業界へ移っていった人材やアイデアが、さまざまなイノベーションと結びつくことによって、外部から金融を揺り動かそうとしているのが、フィンテックによる潮流と解釈することもできよう。(2頁)
Q: How are you using my premium dollars? Glad you asked! Lemonade keeps a fixed 20% fee. This pays for developing loads of cool tech, paying our team's salaries and hopefully making some profit! The remaining 80%? Job #1 is to ensure we can always pay claims Job #2 is to Giveback money that isn’t needed for Job #1.
また、コアの業務ロジック、ビジネスロジックが必要になる場面でも、Integrate with your backendを使用されば、そのロジックが実装されているシステムからコールできるということでしょうか。（Reply.aiで出来るかどうかはわかりませんが）ボット側に不必要に業務ロジックを実装する必要がないのは、アーキテクチャー上も好ましいデザインなのかなと思います。
他にbot integrationサービスを提供する会社がないかググってみましたが、Gupshup(https://www.gupshup.io)しか見つけられませんでした。ドメインからわかるように、インドの会社です。Reply.aiの"Visual Bot builder"と同様、"Flow Bot Builder for non developers"があります。
1.1. Overview of AI
このコースで採用するAIの定義として下記を紹介しています。
"The study and design of intelligent agents, where and intelligent agent is a system that perceives its environment and takes actions that maximize it chances of success. " by Russel and Norvi AI book
1.2 Applications of AI
AIが応用されている下記の分野について、具体例とともに説明がされています。
Speech recognition, Handwriting recognition, Machine translation, Robotics, Recommendation systems, Email, Face detection, Face recognition, Detection of breast cancer in mammography image, Chess, Jeopardy, Go, Autonomous driving
囲碁のことGoっていうですね、知りませんでした。
1.3 AI foundation and history
AIの基礎となる諸学問が紹介されています。例：哲学、数学、経済学、脳神経科学、心理学、コンピュータ・エンジニアリング、サイバネティクス、言語学等。その後AIの歴史を4つの区分で説明しています。ポイントは1956年のDartmouth会議で、初めてAIという造語が使用されたということです。
1940-50: Gestation of AI
-Boolean circuit to model of brain
-Turing's Computing Machinery and intelligence
1950-1970: Early enthusiasm, great expectations
- Birth of AI @ Dartmouth meeting 1956: term Artificial intelligence was coined
- MIT Video "The thinking Machine" on Youtube
1970-1990: Knowledge-based AI
- Expert systems
- AI winter 1990-present
- AI becomes "scientific", use of probability to model uncertainty
- AI spring
1.4 Course Overview
本コースで学ぶ内容の概要が説明されています。"How human think is beyond the scope of the course"とし、AIの一分野であるものの、本コースの対象外としています。
人間がどう考えているかどうかは別として、合理的な問題解決をagent(本コースではPythonでのプログラム)にさせるか、そのためにはどのようなアルゴリズム等があるのか、といったことが本コースの学ぶ内容です。
Week 1 Quiz: Introduction to AI
ここまでの講義の内容と書きのarticleをもとにQuizに答えるようになっています。合計100点で、なんとか満点とることができました。正直、書きのarticle特にWhite Houseが出しているものは量も多く読みきれていないです。Quizに関係ありそうなところだけを読みました。時間をみつけておいおい読んでいこうかなと考えています。
1. Preparing for the Future of Artificial Intelligence. Executive Office of the President, National Science and Technology, Council Committee on Technology. October 2016.
2. Computing Machinery and Intelligence. Alan Turing, 1950.
Week 1 Discussion Questions
Question 1: "Should we be concerned about Artificial Intelligence? Is AI a threat to humankind?”
Stephen Hawking: http://www.bbc.com/news/technology-30290540
Bill Gates: https://www.washingtonpost.com/news/the-switch/wp/2015/01/28/bill-gates-on-dangers-of-artificial-intelligence-dont-understand-why-some-people-are-not-concerned/?utm_term=.666cb624c9b0
