X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=dagnn.git;a=blobdiff_plain;f=dagnn.lua;h=1f45b2acae3bc546495e2b33bd0666f6f577c54e;hp=0f93d95f63a87b320d9e6d261a89c9798b4d9b55;hb=e73c3494970d12154aff7587fcb43cf600f03e30;hpb=d0743d66135ed7cedcb3777cfa5dda883cbeadb3 diff --git a/dagnn.lua b/dagnn.lua index 0f93d95..1f45b2a 100755 --- a/dagnn.lua +++ b/dagnn.lua @@ -1,4 +1,23 @@ +--[[ + + Copyright (c) 2016 Idiap Research Institute, http://www.idiap.ch/ + Written by Francois Fleuret + + This file is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License version 3 as + published by the Free Software Foundation. + + It is distributed in the hope that it will be useful, but WITHOUT + ANY WARRANTY; without even the implied warranty of MERCHANTABILITY + or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public + License for more details. + + You should have received a copy of the GNU General Public License + along with this file. If not, see . + +]]-- + require 'torch' require 'nn' @@ -7,27 +26,10 @@ local DAG, parent = torch.class('nn.DAG', 'nn.Container') function DAG:__init() parent.__init(self) -- Nodes are indexed by the module they contain - self.node = { } -end - -function DAG:createNode(nnm) - if not self.node[nnm] then - self:add(nnm) -- Add it to the object as a Container - self.node[nnm] = {} - self.node[nnm].succ = {} - self.node[nnm].pred = {} - end + self.node = {} end -function DAG:addEdge(nnma, nnmb) - self.sorted = nil - self:createNode(nnma) - self:createNode(nnmb) - table.insert(self.node[nnmb].pred, nnma) - table.insert(self.node[nnma].succ, nnmb) -end - --- Apply f on t recursively; use the corresponding element from args +-- Apply f on t recursively; use the corresponding elements from args -- (i.e. same keys) as second parameter to f when available; return -- the results from f, organized in a similarly nested table. function DAG:nestedApply(f, t, args) @@ -42,36 +44,15 @@ function DAG:nestedApply(f, t, args) end end -function DAG:setInput(i) - self.sorted = nil - self.inputModules = i - self:nestedApply( - function(nnm) - if #self.node[nnm].succ == 0 then - error('Input modules must have outgoing edges.') - end - if #self.node[nnm].pred > 0 then - error('Input modules cannog have incoming edges.') - end - end, - self.inputModules - ) -end - -function DAG:setOutput(o) - self.sorted = nil - self.outputModules = o - self:nestedApply( - function(nnm) - if #self.node[nnm].pred == 0 then - error('Output module must have incoming edges.') - end - if #self.node[nnm].succ > 0 then - error('Output module cannot have outgoing edges.') - end - end, - self.outputModules - ) +function DAG:createNode(nnm) + if not self.node[nnm] then + self:add(nnm) -- Add it to the object as a Container + local node = {} + node.succ = {} + node.pred = {} + node.index = #self.modules + self.node[nnm] = node + end end function DAG:putInOrder() @@ -79,14 +60,14 @@ function DAG:putInOrder() return end - -- First, we sort the nodes according to the DAG order - local distance = {} - - self:nestedApply(function(m) distance[m] = 1 end, self.inputModules) + self:nestedApply( + function(m) distance[m] = 1 end, + self.inputModules + ) local nc - + local nl = 0 repeat nc = 0 for nnma, node in pairs(self.node) do @@ -97,9 +78,15 @@ function DAG:putInOrder() end end end + assert(nl < #self.modules, 'Cycle detected in the graph.') + nl = nl + 1 until nc == 0 - self.sorted = { } + for _, nnm in pairs(self.modules) do + assert(distance[nnm], 'Some modules are not connected to inputs') + end + + self.sorted = {} for m, d in pairs(distance) do table.insert(self.sorted, { distance = d, nnm = m }) end @@ -109,6 +96,82 @@ function DAG:putInOrder() for i, a in ipairs(self.sorted) do self.sorted[i] = a.nnm end end +-- This accumulates x in a, where they are both nested tables of +-- tensors with same structures / keys. If first is true, set a = x +-- (in which case a can be nil) otherwise a = a + x. The behavior is +-- undefined if a and x do not have the exact same structure. +function DAG:nestedAccTensor(a, x, first) + if torch.type(x) == 'table' then + local b = {} + for i in pairs(x) do + b[i] = self:nestedAccTensor(a[i], x[i], first) + end + a = b + else + if first then + if a then + a:resizeAs(x):copy(x) + else + a = x:clone() + end + else + a:add(x) + end + end + return a +end + +function DAG:updateGradOutput(node) + local gradInputSucc = node.gradInputSucc + if #gradInputSucc == 1 then + node.gradOutput = gradInputSucc[1] + elseif #gradInputSucc > 1 then + for k = 1, #gradInputSucc do + node.gradOutput = self:nestedAccTensor(node.gradOutput, gradInputSucc[k], k == 1) + end + end +end + +---------------------------------------------------------------------- + +-- Connect a sequence of modules +function DAG:connect(...) + self.sorted = nil + local prev + for _, nnm in pairs({...}) do + self:createNode(nnm) + if prev then + table.insert(self.node[nnm].pred, prev) + table.insert(self.node[prev].succ, nnm) + end + prev = nnm + end +end + +function DAG:setInput(i) + self.sorted = nil + self.inputModules = i + self:nestedApply( + function(nnm) + assert(#self.node[nnm].succ > 0, 'Input modules must have outgoing edges.') + assert(#self.node[nnm].pred == 0, 'Input modules cannot have incoming edges.') + end, + self.inputModules + ) +end + +function DAG:setOutput(o) + self.sorted = nil + self.outputModules = o + self:nestedApply( + function(nnm) + assert(#self.node[nnm].pred > 0, 'Output module must have incoming edges.') + assert(#self.node[nnm].succ == 0, 'Output module cannot have outgoing edges.') + end, + self.outputModules + ) +end + function DAG:print() self:putInOrder() @@ -117,13 +180,56 @@ function DAG:print() end end +---------------------------------------------------------------------- + +function DAG:saveDot(filename) + local file = (filename and io.open(filename, 'w')) or io.stdout + + file:write('digraph {\n') + + file:write('\n') + + for nnmb, node in pairs(self.node) do + file:write( + ' ' + .. node.index + .. ' [shape=box,label=\"' .. torch.type(nnmb) .. '\"]' + .. '\n' + ) + + for i, nnma in pairs(node.pred) do + local decoration = '' + if #node.pred > 1 then + -- decoration = ' [headlabel=\"' .. i .. '\"]' + decoration = ' [label=\"' .. i .. '\"]' + end + file:write( + ' ' + .. self.node[nnma].index + .. ' -> ' + .. self.node[nnmb].index + .. decoration + .. '\n' + ) + end + + file:write('\n') + end + + file:write('}\n') + +end + +---------------------------------------------------------------------- + function DAG:updateOutput(input) self:putInOrder() self:nestedApply( function(nnm, i) - self.node[nnm].input = i - nnm:updateOutput(i) + local node = self.node[nnm] + node.input = i + self:rethrowErrors(nnm, node.index, 'updateOutput', i) end, self.inputModules, input @@ -131,18 +237,19 @@ function DAG:updateOutput(input) for _, nnm in ipairs(self.sorted) do local node = self.node[nnm] - if #node.pred > 0 then + local pred = node.pred + if #pred > 0 then local i - if #node.pred == 1 then - i = node.pred[1].output - elseif #node.pred > 1 then + if #pred == 1 then + i = pred[1].output + elseif #pred > 1 then i = {} - for k = 1, #node.pred do - i[k] = node.pred[k].output + for k = 1, #pred do + i[k] = pred[k].output end end node.input = i - nnm:updateOutput(i) + self:rethrowErrors(nnm, node.index, 'updateOutput', i) end end @@ -154,27 +261,15 @@ function DAG:updateOutput(input) return self.output end -function DAG:computeGradInput(gradInputSucc) - local gi - if #gradInputSucc == 1 then - gi = gradInputSucc[1] -- we avoid a clone() - elseif #gradInputSucc > 1 then - for k = 1, #gradInputSucc do - if gi then - gi:add(gradInputSucc[k]) - else - gi = gradInputSucc[k]:clone() - end - end - end - return gi -end - function DAG:updateGradInput(input, gradOutput) - self:putInOrder() + assert(self.sorted, 'There has been a structure change before a DAG:updateGradInput') self:nestedApply( - function(nnm, go) nnm:updateGradInput(self.node[nnm].input, go) end, + function(nnm, go) + local node = self.node[nnm] + node.gradOutput = go + self:rethrowErrors(nnm, node.index, 'updateGradInput', node.input, go) + end, self.outputModules, gradOutput ) @@ -190,37 +285,38 @@ function DAG:updateGradInput(input, gradOutput) for k = #self.sorted, 1, -1 do local nnm = self.sorted[k] local node = self.node[nnm] - local pred, gradInputSucc = node.pred, node.gradInputSucc + local pred = node.pred - if #gradInputSucc > 0 then - nnm:updateGradInput(node.input, self:computeGradInput(gradInputSucc)) + if #node.gradInputSucc > 0 then + self:updateGradOutput(node) + self:rethrowErrors(nnm, node.index, 'updateGradInput', node.input, node.gradOutput) end -- We fill the gradInputSucc of our predecessors if #pred == 1 then table.insert(self.node[pred[1]].gradInputSucc, nnm.gradInput) elseif #pred > 1 then - if not torch.type(nnm.gradInput) == 'table' then - error('Should have a table gradInput since it has multiple predecessors') - end + assert(torch.type(nnm.gradInput) == 'table', + 'Should have a table gradInput since it has multiple predecessors') for n = 1, #pred do - table.insert(self.node[node.pred[n]].gradInputSucc, nnm.gradInput[n]) + table.insert(self.node[pred[n]].gradInputSucc, nnm.gradInput[n]) end end end - self.gradInput = self:nestedApply(function(m) return m.gradInput end, self.inputModules) + self.gradInput = self:nestedApply( + function(m) return m.gradInput end, + self.inputModules + ) return self.gradInput end function DAG:accGradParameters(input, gradOutput, scale) - scale = scale or 1 - - self:putInOrder() + assert(self.sorted, 'There has been a structure change before a DAG:accGradParameters') self:nestedApply( - function(nnm, go) nnm:updateGradInput(self.node[nnm].input, go) end, + function(nnm, go) self.node[nnm].gradOutput = go end, self.outputModules, gradOutput ) @@ -229,11 +325,19 @@ function DAG:accGradParameters(input, gradOutput, scale) self.inputModules, input ) - for k = #self.sorted, 1, -1 do - local nnm = self.sorted[k] + for k = 1, #self.modules do + local nnm = self.modules[k] local node = self.node[nnm] - nnm:accGradParameters(node.input, self:computeGradInput(node.gradInputSucc), scale) + self:rethrowErrors(nnm, k, 'accGradParameters', node.input, node.gradOutput, scale) end end -return DAG +function DAG:clearState() + self.sorted = nil + for _, node in pairs(self.node) do + node.input = nil + node.gradInputSucc = nil + node.gradOutput = nil + end + return parent.clearState(self) +end