HTM Overview

Posted 2012.03.06 13:24
"HTM(Hierarchical Temporal Memory) is a machine learning technology that aims to capture the structural and algorithmic properties of the neocortex."  



 Despite several flaws in this algorithm[1], I dare to say that it is a revolutionary approach in machine learning in that it uses term 'prediction' which can easily be found in our daily lives. 

 *  How we 'predict' in our daily activities.
 1. When listening to a song, we are continuously predict next note(or song, if played in a fixed playlist).
 2. When walking down the stairs, we are predicting when our foot will touch the next step.
 3. Our mouth is watering at the sight of lemon. 

 * We only 'focus(learn)'[2] when we encounter unpredicted situation. HTM looks for combinations of input bits that occur together often, which we call 'spatial patterns'. It then looks for how these spatial patterns appears in sequence over time, which we call 'temporal patterns' or sequences. 

 HTM stores sequences of patterns. Successfully matching new inputs to previously stored sequences is the essence of inference and pattern matching. By matching stored sequences with current input, HTM forms a prediction about what inputs will likely arrive next. 

1) Prediction is continuous. 
 In HTM, prediction and inference are almost the same thing.

2) Prediction occurs in every region at every level of the hierarchy.
 In hierarchical structure, prediction will occur at each level. In language example, lower level regions might predict possible next phonemes, and higher level regions might predict words or phrases

3) Predictions are context sensitive. 
 For example, think about a memorized speed such as the Gettysburg Address[3]. To predict the next word, knowing just the current word is rarely sufficient; the word "and" is followed by "seven" and later by "dedicated" just in the first sentence. Just a little bit of context will help prediction. .. 

4) Prediction leads to stability.
 Since the output of a region is a list of active columns and this activation could be done by both feed-forward input and prediction, fine-tuned region's output will hardly vary. 

5) A prediction tells us if a new input is expected or unexpected. 

6) Prediction helps make the system more robust to noise. 


1. HTM structure overview




2. Column, cell, and synapses 




3. Pseudo Code

<Using source highlighting editors such as programmer's notepad recommended> 
/*
Spatial Pooler
*/

//////////////////////////////////
// Phase 1: Overlap //
//////////////////////////////////
/*
 Calculate the overlap of each column. 
*/
for( c=0; c<columnsPerRegion; c++ )
{
columns[c].overlap = 0;
for( s in columns[c].connectedSynapses() )
{// for subset of columns[c].potentialSynapses where the permanence value is greater than connectedPerm. 
columns[c].overlap = columns[c].overlap + syn[s].sourceInput.input(t);
}
// HTM only cares about the columns which exceed 'minOverlab'
if( columns[c].overlap < minOverlap )
columns[c].overlap = 0;
else
columns[c].overlap = columns[c].overlap * columns[c].boost;
}

//////////////////////////////////
// Phase 2: Inhibition //
//////////////////////////////////
/*
 Calculates which columns remain as winners after the inhibition step.
*/
for( c=0; c<columnsPerRegion; c++ )
{// for every columns in a region 
// 1. get kth score from desired local activity of c column. It is for inhibiting column activities. . 
minLocalActivitiy = kthScore(columns[c].neighbors, desiredLocalActivity);
// 2. If this column active then put it to activeColumns. 
if( columns[c].overlap > 0 && columns[c].overlap >= minLocalActivity )
activeColumns.append(t).append(columns[c]);
}

//////////////////////////////////
// Phase 3: Learning //
//////////////////////////////////
/*
 Updates the permanence values of all synapses, boost and inhibition radius. 
 1. Update potential synapse: If a certain column becomes active, reinforce its potential synapses if they contributes its activation, weaken otherwise.
 2. Update boost: If a column has not been actived as often as others, increase its boost value. 
 3. Update connected synapse: If a column's overlap value has not exceeded minOverlap quite often, increase its every connenct synapses' permanence.
 4. Update inhibition radius: Calculate size of receptive field of every columns' connected synapses. 
*/

 1. Update potential synapse
for c in activeColumns(t)
{// for every columns that are active
for s in potentialSynapses(c)
{// for every potential synapses in active columns
if( s.active() )
{// If the potential synapse is active, HTM reinforces the synapse. 
s.permanence = s.permanence + permanenceInc;
s.permanence = min(1.0, s.permanence);
}
else
{// If the potential synapse is not active, HTM weakens the synapse. 
s.permanence = s.permanence - permanenceDec;
s.permanence = min(0.0, s.permanence);
}
}
}
 2. Update boost / 3. Update connected synapses
for c in columns
{// for every columns
// set column's minDutyCycle. It's a threshold for boosting column's overlap.
// *DutyCycle: How often the column has been activated. 
c.minDutyCycle = 0.01 * c.neighbors().maxDutyCycle();
c.activeDutyCycle = c.updateActiveDutyCycle();
// *updateActiveDutyCycle(): calculate the DutyCycle of a column. 
c.boost = c.boostFunction( c.activeDutyCycle, c.minDutyCycle );
// If c.activeDutyCycle is smaller than c.minDutyCycle, set c.boost bigger than 1.0, otherwise set it to 1.0
c.overlapDutyCycle = c.updateOverlapDutyCycle();
// Calculate how often a column has exceeded 'minOverlap' *It's done in Phase 1: Overlap. 
if( c.overlapDutyCycle < c.minDutyCycle )
// If a column's overlapDutyCycle is smaller than its minDutyCycle, increase permanence value of its 'all' connected synapses. 
c.increasePermanences(0.1*connectedPerm);
}
 4. Update inhibition radius
inhibitionRadius = averageReceptiveFieldSize();
// *averageReceptiveFieldSize(): Calculate size of receptive field of every columns' connected synapses. 
// *receptive field: Average of length of every synapse?







/*
Temporal Pooler 

Cells maintatin a list of dendrite segments, where each segment contatins a list of synapses plus its permanence value. 
Changes to a cell's synapse are maintained in segmentUpdateList object.
Each segment also maintains a boolean flag, sequenceSegment, indicatin
g whether the segment predicts FF input on the next time step. 
In Temporal Pooler, we randomly add active synapses to each segment during the learning. 
We maintain three different state arrays for each cell.
1. activeState
2. predictiveState
3. learnState: It determines which cell outputs are used during learning. 
- When an input is unexpected, all the cells in a particular column become active and only one of these cells(bestMatching) has its learnState turned On.
 We only add synapses from cells that have learnState set to '1'. 
*/

//////////////////////////////////////////////////////
// Phase 1: Set cell state of active Columns //
//////////////////////////////////////////////////////

for activeColumns(t, c)
{// for every column that is active

// 1. Initialize flags
buPredicted = false; // BottomUpPredicted: flag indicating that this column's activation is from prediction from bottom-up input
lcChosen = false; // LearningCellChosen: flag indicating that a cell in this column has been chosen for learning
// 2. If the bottom-up input was predicted by any cell, then those cells become active.
for( i=0; i<cellsPerColumns-1; i++ )
{ // For every cell is this activated column
if( columns[c].cell[i].predictveState(t-1) == true )
{// if a certain cell was predicted in t-1 time step,
s = columns[c].cell[i].getActiveSegment(t-1, activeState);
// returns previously active segments(due to FF input?)index of a certain cell of an active column. 
if( seg[s].sequenceSegment == true )
{// if the segment predicts FF input, 
buPredicted = true; // current active column(cell inside) was predicted.
columns[c].cell[i].activeState(t) = 1; // current cell is active.
// If the segment became active from cells chosen with learnState on, this cell is selected as the learning cell. 
if( seg[s].segmentActive(t-1, learnState) == true )
{// if the number of connected synapses on segment s that are previously active due to the learnState is greater than activation threshold, 
lcChosen = true; // There is a cell which is in learning state.
columns[c].cell[i].learnState(t) = 1; // This cell is in learn State.
}
}
}
}
// 3. If the bottom-up input was not predicted, then all cells in this column became active.
if( buPredicted == false )
{
for( i=0; i<cellsPerColumn-1; i++ )
columns[c].cell[i].activeState(t) = 1;
}
// 4. The best matching cell is chosen as the learning cell and a new segment is added to that cell. 
if( lcChosen == false )
{// no cell has been chosen as a leaning cell. Only one cell per a column can be chosen as learning state.
s = columns[c].getBestMatchingCell(t-1); // for a given column, return the cell with the best matching segment.
// *best matching segment: segment with the largest number of active synapse. 
columns[c].cell[i].learnState(t) = 1; // current cell is in learnState
sUpdate = column[c].cell[i].getSegmentActiveSynapses(s, t-1, true);
// Return a segmentUpdate object containing a list of proposed changes to segment 's'. 
// activeSynapses: List of active synapses where the originating cells have their activeState output = '1' at time 't'. 
// *If arg[3] is true: {newSynapseCount-count(activeSynapses)} synapses are added to activeSynapses. 
// These synapses are randomly chosen from the set of cells that have learnState = 1 at time step 't'.
sUpdate.sequenceSegment = true;
segmentUpdateList.add(sUpdate);
}
}

//////////////////////////////////////////////////////////////////
// Phase 2: Prediction and Reinforcement of every cell //
//////////////////////////////////////////////////////////////////

for( c=0; c<columnsPerRegion; c++ )
{// For every column
for( i=0; i<cellsPerColumns-1; i++ )
{// For every cells in a column
for every segments( s, c, i )
{// For every segments in cell in column: for every segments
if( seg[s].segmentActive(t, activeState) )
{// If cell's segment is active, 
// * segment is active = cell is predicted. 
columns[c].cell[i].predictiveState(t) = 1; // Turn On cell's predictive state. 
// 1. Reinforcement of currently active segement
activeUpdate = columns[c].cell[i].getSegmentActiveSynapses(s, t, false);
// Return a segmentUpdate object containing a list of proposed changes to segment 's'. 
// activeSynapses: List of active synapses where the originating cells have their activeState output = '1' at time 't'. 
// *If arg[3] is true: {newSynapseCount-count(activeSynapses)} synapses are added to activeSynapses. 
// These synapses are randomly chosen from the set of cells that have learnState = 1 at time step 't'.
segmentUpdateList.add(activeUpdate);

// 2. Reinforcement of a segment that could have predicted this activation 
predSegment = columns[c].cell[i].GetBestMatchingSegment(t-1);
// Find the segment with the largest number of active synapses. If no segments are found, then an index of -1 is returned. 
predUpdate = columns[c].cell[i].getSegmentActiveSynapses(predSegment, t-1, true);
// // Return a segmentUpdate object containing a list of proposed changes to segment 'predSegment'. 
segmentUpdateList.add(preUpdate);
}
}
}
}

//////////////////////////////////////////////////////////////////
// Phase 3: Actual Learning in every cell in learnState //
//////////////////////////////////////////////////////////////////

for( c=0; c<columnsPerRegion; c++ )
{// For every column
for( i=0; i<cellsPerColumns-1; i++ )
{// For every cells in a column
if( columns[c].cell[i].learnState(t) == 1 )
{// If the segment is in learnState,
columns[c].cell[i].segmentUpdateList.adaptSegments(true); // Actual learning is done here. Only if the segment is in learnState
columns[c].cell[i].segmentUpdateList.delete();
}
else if( columns[c].cell[i].predictiveState(t) == 0 &&
columns[c].cell[i].predictiveState(t-1) == 1 )
{// If the cell stops predicting for any reason, (previously in predicted state, currently in un-predicted state)
columns[c].cell[i].segmentUpdateList.adaptSegments(false); // Negatively reinforce.
columns[c].cell[i].segmentUpdateList.delete();
}
}
}

d
d
d
d
d


Footnote

[1] Three are many component of the theory that are not yet implemented, including attention, feedback between regions, specific timing, and behavior/sensory-motor integration.
  1. Attention: It can be implemented via adjusting 'thresholds' related to 'learning' and 'activation'. 
  2. Feedback between regions: It is similar to attention. We pay attention to what we predict. 
  3. Specific timing: 
  4. sensory-motor integration: It is indispensable in developing human-like vision. When we see stuff, we automatically focus to what we want to see, and this 'focus' is key point in sensory-motor integration. Unfortunately, I'm still working on this.

 [2] Attention and learning are deeply related. 

 [3] Gettysburg Address
 "Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation, so conceived and so dedicated, can long endure. ... "
   
 Reference


저작자 표시 비영리 동일 조건 변경 허락
신고
« PREV : 1 : ··· : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : ··· : 587 : NEXT »