\(A=[a_1, a_2,a_3 ...]\)というリストあって,\(s_n = \sum_{i=1}^n a_i\)として,\(S=[s_1, s_2, s_3,...]\)というリストを新たに作りたいとする.うっかりしているとリスト内包表記を使えば早かろうと思って
def ls_comp_sum(A):
length = len(A)
return [sum(A[:i]) for i in range(length)]
と書いてしまったりするが,forループを使って,
def for_sum(A):
result = [arr[0]]
length = len(arr)
for i in range(1, length):
result.append(result[-1] + arr[i])
return result
としたほうがずっと早い(Dynamic Programmingというらしい).
Eric Grimson, John Guttag, and Ana Bell. 6.0002 Introduction to Computational Thinking and Data Science. Fall 2016. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
ある現実に存在するものや,抽象的な概念の集合(nodes)があって,それらの関係性(edges)を記述する方法にGraphがある.あるnodeから出るedgeを辿って他のnodeにたどり着けるとき,渡ってきたedgeたちをからへのpathという.edgeはnode間の関係性を表すが,必ずしも両方向でない関係性(好き嫌い,因果関係,所属)のような関係を記述するgraphをdirected graph(有向グラフ)といい,必ず両方向である関係(血縁,路線図)を記述するgraphをundirected graph(無向グラフ)という.undirected graphはdirected graphの特別な場合である.また,edge間に重みがつけられているgraphもある。.
特に重要なグラフの一種にtreeがある.treeでは任意の2つのedgeが一意のpathで結ばれている.
例
The network graph formed by Wikipedia editors (edges) contributing to different Wikipedia language versions (vertices) during one month in summer 2013
早速graphを実装する.
class Node(object):
def __init__(self, name):
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name
class Edge(object):
def __init__(self, src, dest):
""" Assumes src and dest are nodes"""
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def __str__(self):
return self.src.getName() + '->' \
+ self.dest.geName()
class Digraph(object): # directed graphのクラス
"""
edge is a dict mapping each node
to a list of its children.
"""
def __init__(self):
self.edges = {}
def addNone(self, node):
if node in self.edges:
raise ValueError('Duplicate node')
else:
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
if not (src in self.edges and dest in self.edges):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.edges
def getNode(self, name):
for n in self.edges:
if n.getName() == name:
return n
raise NameError(name)
def __str__(self):
result = ''
for src in self.edges:
for dest in self.edges[src]:
result = result + src.getName() + '->'\
+ dest.getName() + '\n'
return result[:-1] # omit final newline
class Graph(Digraph):
"""
transform a directed graph to a undirected graph
"""
def addEdge(self, edge):
Digraph.addEdge(self, edge)
rev = Edge(edge.getDestination(), edge.getSource())
Digraph.addEdge(self, rev)古典的なグラフ最適化問題に,最短経路問題がある.node1, node2を結ぶ最短のpathを見つける問題である.ループ構造がある可能性があるので,無限ループを避ける工夫が必要.depth-first search(深さ優先探索)とbreadth-first search(幅優先探索)がある.
初期nodeから辿れるpathを目的nodeに到達するか,到達しないと判明するまで(ループ構造は,辿ってきたpathを保存しておいて照合することで回避する)辿る.
def DFS(graph, start, end, path, shortest, toPrint=False):
path = path + [start]
if toPrint:
print('Current DFS path:', printPath(path))
if start == end:
return path
for node in graph.childrenOf(start):
if node not in path: #avoid cycles
if shortest == None or len(path) < len(shortest):
newPath = DFS(graph, node, end, path, shortest, toPrint)
if newPath != Node:
shortest = newPath
elif toPrint:
print('Already visited', node)
return shortest
def shortestPath(graph, start, end, toPrint=False):
""" a wrapper function of DFS"""
return DFS(graph, start, end, [], None, toPrint)初期nodeから長さnのpathのnodeに目的nodeがあるかすべて探索してから,長さn+1のpathのnodeたちを調べる.depth-first searchよりもふつう低速である.
def BFS(graph, start, end, toPrint=False):
initPath = [start]
pathQueue = [initPath]
while len(PathQueue) != 0:
tmpPath = pathQueue.pop(0)
if toPrint:
print('Current BFS path:', printPath(tmpPath))
lastNode = tmpPath[-1]
if lastNode == end:
return tmpPath
for nextNode in graph.childrenOf(lastNode):
if nextNode not in tmpPath:
newPath = tmpPath + [nextNode]
PathQueue.append(newPath)
return NoneEric Grimson, John Guttag, and Ana Bell. 6.0002 Introduction to Computational Thinking and Data Science. Fall 2016. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Optimization Modelとは，対象となる関数(Objective function)をある制限によってもとで最大化したり最小化したりする引数を探し，現実の問題に応用するモデルのこと．例えばKnapsack problemがある．
Knapsack Problem :
ナップサックに入れられるものの重さの総和が決まっていて，重さの異なる複数種類のものをできるだけ価値が大きくなるようにナップサックに入れたいとき，どうやって入れるものを選ぶか． という問題．
- Continuous or fractional varinant: 入れるものが粉や液体のようないくらでも分割できるものではほとんど意味がない．
- 0/1 variant: それぞれの種類のものは1つしかない –その一つを持っていくか持っていかないか
この方法だと組み合わせ爆発が生じる： 物品が100種類ある時，その冪集合の要素数は
より現実的な解法:
while knapsack not full
put "best" avalilable item in knapsack| Food | wine | beer | pizza | burger | fries | coke | apple | donut |
|---|---|---|---|---|---|---|---|---|
| value | 89 | 90 | 30 | 50 | 90 | 79 | 90 | 10 |
| calories | 123 | 152 | 258 | 354 | 365 | 150 | 95 | 195 |
このようなメニューがあるとき，摂取カロリーを750kcal以下にしつつ，valueの和を最大化する．(ここでvalueというのは値段でなく好みの定量)
class Food(object):
def __init__(self, n, v, w,):
self.name = n
self.value = v
self.weight = w
def getValue(self):
return self.value
def getCost(self):
return self.calories
def density(self):
return self.getValue()/self.getCost()
def __str__(self):
return self.name + ': < ' + set(self.value) + ', ' +str(self.calories) +">"
def buildMenu(names, values, calories):
menu = []
for i in range(len(values)):
menu.append(Food(names[i], values[i], calories[i]))
return menu
def greedy(items, maxCost, keyFunction):
itemsCopy = sorted(items, key = keyFunction, reverse = True)
# "best"の基準をkeyFunctionで指定する．
# value, cost(calories), value/cost, cost^-1などを使う.
# ソートの問題だから，クイックソートを使えば計算量は O(nlog(n))
# (pythonはtimsort というクイックソートの一種を使っている)
resut = []
totalValue, totalCost = 0.0, 0.0
for i in range(len(itemsCopy)): # 計算量はO(n)
if (totalCost + itemsCopy[i].getCost()) <= maxCost:
result.append(itemsCopy[i])
totalCost += itemsCopy[i].getCost()
totalValue += itemsCopy[i].getValue()
return (result, totalvalue)
# 全体の計算量はO(n log n)
貪欲法は簡単に実装できるが，
ナップサック問題での貪欲法は，必ずしも最適解を与えないし，どれほど最適解に近いかわからないという欠点がある．
Treeはデータ構造の一つで，ただ一つのルートノードから発生する子ノードがあり，その子ノードから更に孫ノードが発生し・・・という具合に，ループと合流を許さない階層構造が定義されている．あるノードがからn個のノードを遡るとルートノードに至るとき，そのノードはdepth nであるという(ルートはdepth 0)またdepth n であるノードたちをlevel nに属するという.treeのノードのたちのうち，最大のdepthをtreeのlevelという．
rootから木を構成する．物品は最初にテーブルに並んでいて，その順序関係は変わらないとする．
1. 最も若い番号の物品をナップサックに入れても重量オーバーにならないとき，それをナップサックに入れるときのノードと入れないときのノードを作り，重量オーバーになるとき，ナップサックに入れないときのノードのみ作る．どちらにせよその物品はテーブルから削除する．
2. 子ノードを持っていない全てのノードに1の操作を行う
3. テーブルが空になったら，最大の価値があるような末端ノードを選ぶ．
def maxVal(toConsider, avail): # これは効率の悪いアルゴリズムである．
"""
assumes toConsider a list of items,
avail a weight
Returns a tuple of the total value of a solution to 0/1 knapsack problem
and the items of that solution
"""
# toConsiderの左端をナップサックに入れるかどうかを考えている．
if toConsider == [] or avail == 0: # ノードを追加できない
result = (0, ())
elif toConsider[0].getUnits() > avail: # ナップサックには空きがあるが，
# 今考えている物品は入らない
result = maxVal(toConsider[1:], avail)
else: # ナップサックに今考えている物品が入る
nextItem = toConsider[0]
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getUnits())
withVal += nextItem.getValue()
vithoutVal, withoutToTake = maxVal(toConsider[1:], avail)
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
return resultクロージャを使ったメモ化
でフィボナッチ数列の計算を高速化できたように，問題を解く仮定で同じサブ問題を何度も解く必要があるとき，最初に計算した答えを保存しておき，以下同じ引数が出てきたときには保存していた答えを取ってくるようにすると，高速に解けることがある．
メモ化が有効である条件は，
- Optimal substructure : 問題の最適な答えは，その問題をいくつかの小問題に分けたときの小問題の最適解たちに簡単な演算を施すことで得られて，小問題はもとの問題と同じ形をしている．
- Overlapping subproblems : 問題の最適解を得るために，同じ問題を複数書いといているとき
この基準からすると，fig.1の場合はDPはさほど有効でないが，fig.2の場合には計算量が半分以下になることが見て取れる．
def fastMaxVal(toConsider, avail, memo={}): # メモ化による高速版
"""
assumes toConsider a list of items,
avail a weight
Returns a tuple of the total value of a solution to 0/1 knapsack problem
and the items of that solution
"""
if (len(topConsider), avail) in memo.keys():
result = memo[(len(topConsider), avail)]
# toConsiderの左端をナップサックに入れるかどうかを考えている．
elif toConsider == [] or avail == 0: # ノードを追加できない
result = (0, ())
elif toConsider[0].getUnits() > avail: # ナップサックには空きがあるが，
# 今考えている物品は入らない
result = fastMaxVal(toConsider[1:], avail, memo)
else: # ナップサックに今考えている物品が入る
nextItem = toConsider[0]
withVal, withToTake = fastMaxVal(toConsider[1:],
avail - nextItem.getUnits(), memo)
withVal += nextItem.getValue()
vithoutVal, withoutToTake = maxVal(toConsider[1:], avail, memo)
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
memo[(len(toConsider), avail)] = result
return result連鎖率を使って多変数の合成関数のへ微分係数を計算する.Nielsenとはだいぶ違った書き方をしている． $$ f(y_1, ..., y_n)$$ $$y_i = y_i(x_1, ..., x_m) $$ と書けてるとき(偏微分可能性とかは一旦おいて)， $$ \frac{\partial f}{\partial x_i} = \sum_k \frac{\partial f}{\partial y_k} \frac{\partial y_k}{\partial x_i}$$ これが偏微分の連鎖率．
$$ f = f^{1}(f^{2}(...(f^{n}(x_1, ..., x_m))...)$$
このような関数たち$\{f_i\}$があって，偏微分可能とする.
$y^1_1, ..., y^1_{m1} = f^{2}(...(f^{n}(x_1, ..., x_{m}))...)$ とおくとき，
$\{\frac{\partial f}{\partial y^1_i}\}^{m1}_{i=1}$ は数値的に計算できる.
$y^2_1, ..., y^2_{m2} = f^{3}(...(f^{n}(x_1, ..., x_{m}))...)$ とおくとき，
$$ \frac{\partial f}{\partial y^{2}_i} = \sum_k \frac{\partial f}{\partial y^1_k}\frac{\partial y^1_k}{\partial y^2_i} $$
$\frac{\partial f}{\partial y^1_k}$ は既知で，$\frac{\partial y^1_k}{\partial y^2_i}$ は$f^2$ が簡単に偏微分できる関数であるなら，解析的に偏導関数をプログラマが予め与えて（次節），偏微分係数を計算する．
こうして，数値的な方法よりも高速に$\{\frac{\partial f}{\partial y^2_i}\}^{m2}_{i=1}$を計算できる．
このように関数の後ろから変微分係数を計算していくのがbackpropagation.
neural networkの世界では，$f^j : R^n \rightarrow R^m$ の出力は全て同一なことが多い．すなわち， $f^j _0 : R^n \rightarrow R $ があって， $f^j = [f^j_0, f^j_0, ..., f^j_0]$ と書ける．$f^j_0$ を単に$f^j$ と書く．neural network でよく使われる$f^j$ は次の3つ．