实现 TD-Gammon 算法
Implementing the TD-Gammon algorithm
我正在尝试实现来自 Gerald Tesauro 的 TD-Gammon article 的算法。学习算法的核心在以下段落中描述:
我决定使用一个隐藏层(如果这足以玩 1990 年代早期的世界-class 双陆棋,那么对我来说就足够了)。我很确定除了 train()
函数之外的所有东西都是正确的(它们更容易测试),但我不知道我是否正确地实现了这个最终算法。
import numpy as np
class TD_network:
"""
Neural network with a single hidden layer and a Temporal Displacement training algorithm
taken from G. Tesauro's 1995 TD-Gammon article.
"""
def __init__(self, num_input, num_hidden, num_output, hnorm, dhnorm, onorm, donorm):
self.w21 = 2*np.random.rand(num_hidden, num_input) - 1
self.w32 = 2*np.random.rand(num_output, num_hidden) - 1
self.b2 = 2*np.random.rand(num_hidden) - 1
self.b3 = 2*np.random.rand(num_output) - 1
self.hnorm = hnorm
self.dhnorm = dhnorm
self.onorm = onorm
self.donorm = donorm
def value(self, input):
"""Evaluates the NN output"""
assert(input.shape == self.w21[1,:].shape)
h = self.w21.dot(input) + self.b2
hn = self.hnorm(h)
o = self.w32.dot(hn) + self.b3
return(self.onorm(o))
def gradient(self, input):
"""
Calculates the gradient of the NN at the given input. Outputs a list of dictionaries
where each dict corresponds to the gradient of an output node, and each element in
a given dict gives the gradient for a subset of the weights.
"""
assert(input.shape == self.w21[1,:].shape)
J = []
h = self.w21.dot(input) + self.b2
hn = self.hnorm(h)
o = self.w32.dot(hn) + self.b3
for i in range(len(self.b3)):
db3 = np.zeros(self.b3.shape)
db3[i] = self.donorm(o[i])
dw32 = np.zeros(self.w32.shape)
dw32[i, :] = self.donorm(o[i])*hn
db2 = np.multiply(self.dhnorm(h), self.w32[i,:])*self.donorm(o[i])
dw21 = np.transpose(np.outer(input, db2))
J.append(dict(db3 = db3, dw32 = dw32, db2 = db2, dw21 = dw21))
return(J)
def train(self, input_states, end_result, a = 0.1, l = 0.7):
"""
Trains the network using a single series of input states representing a game from beginning
to end, and a final (supervised / desired) output for the end state
"""
outputs = [self(input_state) for input_state in input_states]
outputs.append(end_result)
for t in range(len(input_states)):
delta = dict(
db3 = np.zeros(self.b3.shape),
dw32 = np.zeros(self.w32.shape),
db2 = np.zeros(self.b2.shape),
dw21 = np.zeros(self.w21.shape))
grad = self.gradient(input_states[t])
for i in range(len(self.b3)):
for key in delta.keys():
td_sum = sum([l**(t-k)*grad[i][key] for k in range(t + 1)])
delta[key] += a*(outputs[t + 1][i] - outputs[t][i])*td_sum
self.w21 += delta["dw21"]
self.w32 += delta["dw32"]
self.b2 += delta["db2"]
self.b3 += delta["db3"]
我使用它的方式是玩整个游戏(或者更确切地说,神经网络与自己对战),然后我将游戏的状态从开始到结束发送到 train()
,以及最终结果。然后获取此游戏日志,并应用上述公式使用第一个游戏状态更改权重,然后是第一个和第二个游戏状态,依此类推,直到最后一次使用整个游戏状态列表。然后我重复了很多次,希望网络学习。
需要说明的是,我并不是在寻求对我的代码编写的反馈。这绝不意味着只是一个快速而肮脏的实施,以确保我在正确的位置拥有所有的螺母和螺栓。
但是,我不知道它是否正确,因为到目前为止我还无法让它能够以任何合理的水平玩井字游戏。这可能有很多原因。也许我没有给它足够的隐藏节点(我用了 10 到 12 个)。也许它需要更多的游戏来训练(我用了 200 000)。也许使用不同的归一化函数会做得更好(我尝试过 sigmoid 和 ReLU,leaky 和 non-leaky,在不同的变体中)。也许学习参数没有调整正确。也许 tic-tac-toe 及其确定性游戏玩法意味着它 "locks in" 在游戏树的某些路径上。或者也许培训实施是错误的。这就是我来这里的原因。
我是不是误解了 Tesauro 的算法?
我不能说我完全理解你的实现,但我突然想到了这一行:
td_sum = sum([l**(t-k)*grad[i][key] for k in range(t + 1)])
与您引用的公式对比:
我看到至少两个不同点:
- 与公式中的
t
个元素相比,您的实现对 t+1
个元素求和
- 渐变应该使用与
l**(t-k)
相同的 k
进行索引,但在您的实现中它使用 i
和 key
进行索引,没有任何参考至 k
如果您修复这些差异,您的解决方案可能会更符合预期。
我正在尝试实现来自 Gerald Tesauro 的 TD-Gammon article 的算法。学习算法的核心在以下段落中描述:
我决定使用一个隐藏层(如果这足以玩 1990 年代早期的世界-class 双陆棋,那么对我来说就足够了)。我很确定除了 train()
函数之外的所有东西都是正确的(它们更容易测试),但我不知道我是否正确地实现了这个最终算法。
import numpy as np
class TD_network:
"""
Neural network with a single hidden layer and a Temporal Displacement training algorithm
taken from G. Tesauro's 1995 TD-Gammon article.
"""
def __init__(self, num_input, num_hidden, num_output, hnorm, dhnorm, onorm, donorm):
self.w21 = 2*np.random.rand(num_hidden, num_input) - 1
self.w32 = 2*np.random.rand(num_output, num_hidden) - 1
self.b2 = 2*np.random.rand(num_hidden) - 1
self.b3 = 2*np.random.rand(num_output) - 1
self.hnorm = hnorm
self.dhnorm = dhnorm
self.onorm = onorm
self.donorm = donorm
def value(self, input):
"""Evaluates the NN output"""
assert(input.shape == self.w21[1,:].shape)
h = self.w21.dot(input) + self.b2
hn = self.hnorm(h)
o = self.w32.dot(hn) + self.b3
return(self.onorm(o))
def gradient(self, input):
"""
Calculates the gradient of the NN at the given input. Outputs a list of dictionaries
where each dict corresponds to the gradient of an output node, and each element in
a given dict gives the gradient for a subset of the weights.
"""
assert(input.shape == self.w21[1,:].shape)
J = []
h = self.w21.dot(input) + self.b2
hn = self.hnorm(h)
o = self.w32.dot(hn) + self.b3
for i in range(len(self.b3)):
db3 = np.zeros(self.b3.shape)
db3[i] = self.donorm(o[i])
dw32 = np.zeros(self.w32.shape)
dw32[i, :] = self.donorm(o[i])*hn
db2 = np.multiply(self.dhnorm(h), self.w32[i,:])*self.donorm(o[i])
dw21 = np.transpose(np.outer(input, db2))
J.append(dict(db3 = db3, dw32 = dw32, db2 = db2, dw21 = dw21))
return(J)
def train(self, input_states, end_result, a = 0.1, l = 0.7):
"""
Trains the network using a single series of input states representing a game from beginning
to end, and a final (supervised / desired) output for the end state
"""
outputs = [self(input_state) for input_state in input_states]
outputs.append(end_result)
for t in range(len(input_states)):
delta = dict(
db3 = np.zeros(self.b3.shape),
dw32 = np.zeros(self.w32.shape),
db2 = np.zeros(self.b2.shape),
dw21 = np.zeros(self.w21.shape))
grad = self.gradient(input_states[t])
for i in range(len(self.b3)):
for key in delta.keys():
td_sum = sum([l**(t-k)*grad[i][key] for k in range(t + 1)])
delta[key] += a*(outputs[t + 1][i] - outputs[t][i])*td_sum
self.w21 += delta["dw21"]
self.w32 += delta["dw32"]
self.b2 += delta["db2"]
self.b3 += delta["db3"]
我使用它的方式是玩整个游戏(或者更确切地说,神经网络与自己对战),然后我将游戏的状态从开始到结束发送到 train()
,以及最终结果。然后获取此游戏日志,并应用上述公式使用第一个游戏状态更改权重,然后是第一个和第二个游戏状态,依此类推,直到最后一次使用整个游戏状态列表。然后我重复了很多次,希望网络学习。
需要说明的是,我并不是在寻求对我的代码编写的反馈。这绝不意味着只是一个快速而肮脏的实施,以确保我在正确的位置拥有所有的螺母和螺栓。
但是,我不知道它是否正确,因为到目前为止我还无法让它能够以任何合理的水平玩井字游戏。这可能有很多原因。也许我没有给它足够的隐藏节点(我用了 10 到 12 个)。也许它需要更多的游戏来训练(我用了 200 000)。也许使用不同的归一化函数会做得更好(我尝试过 sigmoid 和 ReLU,leaky 和 non-leaky,在不同的变体中)。也许学习参数没有调整正确。也许 tic-tac-toe 及其确定性游戏玩法意味着它 "locks in" 在游戏树的某些路径上。或者也许培训实施是错误的。这就是我来这里的原因。
我是不是误解了 Tesauro 的算法?
我不能说我完全理解你的实现,但我突然想到了这一行:
td_sum = sum([l**(t-k)*grad[i][key] for k in range(t + 1)])
与您引用的公式对比:
我看到至少两个不同点:
- 与公式中的
t
个元素相比,您的实现对t+1
个元素求和 - 渐变应该使用与
l**(t-k)
相同的k
进行索引,但在您的实现中它使用i
和key
进行索引,没有任何参考至k
如果您修复这些差异,您的解决方案可能会更符合预期。