Math

Domain

template <typename UInt>
class Domain

A class that models the cartesian product of several ranges along several dimensions.

Public Functions

bool includes(const Domain &d) const

Not strict inclusion.

Index

template <typename UInt, const UInt NDims>
class Index

Responsibility Index is a multi-dimensional index, consisting of a series of integers.

It is a fixed size index, where the size is fixed at compile time. The size is the parameter NDims of the template. UInt is the type of integers stored in the index.

Rationale Index is useful when working multi-dimensional SparseTensors.

Notes NDims > 0 (that is, 0 is not allowed...)

Public Functions

Index()

Default constructor.

Creates an index initialized to zero.

Index(const UInt i[NDims])

Constructor from an array.

Creates an index that has the values in the given array.

Parameters
  • i: [Uint[NDims] ] the values to initialize the index with

Index(UInt i0, ...)

Constructor from a list.

Creates an index initialized with the values passed in the list.

Parameters
  • i0: [Uint...] the list of values to initialize the index with

Index(const Index &bounds, const value_type &ordinal)

Constructor from bounds and an ordinal.

This constructor builds the index that corresponds to the given ordinal, with the given bounds.

Parameters
  • bounds: [Index] the bounds to use to compute the index
  • ordinal: [UInt] the ordinal that will correspond to this index

Index(const Index &from)

Copy constructor.

Parameters
  • from: [Index] the index to copy

Index &operator=(const Index &from)

Assignment operator.

Parameters
  • from: [Index] the index to copy

UInt &operator[](const UInt idx)

Indexing operator.

Parameters
  • idx: [0 <= UInt < NDims] index
Return Value
  • [UInt&]: the value at index ‘idx’

UInt operator[](const UInt &idx) const

Const indexing operator.

Parameters
  • idx: [0 <= UInt < NDims] index
Return Value
  • [const: UInt] the value at index ‘idx’

void setToZero()

Resets the whole index to all zeros.

bool isSet() const

Returns whether the values in this index constitute a set or not (there are no duplicates).

bool increment(const Index &bounds)

Increments this index, using bounds as the upper bound for the iteration.

Parameters
  • bounds: [Index] the upper bound
Return Value
  • bool: whether we’ve reached the end of the iteration or not

bool increment(const Index &lb, const Index &ub)

Increment this index, using lb and ub as lower and upper bounds for the iteration.

Parameters
  • lb: [index] the lower bound
  • ub: [Index] the upper bound
Return Value
  • bool: whether we’ve reached the end of the iteration or not

UInt ordinal(const Index &bounds) const

Computes the ordinal corresponding to the “natural” order for this index.

For example, with bounds = [3, 2], [0, 0] -> 0, [0, 1] -> 1, [1, 0] -> 2, [1, 1] -> 3, [2, 0] -> 4, [2, 1] -> 5.

Parameters
  • bounds: [Index] the upper bound to use to compute the ordinal
Return Value
  • UInt: the ordinal for this index

UInt stride(const UInt &dim) const

Computes the stride for dimension dim of this Index.

If the Index is :[6, 7, 5, 4], then: stride(0) = 7*5*4, stride(1) = 5*4, stride(2) = 4, stride(3) = 1.

Parameters
  • dim: [UInt] the dim for which we want the stride
Return Value
  • UInt: the stride

UInt distance(const Index &bounds, const Index &other) const

Computes the distance between two indices, with respect to a given upper bound.

That is: distance = other.ordinal(bounds) - this->ordinal(bounds).

Parameters
  • bounds: [Index] the upper bound
  • other: [Index] the second index
Return Value
  • UInt: the distance between this and the second index

UInt product() const

Computes the product of all the values in this index.

The result can be zero, if at least one of the indices is zero.

Return Value
  • UInt: the product

template <UInt R>
void complement(Index<UInt, R> &idx) const

Computes the complement of this index.

For example: (*this) [0, 2, 4] -(N=6)-> (idx) [1, 3, 5] (*this) [0, 2] -(N=3)-> (idx) [1] (*this) [0] -(N=2)-> (idx) [1] (*this) [0, 1] -(N=3)-> (idx) [2]

Parameters
  • idx: [Index<UInt, R>] the complement of this index

template <UInt R>
void project(const Index<UInt, R> &dims, Index<UInt, R> &idx2) const

Computes the projection of this index on to the dimensions specified: idx2[k] = (*this)[dims[k]], for k in [0..R).

Parameters
  • dims: [Index<UInt, R>] the dimensions to project onto
  • idx2: [Index<Uint, R>] the projection of this index

template <UInt R, UInt R2>
void embed(const Index<UInt, R> &dims, Index<UInt, R2> &idx2) const

Embeds the current index into an index of higher dimension: idx2[dims[k]] = (*this)[k], for k in [0..R).

Parameters
  • dims: [Index<Uint, R>] the dimensions to embed into
  • idx: [Index<Uint, R2>] the embedding of this index

void permute(const Index &ind, Index &perm) const

Permutes this index according to the order specified in ind.

Examples: [1 2 3 4 5] becomes [2 3 4 5 1] with ind = [1 2 3 4 0] [1 2 3] becomes [3 1 2] with ind = [2 1 0]

Parameters
  • ind: [Index<UInt, NDims>] the new order
  • perm: [Index<UInt, NDims>] the resulting permutation

void findPermutation(Index &ind, const Index &perm) const

Finds the permutation that transforms this index into perm.

If this index is [1 2 3 4 5] and perm is [2 3 4 5 1], the permutation is [1 2 3 4 0] Slow: O(NDims^2)

bool hasZero() const

Returns whether any of the values in this index is a zero.

(That is, the “index” cannot be used to describe the dimensions of a tensor).

Public Members

template<>
UInt i_[NDims]

Streaming operator (for debugging).

NearestNeighbor

template <typename T>
class NearestNeighbor : public T

Public Functions

NearestNeighbor(size_type nrows, size_type ncols)

Constructor with a number of columns and a hint for the number of rows.

The SparseMatrix is empty.

Exceptions:

  • nrows < 0 (check)
  • ncols < 0 (check)
  • Not enough memory (error)
Parameters
  • nrows: [size_type >= 0] number of rows
  • ncols: [size_type >= 0] number of columns

template <typename InputIterator>
NearestNeighbor(size_type nrows, size_type ncols, InputIterator dense)

Constructor from a dense matrix passed as an array of value_type.

Uses the values in mat to initialize the SparseMatrix.

Exceptions:

  • nrows <= 0 (check)
  • ncols <= 0 (check)
  • mat == NULL (check)
  • NULL pointer in mat (check)
  • Not enough memory (error)
Parameters
  • nrows: [size_type >= 0] number of rows
  • ncols: [size_type >= 0] number of columns
  • dense: [value_type** != NULL] initial array of values

NearestNeighbor(std::istream &inStream)

Constructor from a stream in CSR format (don’t forget number of bytes after ‘csr’ tag!).

NearestNeighbor(const NearestNeighbor &other)

Copy constructor.

TODO copy part of a matrix?

Copies the given NearestNeighbor into this one.

NearestNeighbor &operator=(const NearestNeighbor &other)

Assignment operator.

template <typename InputIterator>
value_type rowL0Dist(size_type row, InputIterator x) const

Computes the distance between vector x and a given row of this NearestNeighbor, using the L0 (Hamming) distance:

dist(row, x) = sum(| row[i] - x[i] | > epsilon)

Computations are performed on the non-zeros only.

Non-mutating, O(nnzr)

Exceptions:

  • row < 0 || row >= nrows (check)
Parameters
  • row: [0 <= size_type < nrows] index of row to compute distance from
  • x: [InputIterator<value_type>] x vector
Return Value
  • [value_type]: distance from x to row of index ‘row’

template <typename InputIterator>
value_type rowL1Dist(size_type row, InputIterator x) const

Computes the distance between vector x and a given row of this NearestNeighbor, using the L1 (Manhattan) distance:

dist(row, x) = sum(| row[i] - x[i] |)

Computations are performed on the non-zeros only.

Non-mutating, O(nnzr)

Exceptions:

  • row < 0 || row >= nrows (check)
Parameters
  • row: [0 <= size_type < nrows] index of row to compute distance from
  • x: [InputIterator<value_type>] x vector
Return Value
  • [value_type]: distance from x to row of index ‘row’

template <typename InputIterator>
value_type rowL2Dist(size_type row, InputIterator x, bool take_root = false) const

Computes the distance between vector x and a given row of this NearestNeighbor, using the Euclidean distance:

dist(row, x) = [ sum((row[i] - x[i])^2) ] ^ 1/2

Computations are performed on the non-zeros only. The square root is optional, controlled by parameter take_root.

Non-mutating, O(ncols + nnzr)

Exceptions:

  • row < 0 || row >= nrows (check)
Parameters
  • row: [0 <= size_type < nrows] index of row to compute distance from
  • x: [InputIterator<value_type>] vector of the squared distances to x
  • take_root: [bool (false)] whether to return the square root of the distance or the exact value (the square root of the sum of the sqaures). Default is to return the square of the distance.
Return Value
  • [value_type]: distance from x to row of index ‘row’

template <typename InputIterator>
value_type rowLMaxDist(size_type row, InputIterator x) const

Computes the distance between vector x and a given row of this NearestNeighbor, using the Lmax distance:

dist(row, x) = max(| row[i] - x[i] |)

Computations are performed on the non-zeros only.

Non-mutating, O(nnzr)

Exceptions:

  • row < 0 || row >= nrows (check)
Parameters
  • row: [0 <= size_type < nrows] index of row to compute distance from
  • x: [InputIterator<value_type>] x vector
Return Value
  • [value_type]: distance from x to row of index ‘row’

template <typename InputIterator>
value_type rowLpDist(value_type p, size_type row, InputIterator x, bool take_root = false) const

Computes the distance between vector x and a given row of this NearestNeighbor, using the Lp distance:

dist(row, x) = [ sum(|row[i] - x[i]|^p) ] ^ 1/p

Computations are performed on the non-zeros only. The square root is optional, controlled by parameter take_root.

Non-mutating.

Exceptions:

  • row < 0 || row >= nrows (check)
Parameters
  • row: [0 <= size_type < nrows] index of row to compute distance from
  • x: [InputIterator<value_type>] vector of the squared distances to x
  • take_root: [bool (false)] whether to return the p-th power of the distance or the exact value (the p-th root of the sum of the p-powers). Default is to return the p-th power of the distance.
Return Value
  • [value_type]: distance from x to row of index ‘row’

template <typename InputIterator, typename OutputIterator>
void L0Dist(InputIterator x, OutputIterator y) const

Computes the distance between vector x and all the rows of this NearestNeighbor, using the L0 (Hamming) distance:

dist(row, x) = sum(| row[i] - x[i] | > Epsilon)

Computations are performed on the non-zeros only.

Non-mutating, O(nnzr)

Exceptions:

  • None
Parameters
  • x: [InputIterator<value_type>] x vector
  • y: [OutputIterator<value_type>] vector of distances of x to each row

template <typename InputIterator, typename OutputIterator>
void L1Dist(InputIterator x, OutputIterator y) const

Computes the distance between vector x and all the rows of this NearestNeighbor, using the L1 (Manhattan) distance:

dist(row, x) = sum(| row[i] - x[i] |)

Computations are performed on the non-zeros only.

Non-mutating, O(nnzr)

Exceptions:

  • None
Parameters
  • x: [InputIterator<value_type>] x vector
  • y: [OutputIterator<value_type>] vector of distances of x to each row

template <typename InputIterator, typename OutputIterator>
void L2Dist(InputIterator x, OutputIterator y, bool take_root = false) const

Computes the Euclidean distance between vector x and each row of this NearestNeighbor.

Non-mutating, O(nnz)

Exceptions:

  • None
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • y: [OutputIterator<value_type>] vector of the distances to x
  • take_root: [bool (false)] whether to return the square root of the distances or their exact value (the square root of the sum of the squares). Default is to return the square of the distances.

template <typename InputIterator, typename OutputIterator>
void LMaxDist(InputIterator x, OutputIterator y) const

Computes the Lmax distance between vector x and each row of this NearestNeighbor.

Non-mutating, O(nrows*ncols)

Exceptions:

  • None
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • y: [OutputIterator<value_type>] vector of the distances to x

template <typename InputIterator, typename OutputIterator>
void LpDist(value_type p, InputIterator x, OutputIterator y, bool take_root = false) const

Computes the p-th power of the Lp distance between vector x and each row of this NearestNeighbor.

Puts the result in vector y. If take_root is true, we take the p-th root of the sums, if not, y will contain the sum of the p-th powers only.

Non-mutating, O(nnz)

Exceptions:

  • None
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • y: [OutputIterator<value_type>] vector of the squared distances to x
  • take_root: [bool (false)] whether to return the p-th power of the distances or their exact value (the p-th root of the sum of the p-powers). Default is to return the p-th power of the distances.

template <typename InputIterator, typename OutputIterator>
void L0Nearest(InputIterator x, OutputIterator nn, size_type k = 1) const

Finds the row nearest to x, where nearest is defined as the row which has the smallest L0 (Hamming) distance to x.

If k > 1, finds the k nearest rows to x.

Non-mutating, O(nnz) + complexity of partial sort up to k if k > 1.

Exceptions:

  • If k < 1.
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • nn: [OutputIterator] the indices and distances of the nearest rows (pairs)
  • k: [size_type > 0, (1)] the number of nearest rows to retrieve

template <typename InputIterator, typename OutputIterator>
void L1Nearest(InputIterator x, OutputIterator nn, size_type k = 1) const

Finds the row nearest to x, where nearest is defined as the row which has the smallest L1 (Manhattan) distance to x.

If k > 1, finds the k nearest rows to x.

Non-mutating, O(nnz) + complexity of partial sort up to k if k > 1.

Exceptions:

  • If k < 1.
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • nn: [OutputIterator] the indices and distances of the nearest rows (pairs)
  • k: [size_type > 0, (1)] the number of nearest rows to retrieve

template <typename InputIterator, typename OutputIterator>
void L2Nearest(InputIterator x, OutputIterator nn, size_type k = 1, bool take_root = false) const

Finds the row nearest to x, where nearest is defined as the row which has the smallest L2 (Euclidean) distance to x.

If k > 1, finds the k nearest rows to x.

Non-mutating, O(nnz) + complexity of partial sort up to k if k > 1.

Exceptions:

  • If k < 1.
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • nn: [OutputIterator] the indices and distances of the nearest rows (pairs)
  • k: [size_type > 0, (1)] the number of nearest rows to retrieve
  • take_root: [bool (false)] whether to return the square root of the distances or their exact value (the square root of the sum of the squares). Default is to return the square of the distances.

template <typename InputIterator, typename OutputIterator>
void LMaxNearest(InputIterator x, OutputIterator nn, size_type k = 1) const

Finds the row nearest to x, where nearest is defined as the row which has the smallest Lmax distance to x.

If k > 1, finds the k nearest rows to x.

Non-mutating, O(nnz) + complexity of partial sort up to k if k > 1.

Exceptions:

  • If k < 1.
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • nn: [OutputIterator] the indices and distances of the nearest rows (pairs)
  • k: [size_type > 0, (1)] the number of nearest rows to retrieve

template <typename InputIterator, typename OutputIterator>
void LpNearest(value_type p, InputIterator x, OutputIterator nn, size_type k = 1, bool take_root = false) const

Finds the row nearest to x, where nearest is defined as the row which has the smallest Lp distance to x.

If k > 1, finds the k nearest rows to x.

Non-mutating, O(nnz) + complexity of partial sort up to k if k > 1.

Exceptions:

  • If p < 0.
  • If k < 1.
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
  • nn: [OutputIterator1] the indices and distances of the nearest rows (pairs)
  • k: [size_type > 0, (1)] the number of nearest rows to retrieve
  • take_root: [bool (false)] whether to return the p-th power of the distances or their exact value (the p-th root of the sum of the p-powers). Default is to return the p-th power of the distances.

template <typename InputIterator>
std::pair<size_type, value_type> dotNearest(InputIterator x) const

Computes the “nearest-dot” distance between vector x and each row in this NearestNeighbor.

Returns the index of the row that maximizes the dot product as well as the value of this dot-product.

Note that this equivalent to L2Nearest if all the vectors are normalized.

Non-mutating, O(nnz)

Exceptions:

  • None
Parameters
  • x: [InputIterator<value_type>] vector to compute the distance from
Return Value
  • [std::pair<size_typevalue_type>]: index of the row nearest to x, and value of the distance between x and that row

template <typename InputIterator, typename OutputIterator>
void projLpNearest(value_type p, InputIterator x, OutputIterator nn, size_type k = 1, bool take_root = false) const

Finds the k-nearest neighbors to x, ignoring the zeros of each vector stored in this matrix.

Public Members

std::vector<value_type> stddev_

EXPERIMENTAL This method computes the std dev of each component of the vectors, and scales them by that standard deviation before computing the norms.

Distance values are distorted by the standard deviation.

SegmentMatrixAdapter

template <typename Matrix>
class SegmentMatrixAdapter

A data structure that stores dendrite segments as rows in a matrix.

The matrix itself is part of this class’s public API. This class stores the segments for each cell, and it can get the cell for each segment.

This class is focused on Python consumers. C++ consumers could easily accomplish all of this directly with a matrix class, but Python consumers need a fast way of doing segment reads and writes in batches. This class makes it possible to add rows in batch, maintaining mappings between cells and segments, and providing batch lookups on those mappings.

Public Functions

size_type nCells() const

Get the number of cells.

size_type nSegments() const

Get the number of segments.

size_type createSegment(size_type cell)

Create a segment.

Parameters
  • cell: The cell that gets a new segment

template <typename InputIterator, typename OutputIterator>
void createSegments(InputIterator cells_begin, InputIterator cells_end, OutputIterator segments_begin)

Create one segment on each of the specified cells.

Parameters
  • cells: The cells that each get a new segment
  • segments: An output array with the same size as ‘cells’

void destroySegment(size_type segment)

Destroy a segment.

Remove it from its cell and remove all of its synapses in the Matrix.

This doesn’t remove the segment’s row from the Matrix, so the other segments’ row numbers are unaffected.

Parameters
  • segment: The segment to destroy

template <typename InputIterator>
void destroySegments(InputIterator segments_begin, InputIterator segments_end)

Destroy multiple segments.

Parameters
  • segments: The segments to destroy

template <typename InputIterator, typename OutputIterator>
void getSegmentCounts(InputIterator cells_begin, InputIterator cells_end, OutputIterator counts_begin) const

Get the number of segments on each of the provided cells.

Parameters
  • cells: The cells to check
  • counts: Output array with the same length as ‘cells’

const std::vector<size_type> &getSegmentsForCell(size_type cell) const

Get the segments for a cell.

Parameters
  • cell: The cell

template <typename InputIterator>
void sortSegmentsByCell(InputIterator segments_begin, InputIterator segments_end) const

Sort an array of segments by cell in increasing order.

Parameters
  • segments: The segment array. It’s sorted in-place.

template <typename InputIterator1, typename InputIterator2>
std::vector<size_type> filterSegmentsByCell(InputIterator1 segments_begin, InputIterator1 segments_end, InputIterator2 cells_begin, InputIterator2 cells_end) const

Return the subset of segments that are on the provided cells.

Parameters
  • segments: The segments to filter. Must be sorted by cell.
  • cells: The cells whose segments we want to keep. Must be sorted.

template <typename InputIterator, typename OutputIterator>
void mapSegmentsToCells(InputIterator segments_begin, InputIterator segments_end, OutputIterator cells_begin) const

Get the cell for each provided segment.

Parameters
  • segments: The segments to query
  • cells: Output array with the same length as ‘segments’

Public Members

Matrix matrix

The underlying Matrix.

Each row is a segment.

Don’t add or remove rows directly. Use createSegment / destroySegment.

Set

template <typename T = size_t, typename T_byte = unsigned char>
class Set

Public Functions

Set(T _m, T _n, T *ss)

Constructs from a list of n element indices ss, each element being in the interval [0,m[.

T intersection(T n2, T *s2, T *r) const

Computes the intersection between this and another set (n2, s2).

n2 is the number of element in the second s, s2 is a pointer to the first element, which needs to be stored contiguously. s2 needs to store the indices of the elements: (2,7,11) is the set of those 3 elements. r is the result set, and is also a list of element indices. This method also returns an integer, which is the number of elements in the intersection (so that r can be allocated once, and its first few positions reused over and over again).

NOTE: for best performance, have n2 << n

SparseMatrixAlgorithms

struct SparseMatrixAlgorithms

A collection of algorithms that operate on SparseMatrix.

They are put here instead of directly in the SparseMatrix because they are not as general as the SparseMatrix methods. They are usually tailored for a specific, sometimes experimental, algorithm. This struct is a friend of SparseMatrix, so that it can access iterators on the indices and values of the non-zeros that are not made public in SparseMatrix. In the following methods, template parameter “SM” stands for a SparseMatrix type.

Public Static Functions

template <typename SM>
static SM::value_type entropy_rate(const SM &sm)

Computes the entropy rate of a sparse matrix, along the rows or the columns.

This is defined as: sum(-nz[i,j] * log2(nz[i,j]) * sum_of_row[i], for all i,j), i.e. the usual definition of entropy, but weighted by the probability of the rows or column, i.e. the probability of the conditional distributions.

A copy of the matrix passed in is performed, and the copy is normalized to give it the meaning of a joint distribution. This is pretty slow.

TODO:

I don’t think the matrix needs to be normalized (which means rowwise normalization). You’ve already computed the “row sums”, which are the per-row normalization factor, and you can use this in the entropy calculation. i.e. if n is the norm of a single row and x[i] is the original value and xn[i] = x[i]/n is the normalized value then the partial contribution for that row is:

  • n * sum xn[i] * ln xn[i] = - n * sum x[i]/n * ln x[i]/n = - sum x[i] *( ln x[i] - ln[n]) = sum x[i] ln[n] - sum x[i] ln x[i] = n ln [n] - sum x[i] ln x[i]

In other words, you compute the entropy based on the non-normalized matrix and then add n ln[n] (There may be an error in this calculation, but in any case, I’m pretty sure you don’t actually need to normalize the matrix)

template <typename SM, typename OutputIter>
static void matrix_entropy(const SM &sm, OutputIter row_out, OutputIter row_out_end, OutputIter col_out, OutputIter col_out_end, typename SM::value_type s = 1.0)

Computes an entropy on a “smoothed” SM, for each row and for each column.

Smoothes by simply adding 1 to each count as the entropy is calculated.

template <typename SM1, typename SM2>
static void aX_plus_bX_elementMultiply_Y(const typename SM1::value_type &a, SM1 &Xoutput, const typename SM1::value_type &b, const SM2 &Y)

Multiplies the ‘X’ matrix by the constant ‘a’, then adds ‘b * X * Y’ to it, in-place.

for row in [0,nrows): for col in [0,ncols): X[row,col] = X[row,col] * (a + b * Y[row,col])

Parameters
  • a: [value_type] a coefficient
  • b: [value_type] b coefficient
  • B: [const SparseMatrix<size_type, value_type>] Y matrix

template <typename SM, typename InIter1, typename OutIter>
static void kthroot_product(const SM &sm, typename SM::size_type ss, InIter1 x, OutIter y, const typename SM::value_type &min_input)

Used to speed up sparse pooler algorithm.

TODO: describe algo.

template <typename SM, typename InputIterator1, typename InputIterator2>
static void sparseRightVecProd(const SM &sm, typename SM::size_type x_begin, typename SM::size_type x_end, InputIterator1 x, InputIterator2 y)

Computes the product of a sparse matrix and a sparse vector on the right.

[x_begin, x_end) is the range of x that contains the non-zeros for x. This function skips multiplying by zeros out of [x_begin, x_end). This is used only in nupic/math_research/shmm.cpp and direct unit testing is missing.

TODO: check if we can’t remove that and replace by incrementOuterWithNZ

template <typename SM, typename InputIterator, typename OutputIterator>
static void smoothVecMaxProd(const SM &sm, typename SM::value_type k, InputIterator x, InputIterator x_end, OutputIterator y, OutputIterator y_end)

Wrapper for iterator-based sparseRightVecProd that takes std::vectors.

TODO: can we remove? Computes a smoothed version of all rows vec max prod, that is:

for row in [0,nrows): y[row] = max((this[row,col] + k) * x[col], for col in [0,ncols))

template <typename SM, typename InputIterator, typename OutputIterator>
static void smoothVecArgMaxProd(const SM &sm, typename SM::value_type k, InputIterator x, InputIterator x_end, OutputIterator y, OutputIterator y_end)

Computes a smoothed version of all rows vec arg max prod, that is:

for row in [0,nrows): y[row] = argmax((this[row,col] + k) * x[col], for col in [0,ncols))

template <typename SM>
static void addToNZOnly(SM &A, double val, typename SM::value_type minFloor = 0)

Adds a value to the non-zeros of a SparseMatrix.

If minFloor > 0, values < minFloor are replaced by minFloor.

template <typename SM, typename U>
static void addToNZDownCols(SM &A, U begin, U end, typename SM::value_type minFloor = 0)

Adds vector to non-zeros only, down the columns.

If minFloor is > 0, any element that drop below minFloor are replaced by minFloor.

template <typename SM, typename U>
static void addToNZAcrossRows(SM &A, U begin, U end, typename SM::value_type minFloor = 0)

Adds vector to non-zeros only, across the rows.

If minFloor is > 0, any element that drop below minFloor are replaced by minFloor.

template <typename SM>
static void NZOneMinus(SM &A)

Replaces non-zeros by 1 - non-zero value.

This can introduce new zeros, but not any new zero.

TODO: clarify.

template <typename SM>
static void addNoAlloc(SM &A, const SM &B, typename SM::value_type minFloor = 0)

Adds the non-zeros of B to the non-zeros of A.

Assumes that everywhere B has a non-zeros, A has a non-zero. Non-zeros of A that don’t match up with a non-zero of B are unaffected.

[[1 0 2] + [[3 0 0] = [[4 0 2] [0 3 0]] [0 1 0]] [0 4 0]]

template <typename SM>
static void subtractNoAlloc(SM &A, const SM &B, typename SM::value_type minFloor = 0)

Subtracts the non-zeros of B from the non-zeros of A.

Assumes that everywhere B has a non-zeros, A has a non-zero. Non-zeros of A that don’t match up with a non-zero of B are unaffected.

[[1 0 2] - [[3 0 0] = [[-2 0 2] [0 3 0]] [0 1 0]] [0 2 0]]

template <typename SM>
static void assignNoAlloc(SM &A, const SM &B)

Copies the values of the non-zeros of B into A, where A and B have a non-zero in the same location.

Leaves the other non-zeros of A unchanged.

TODO: move to SM copy, with parameter to re-use memory

template <typename SM, typename SM01>
static void assignNoAllocFromBinary(SM &A, const SM01 &B)

Copies the values of the non-zeros of B into A, only where A and B have a non-zero in the same location.

The other non-zeros of A are left unchanged. SM2 is assumed to be a binary matrix.

TODO: maybe a constructor of SM, or a copy method with an argument to re-use the memory.

template <typename SM, typename SM01>
static void addConstantOnNonZeros(SM &A, const SM01 &B, typename SM::value_type cval)

Adds a constant value on nonzeros of one SparseMatrix(B) to another (A).

template <typename SM>
static void logSumNoAlloc(SM &A, const SM &B, typename SM::value_type minFloor = 0)

Computes the sum of two SMs that are in log space.

A = log(exp(A) + exp(B)), but only for the non-zeros of B. A and B are already in log space. A has non-zeros everywhere that B does. This assumes that the operation does not introduce new zeros. Note: we follow the non-zeros of B, which can be less than the non-zeros of A. If minFloor > 0, any value that drops below minFloor becomes minFloor.

template <typename SM>
static void logAddValNoAlloc(SM &A, typename SM::value_type val, typename SM::value_type minFloor = 0)

Adds a constant to the non-zeros of A in log space.

Assumes that no new zeros are introduced.

template <typename SM>
static void logDiffNoAlloc(SM &A, const SM &B, typename SM::value_type minFloor = 0)

Computes the diff of two SMs that are in log space.

A = log(exp(A) - exp(B)), but only for the non-zeros of B. A and B are already in log space. A has non-zeros everywhere that B does. A > B in all non-zeros. This assumes that the operation does not introduce new zeros. Note: we follow the non-zeros of B, which can be less than the non-zeros of A. If minFloor > 0, any value that drops below minFloor becomes minFloor.

template <typename SM>
static void LBP_piPrime(SM &mat, typename SM::value_type max_floor)

Algorithm to compute piPrime in loopy belief propagation.

The net operation performed is prod(col)/element, but it is performed in log mode and the mat argument is assumed to have already been converted to log mode. All values within mat are between 0 and 1 in normal space (-inf and -epsilon in log space).

This does a sum of each column, then places colSum-element into each location, insuring that no new zeros are introduced. Any result that would have computed to 0 (within max_floor) will be replaced with max_floor

template <typename SM, typename STR3F>
static void assignNoAlloc(SM &A, const STR3F &B, typename SM::size_type s)

Copies the values of the non-zeros of B into A, only where A and B have a non-zero in the same location.

The other non-zeros of A are left unchanged.

template <typename SM, typename STR3F>
static void logSumNoAlloc(STR3F &A, typename SM::size_type s, const SM &B, typename SM::value_type minFloor = 0)

Computes the sum in log space of A and B, where A is a slice of a STR3F and B is a SM.

The operation is: a = log(exp(a) + exp(b)), where a is a non-zero of slice s of A, and b is the corresponding non-zero of B (in the same location).

The number of non-zeros of in A is unchanged, and if the absolute value of a non-zero would fall below minFloor, it is replaced by minFloor. A and B need to have the same dimensions.

template <typename SM, typename STR3F>
static void logDiffNoAlloc(STR3F &A, typename SM::size_type s, const SM &B, typename SM::value_type minFloor = 0)

Computes the diff in log space of A and B, where A is a slice of a STR3F and B is a SM.

The operation is: a = log(exp(a) - exp(b)), where a is a non-zero of slice s of A, and b is the corresponding non-zero of B (in the same location).

The number of non-zeros of in A is unchanged, and if the absolute value of a non-zero would fall below minFloor, it is replaced by minFloor. A and B need to have the same dimensions.

template <typename STR3F>
static void assignNoAlloc(STR3F &A, typename STR3F::size_type slice_a, const STR3F &B, typename STR3F::size_type slice_b)

Updates A only where A and B have a non-zero in the same location, by copying the corresponding non-zero of B.

The other non-zeros of A are left unchanged.

template <typename STR3F>
static void logSumNoAlloc(STR3F &A, typename STR3F::size_type slice_a, const STR3F &B, typename STR3F::size_type slice_b, typename STR3F::value_type minFloor = 0)

Computes the sum in log space of A and B, where A is a slice of a STR3F and B is another slice of another STR3F.

The operation is: a = log(exp(a) + exp(b)), where a is a non-zero of slice s of A, and b is the corresponding non-zero of B (in the same location).

The number of non-zeros of in A is unchanged, and if the absolute value of a non-zero would fall below minFloor, it is replaced by minFloor. A and B need to have the same dimensions.

template <typename STR3F>
static void logDiffNoAlloc(STR3F &A, typename STR3F::size_type slice_a, const STR3F &B, typename STR3F::size_type slice_b, typename STR3F::value_type minFloor = 0)

Computes the diff in log space of A and B, where A is a slice of a STR3F and B is another slice of another STR3F.

The operation is: a = log(exp(a) - exp(b)), where a is a non-zero of slice s of A, and b is the corresponding non-zero of B (in the same location).

The number of non-zeros of in A is unchanged, and if the absolute value of a non-zero would fall below minFloor, it is replaced by minFloor. A and B need to have the same dimensions.

SparseMatrixConnections

class SparseMatrixConnections : public nupic::SegmentMatrixAdapter<SparseMatrix<UInt32, Real32, Int32, Real64>>

Wraps the SparseMatrix with an easy-to-read API that stores dendrite segments as rows in the matrix.

The internal SparseMatrix is part of the public API. It is exposed via the “matrix” member variable.

Public Functions

SparseMatrixConnections(UInt32 numCells, UInt32 numInputs)

SparseMatrixConnections constructor.

Parameters
  • numCells: The number of cells in this Connections
  • numInputs: The number of input bits, i.e. the number of columns in the internal SparseMatrix

void computeActivity(const UInt32 *activeInputs_begin, const UInt32 *activeInputs_end, Int32 *overlaps_begin) const

Compute the number of active synapses on each segment.

Parameters
  • activeInputs: The active input bits
  • overlaps: Output buffer that will be filled with a number of active synapses for each segment. This number is the “overlap” between the input SDR and the SDR formed by each segment’s synapses.

void computeActivity(const UInt32 *activeInputs_begin, const UInt32 *activeInputs_end, Real32 permanenceThreshold, Int32 *overlaps_begin) const

Compute the number of active connected synapses on each segment.

Parameters
  • activeInputs: The active input bits
  • permanenceThreshold: The minimum permanence required for a synapse to be “connected”
  • overlaps: Output buffer that will be filled with a number of active connected synapses for each segment. This number is the “overlap” between the input SDR and the SDR formed by each segment’s connected synapses.

void adjustSynapses(const UInt32 *segments_begin, const UInt32 *segments_end, const UInt32 *activeInputs_begin, const UInt32 *activeInputs_end, Real32 activePermanenceDelta, Real32 inactivePermanenceDelta)

For each specified segment, update the permanence of each synapse according to whether the synapse would be active given the specified active inputs.

Parameters
  • segments: The segments to modify
  • activeInputs: The active inputs. Used to compute the active synapses.
  • activePermanenceDelta: Additive constant for each active synapse’s permanence
  • inactivePermanenceDelta: Additive constant for each inactive synapse’s permanence

void adjustActiveSynapses(const UInt32 *segments_begin, const UInt32 *segments_end, const UInt32 *activeInputs_begin, const UInt32 *activeInputs_end, Real32 permanenceDelta)

For each specified segment, add a delta to the permanences of the synapses that would be active given the specified active inputs.

Parameters
  • segments: The segments to modify
  • activeInputs: The active inputs. Used to compute the active synapses.
  • permanenceDelta: Additive constant for each active synapse’s permanence

void adjustInactiveSynapses(const UInt32 *segments_begin, const UInt32 *segments_end, const UInt32 *activeInputs_begin, const UInt32 *activeInputs_end, Real32 permanenceDelta)

For each specified segment, add a delta to the permanences of the synapses that would be inactive given the specified active inputs.

Parameters
  • segments: The segments to modify
  • activeInputs: The active inputs. Used to compute the active synapses.
  • permanenceDelta: Additive constant for each inactive synapse’s permanence

void growSynapses(const UInt32 *segments_begin, const UInt32 *segments_end, const UInt32 *inputs_begin, const UInt32 *inputs_end, Real32 initialPermanence)

For each specified segments, grow synapses to all specified inputs that aren’t already connected to the segment.

Parameters
  • segments: The segments to modify
  • inputs: The inputs to connect to
  • initialPermanence: The permanence for each added synapse

void growSynapsesToSample(const UInt32 *segments_begin, const UInt32 *segments_end, const UInt32 *inputs_begin, const UInt32 *inputs_end, Int32 sampleSize, Real32 initialPermanence, nupic::Random &rng)

For each specified segments, grow synapses to a random subset of the inputs that aren’t already connected to the segment.

Parameters
  • segments: The segments to modify
  • inputs: The inputs to sample
  • sampleSize: The number of synapses to attempt to grow per segment
  • initialPermanence: The permanence for each added synapse
  • rng: Random number generator

void growSynapsesToSample(const UInt32 *segments_begin, const UInt32 *segments_end, const UInt32 *inputs_begin, const UInt32 *inputs_end, const Int32 *sampleSizes_begin, const Int32 *sampleSizes_end, Real32 initialPermanence, nupic::Random &rng)

For each specified segments, grow synapses to a random subset of the inputs that aren’t already connected to the segment.

Parameters
  • segments: The segments to modify
  • inputs: The inputs to sample
  • sampleSizes: The number of synapses to attempt to grow for each segment. This list must be the same length as ‘segments’.
  • initialPermanence: The permanence for each added synapse
  • rng: Random number generator

void clipPermanences(const UInt32 *segments_begin, const UInt32 *segments_end)

Clip all permanences to a minimum of 0.0 and a maximum of 1.0.

For any synapse with <= 0.0 permanence, destroy the synapse. For any synapse with > 1.0 permanence, set the permanence to 1.0.

Parameters
  • segments: The segments to modify

void mapSegmentsToSynapseCounts(const UInt32 *segments_begin, const UInt32 *segments_end, Int32 *out_begin) const

Get the number of synapses for each specified segment.

Parameters
  • segments: The segments to query
  • out: An output buffer that will be filled with the counts

SparseRLEMatrix

template <typename Index, typename Value>
class SparseRLEMatrix

A matrix where only the positions and values of runs of non-zeros are stored.

Optionally compresses values using zlib (off by default).

WATCH OUT! That the Index type doesn’t become too small to store parameters of the matrix, such as total number of non-zeros.

TODO: run length encode different values, which can be valuable when quantizing vector components. This could be another data structure.

Public Functions

void compact()

Adjusts the size of the internal vectors so that their capacity matches their size.

void compressData()

Compress data using compression algorithm.

void clear()

Deallocates memory used by this instance.

template <typename InputIterator>
void appendRow(InputIterator begin, InputIterator end)

Appends a row to this matrix.

template <typename InputIterator>
ulong_size_type firstRowCloserThan(InputIterator begin, InputIterator end, nupic::Real32 distance) const

Returns index of first row within <distance> of argument, or nRows() if none.

template <typename InputIterator>
void fromDense(ulong_size_type nrows, size_type ncols, InputIterator begin, InputIterator end)

Clears this instance and creates a new one from dense.

SparseTensor

template <typename Index, typename Float>
class SparseTensor

Description SparseTensor models a multi-dimensional array, with an arbitrary number of dimensions, and arbitrary size for each dimension, where only certain elements are not zero.

“Not zero” is defined as being outside the closed ball [-nupic::Epsilon..nupic::Epsilon]. Zero elements are not stored. Non-zero elements are stored in a data structure that provides logarithmic insertion and retrieval. A number of operations on tensors are implemented as efficiently as possible, oftentimes having complexity not worse than the number of non-zeros in the tensor. There is no limit to the number of dimensions that can be specified for a sparse tensor.

SparseTensor is parameterized on the type of Index used to index the non-zeros, and on the type of the non-zeros themselves (Float). The numerical type used as the second template parameter needs to be functionally equivalent to float, but can be int or double. It doesn’t work with complex numbers yet (have to modify nearlyZero_ to look at the modulus).

The implementation relies on a Unique, Sorted Associative NZ, that is map (rather than hash_map, we need the Indices to be sorted).

Examples: 1) SparseTensor<Index<UInt, 2>, float>: defines a sparse tensor of dimension 2 (a matrix), storing floats. The type of Index is the efficient, compile-time sized Index.

2) SparseTensor<std::vector<UInt>, float>: defines the same sparse tensor as 1), but using std::vector<UInt> for the index, which is not as fast.

3) SparseTensor<Index<UInt, 4> double>: defines a sparse tensor of rank 4 (4 dimensions), storing doubles.

Responsibility An efficient multi-dimensional sparse data structure

Rationale Numenta algorithms require very large data structure that are sparse, and those data structures cannot be handled efficiently with contiguous storage in memory.

ResourceSparseTensor owns the keys used to index the non-zeros, as well as the values of the non-zeros themselves.

Notes Note 1: in preliminary testing, using Index<UInt, Rank> was about 20 times faster than using std::vector<UInt>.

Note 2: some operations are very slow, depending on the properties of the functors used. Watch out that you are using the right one for your functor.

Note 3: SparseTensor is limited to max<unsigned long> columns, or rows or non-zeros.

Public Functions

SparseTensor(UInt ub0, ...)

SparseTensor constructor from list of bounds.

The constructed instance is identically zero. Each of the integers passed in represents the size of this sparse tensor along a given dimension. There need to be as many integers passed in as this tensor has dimensions. All the integers need to be > 0.

Note: This constructor will not work with Index = std::vector

Parameters
  • ub: [UInt >= 0] the size of this tensor along one dimension

SparseTensor(const Index &bounds)

SparseTensor constructor from Index that contains the bounds.

The constructed instance is identically zero. The size of the Index becomes the rank of this sparse tensor, that is, its number of dimensions. The values of each element of the index need to be > 0.

Parameters
  • bounds: [Index] the bounds of each dimension

SparseTensor(const SparseTensor &other)

SparseTensor copy constructor.

SparseTensor &operator=(const SparseTensor &other)

Assignment operator.

void swap(SparseTensor<Index, Float> &B)

Swaps the contents of two tensors.

The two tensors need to have the same rank, but they don’t need to have the same dimensions.

Parameters
  • B: [SparseTensor<Index, Float>] the tensor to swap with

const UInt getRank() const

Returns the rank of this tensor.

The rank is the number of dimensions of this sparse tensor, it is an integer >= 1.

Examples: A tensor of rank 0 is a scalar (not possible here). A tensor of rank 1 is a vector. A tensor of rank 2 is a matrix.

Return Value
  • UInt: [ > 0 ] the rank of this sparse tensor

const Index getBounds() const

Returns the bounds of this tensor, that is the size of this tensor along each of its dimensions.

Tensor indices start at zero along all dimensions. The product of the bounds is the total number of elements that this sparse tensor can store.

Examples: A 3 long vector has bounds Index(3). A 10x10 matrix has bounds: Index(10, 10).

Return Value
  • Index: the upper bound for this sparse tensor

const UInt getBound(const UInt &dim) const

Returns the upper bound of this sparse tensor along the given dimension.

Example: A 3x4x5 tensor has:

  • getBound(0) == 3, getBound(1) == 4, getBound(2) == 5.

Parameters
Return Value
  • [UInt: >= 0] the upper of this tensor along dim

Domain<UInt> getDomain() const

Returns the domain of this sparse tensor, where the lower bound is zero and the upper bound is the upper bound.

Example: A 3x2x4 tensor has domain { [0..3), [0..2), [0..4) }.

Return Value
  • [Domain<UInt>]: the domain for this tensor

const UInt getSizeElts() const

Returns the total size of this sparse tensor, that is, the total number of non-zeros that can be stored.

It is the product of the bounds.

Example: A 3x3 matrix has a size of 9.

Return Value
  • UInt: [ > 0 ] the size of this sparse tensor

template <typename Index2>
const UInt getSizeElts(const Index2 &dims) const

Returns the size of a sub-space of this sparse tensor, designated by dims.

Example: A 3x4 matrix has a size of 4 along the columns and 3 along the rows.

const UInt getNNonZeros() const

Returns the number of non-zeros in this sparse tensor.

Invariant: getNNonZeros() + getNZeros() == product(getBounds())

Return Value
  • UInt: [ >= 0 ] the number of non-zeros in this sparse tensor

const UInt getNZeros() const

Returns the number of zeros in this sparse tensor.

Invariant: getNZeros() + getNNonZeros() == product(getBounds())

Return Value
  • UInt: [ >= 0 ] the number of zeros in this sparse tensor

const UInt getNNonZeros(const Domain<UInt> &dom) const

Returns the number of non-zeros in a domain of this sparse tensor.

Does not work with a domain that has closed dimensions. The domain needs to have the same rank as this sparse tensor.

Parameters
  • dom: [Domain<UInt>] the domain to scan for non-zeros
Return Value
  • UInt: [ >= 0 ] the number of non-zeros in dom

const UInt getNZeros(const Domain<UInt> &dom) const

Returns the number of zeros in a domain of this sparse tensor.

Doens’t work if the domain has closed dimensions. The domain needs to have the same rank as this sparse tensor.

Parameters
  • dom: [Domain<UInt>] the domain to scan for zeros
Return Value
  • UInt: [ >= 0 ] the number of zeros in dom

template <typename Index2, typename IndexB>
void getNNonZeros(const Index2 &dims, SparseTensor<IndexB, Float> &B) const

Returns the number of non-zeros in designated sub-spaces of this sparse tensor.

The sub-spaces are designated by dims. The B tensor collects the results.

Complexity: O(number of non-zeros)

Example: If A is a 11x13 sparse tensor:

  • A.getNNonZeros(I1(1), B) returns the number of non-zeros per row in A, and B is a vector of size 11.
  • A.getNNonZeros(I1(0), B) returns the number of non-zeros per column of A, and B is a vector of size 13.

Parameters
  • dims: [Index2] the dimensions along which to count the non-zeros
  • B: [SparseTensor<IndexB, Float>] the sparse tensor of the number of non-zeros per sub-space

template <typename Index2, typename IndexB>
void getNZeros(const Index2 &dims, SparseTensor<IndexB, Float> &B) const

Returns the number of zeros in designated sub-spaces of this sparse tensor.

See getNNonZeros doc.

bool isNull() const

Returns true if this SparseTensor is the “empty” tensor, that is, a SparseTensor with no value (like a matrix without rows).

bool isZero() const

Returns true if there is no non-zero in this tensor, false otherwise.

Return Value
  • bool: whether this sparse tensor is identically zero or not

bool isZero(const Domain<UInt> &dom) const

Returns true if the domain inside this sparse tensor is identically zero.

Doens’t work if the domain has closed dimensions. The domain needs to have the same rank as this sparse tensor.

Parameters
  • dom: [Domain<UInt>] the domain to look at
Return Value
  • bool: whether this sparse tensor is zero inside dom

bool isDense() const

Returns true if there are no zeros in this tensor, false otherwise.

The tensor is dense if it contains no zero.

Return Value
  • bool: whether this tensor is dense or not

bool isDense(const Domain<UInt> &dom) const

Returns true if the domain inside this sparse tensor is dense.

Doens’t work if the domain has closed dimensions. The domain needs to have the same rank as this sparse tensor.

Parameters
  • dom: [Domain<UInt>] the domain to look at
Return Value
  • bool: whether this sparse tensor is dense inside dom

bool isSparse() const

Returns true if there are zeros in this tensor, false otherwise.

The tensor is sparse if it contains at least one zero.

Return Value
  • bool: whether this tensor is sparse or not

bool isSparse(const Domain<UInt> &dom) const

Returns true if the domain inside this sparse tensor is sparse.

Doens’t work if the domain has closed dimensions. The domain needs to have the same rank as this sparse tensor.

Parameters
  • dom: [Domain<UInt>] the domain to look at
Return Value
  • bool: whether this sparse tensor is sparse inside dom

const Float getFillRate() const

Returns the fill rate for this tensor, that is, the ratio of the number of non-zeros to the total number of elements in this tensor.

Return Value
  • Float: the fill rate

const Float getFillRate(const Domain<UInt> &dom) const

Returns the fill rate for this tensor inside the given domain, that is, the ratio of the number of non-zeros in the given domain to the size of the domain.

Return Value
  • Float: the fill rate inside the given domain

template <typename Index2, typename IndexB>
void getFillRate(const Index2 &dims, SparseTensor<IndexB, Float> &B) const

Returns the fill rate for sub-spaces of this sparse tensor.

bool isPositive() const

Returns whether this sparse tensor is positive or not, that is, whether all its coefficients are > nupic::Epsilon (there are no zeros in this tensor, and all the elements have positive values).

Complexity: O(number of non-zeros)

bool isNonNegative() const

Returns whether this sparse tensor is non-negative or not, that is, whether all its coefficients are >= -nupic::Epsilon (there can be zeros in this tensor, but all the non-zeros have positive values).

Complexity: O(number of non-zeros)

std::map<Float, UInt> values() const

Returns the set of values in this SparseTensor and how many times each of them appears.

Complexity: O(number of non-zeros) with some log for the insertion in the result map...

void clear()

Makes this tensor the tensor zero, that is, all the non-zeros are removed.

Index getNewIndex() const

Creates a new Index that has the rank of this sparse tensor.

The initial value of this Index is the bounds of this tensor.

Note: To accomodate both Index<UInt, X> and std::vector<UInt> as indices, we can’t allocate memory ourselves, so when we need an index, we create a copy of the bounds, and either do nothing, or set it to zero, or set to some specified set of values.

Return Value
  • Index: a new Index, that contains the values of the bounds for this sparse tensor

Index getNewZeroIndex() const

Creates a new Index that has the rank of this sparse tensor and sets it to zero (see note in getNewIndex()).

Return Value

Index getNewIndex(UInt i0, ...) const

Creates a new Index that has the rank of this sparse tensor and sets it to the specified values (see note in getNewIndex()).

Return Value
  • Index: a new Index, initialized to the values passed

bool isSymmetric(const Index &perm) const

Computes whether this tensor is symmetric or not.

A tensor is symmetric w.r.t. a permutation of the dimensions iff: A[ijkl...] = A[permutation(ijkl...)]. This implies that the bounds of the permuted dimensions need to be the same. If they are not, the tensor is not symmetric. The Index passed in needs to have the same size as the rank of this sparse tensor.

Complexity: O(number of non-zeros)

Parameters
  • perm: [Index] the permutation to use to evaluate whether this sparse tensor is symmetric or not
Return Value
  • bool: whether this sparse tensor is symmetric w.r.t. the given permutation

bool isAntiSymmetric(const Index &perm) const

Computes whether this tensor is anti-symmetric or not.

A tensor is anti-symmetric w.r.t. to a permutation of the dimensions iff: A[ijkl...] = -A[permutation(ijkl...)] This implies that the upper bounds of the permuted dimensions need to be the same, or the tensor is not anti-symmetric. The Index passed in needs to have the same size as the rank of this sparse tensor.

Complexity: O(number of non-zeros)

Parameters
  • perm: [Index] the permutation to use to evaluate anti-symmetry
Return Value
  • bool: whether this sparse tensor is anty-symmetric w.r.t. the given permutation or not

void set(const Index &idx, const Float &val)

Sets the element at idx to val.

Handles zeros by not storing them, or by erasing non-zeros that become zeros when val = 0. The Index idx needs to be >= 0 and < getBounds().

Complexity: O(log(number of non-zeros))

Parameters
  • idx: [Index] the index of the element to set
  • val: [Float] the value to set for the element at index

void set(UInt i0, ...)

Sets the element at idx to val.

Calls set(Index, Float).

void set(const Domain<UInt> &dom, const Float &val)

Sets all the elements inside the dom to val.

Handles zeros correctly (i.e. does not store them).

Parameters
  • dom: [Domain<UInt>] the domain inside which to set values
  • val: [Float] the value to set inside dom

void setZero(const Index &idx)

Sets the element at idx to zero, that is, removes it from the internal storage.

Complexity: O(log(number of non-zeros))

Parameters
  • idx: [Index] the index of the element to set to zero

void setZero(UInt i0, ...)

Sets the element at idx to zero.

Calls setZero(Index).

void setZero(const Domain<UInt> &dom)

Sets to zero all the elements in Domain dom.

Parameters
  • dom: [Domain<UInt>] the domain to set to zero

void setNonZero(const Index &idx, const Float &val)

Sets element at idx to val, where |val| > nupic::Epsilon.

Use if you know what you do: even f(non-zero, non-zero) can be “zero”, if it falls below nupic::Epsilon.

Complexity: O(log(number of non-zeros))

Parameters
  • idx: [Index] the index of the element to set to val
  • val: [Float] the value to set for the element at idx

void setNonZero(const Domain<UInt> &dom, const Float &val)

Sets all the values inside dom to val.

Works only if |val| > nupic::Epsilon.

Parameters
  • dom: [Domain<UInt>] the domain inside which to set values
  • val: [Float] the value to set inside dom

template <typename binary_functor>
Float update(const Index &idx, const Float &val, binary_functor f)

Updates the value of this tensor at idx in place, using f and val: A[idx] = f(A[idx], val) (val as second argument).

Handles zeros properly.

Complexity: O(log(number of non-zeros))

void add(const Index &idx, const Float &val)

TODO: unit test.

void setAll(const Float &val)

Sets all the values in this tensor to val.

Makes this sparse tensor dense if |val| > nupic::Epsilon. Otherwise, removes all the values in this sparse tensor

Complexity: O(product of bounds) (worst case, if |val| > nupic::Epsilon)

Float get(const Index &idx) const

Returns the value of the element at idx.

Complexity: O(log(number of non-zeros))

const Float get(UInt i0, ...)

Returns the value of the element at idx.

Calls get(Index).

const Float operator()(UInt i0, ...) const

Returns the element at idx.

Calls get(Index). not providing the other one, because we need to control for zero, we can’t just blindly pass a reference

void extract(UInt dim, const std::set<UInt> &ind, SparseTensor &B) const

Extract sub-spaces along dimension dim, and put result in B.

Only the non-zeros who dim-th coordinate is in ind are kept and stored in B.

This operation reduces the size of this SparseTensor along dimension dim to the number of elements in ind. This operation reduces the size of this SparseTensor along dimension dim to the number of elements in ind. If ind is full, returns this SparseTensor unmodified. If ind is empty, throws an exception, because I can’t reduce a SparseTensor to have a size along any dimension of zero. You need to detect that ind is empty before calling reduce.

Returns the null tensor (not a tensor) if ind is empty, i.e.

dim = 0 indicates that some rows will be removed...

void reduce(UInt dim, const std::set<UInt> &ind)

In place (mutating) reduce.

Keeps only the sub-spaces (rows or columns for a matrix) whose coordinate is a member of ind. Reduces the size of the tensor along dimension dim to the size of ind. Yields the null tensor if ind is empty. Does not change the tensor if ind is full.

Examples: S2.reduce(0, set(1, 3)) keeps rows 1 and 3 of the matrix, eliminates the other rows. S2.reduce(1, set(1, 3)) keeps columns 1 and 3 of the matrix, eliminates the other columns.

template <typename IndexB>
void getSlice(const Domain<UInt> &range, SparseTensor<IndexB, Float> &B) const

Extract slices or sub-arrays from this tensor, of any dimensions, and within any bounds.

Slices can be of any dimension <= getRank(). Slices are not allocated by this function, so an optional clearYesNo parameter is provided to remove all the existing non-zeros from the slice (B). When the range is not as big as the cartesian product of the bounds of this tensor, a sub-array tensor is extracted.

Examples: If A has dimensions [(0, 10), (0, 20), (0, 30)]

  • slice with Domain = ((0, 0, 0), (10, 20, 30)) gives A
  • slice with Domain = ((0, 0, 10), (10, 20, 30)) gives the subarray of A reduced to indices 10 to 29 along the third dimension
  • slice with Domain = ((0, 0, 10), (10, 20, 10)) gives the matrix (0,10) by (0, 20) obtained when the third index is blocked to 10.

Complexity: O(number of non-zeros in slice)

Parameters
  • range: [Domain<UInt>] the range to extract from this tensor.
  • B: [SparseTensor<IndexB, Float>] the resulting slice
  • clearYesNo: [bool] whether to clear B before slicing or not

bool isZero(const Index &idx) const

Returns whether the element at idx is zero or not.

Complexity: O(log(number of non-zeros))

bool isZero(UInt i0, ...) const

Returns whether the element at idx is zero or not.

Calls isZero(Index).

template <typename OutIter>
void toDense(OutIter array) const

Copies this sparse tensor to the given array of Floats.

Sets the array to zero first, then copies only the non-zeros.

Complexity: O(number of non-zeros)

template <typename InIter>
void fromDense(InIter array, bool clearYesNo = true)

Copies the non-zeros from array into this sparse tensor.

Clears this tensor first if the flag is true.

Complexity: O(size * log(size)) ??

template <typename OutIter>
void toIdxVal(OutIter iv) const

Copies the non-zeros from this tensor to the given output iterator.

Complexity: O(number of non-zeros)

template <typename InIter>
void fromIdxVal(const UInt &nz, InIter iv, bool clearYesNo = true)

Copies the values from the input iterator into this sparse tensor.

Clear this tensor first, optionally.

template <typename InIter>
void fromIdxVal_nz(const UInt &nz, InIter iv, bool clearYesNo = true)

Copies the values from the input iterator into this sparse tensor, assuming that only non-zeros are passed.

Clear this tensor first, optionally.

template <typename InIter, typename binary_functor>
void updateFromIdxVal(const UInt &nz, InIter iv, binary_functor f)

Updates some of the values in this sparse tensor, the indices and values to use for the update being passed in the input iterator.

Uses binary functor f to carry out the update.

void toStream(std::ostream &outStream) const

Outputs the non-zeros of this sparse tensor to a stream.

Only non-zeros are put to the stream.

void fromStream(std::istream &inStream)

Reads values for this sparse tensor from a stream.

Works even if the stream contains zeros (calls set).

iterator begin()

Returns an iterator to the beginning of the non-zeros in this tensor.

Iterator iterate only over the non-zeros.

iterator end()

Returns an iterator to one past the end of the non-zeros in this tensor.

Iterator iterate only over the non-zeros.

const_iterator begin() const

Returns a const iterator to the beginning of the non-zeros in this tensor.

Iterator iterate only over the non-zeros.

const_iterator end() const

Returns a const iterator to one past the end of the non-zeros in this tensor.

Iterator iterate only over the non-zeros.

void permute(const Index &ind)

Permute the dimensions of each element of this tensor.

Complexity: O(number of non-zeros)

void resize(const Index &newBounds)

Change the bounds of this tensor, while keeping the dimensionality.

template <typename IndexB>
void reshape(SparseTensor<IndexB, Float> &B) const

Produces a tensor B that has the same non-zeros as this one but the given dimensions (the dimensions of B).

Tensor B needs to provide as much storage as this sparse tensor.

Complexity: O(number of non-zeros)

B [SparseTensor<IndexB, Float>] the target sparse tensor

void nz_intersection(const SparseTensor &B, std::vector<Index> &inter) const

Computes the set of indices where this tensor and B have common non-zeros, when A and B have the same rank.

Complexity: O(smaller number of non-zeros between this and B)

template <typename IndexB>
void nz_intersection(const IndexB &dims, const SparseTensor<IndexB, Float> &B, NonZeros<Index, IndexB> &inter) const

Computes the set of indices where the projection of this tensor on dims and B have common non-zeros.

A and B have different Ranks.

Complexity: O(number of non-zeros)

void nz_union(const SparseTensor &B, std::vector<Index> &u) const

Computes the set of indices where this tensor or B have a non-zero.

Complexity: O(sum of number of non-zeros in this and B)

template <typename IndexB>
void nz_union(const IndexB &dims, const SparseTensor<IndexB, Float> &B, NonZeros<Index, IndexB> &u) const

Computes the set of indices where the projection of this tensor on dims and B have at least one non-zero.

Complexity: O(product of bounds)

Note: wish I could find a faster way to compute that union

template <typename unary_function>
void element_apply_nz(unary_function f)

Applies the unary functor f to each non-zero element in this sparse tensor, assuming that no new non-zero is introduced.

This works for scaling, for example, if the scaling value is not zero.

: this is pretty dangerous, since it doesn’t check that f introduces new zeros!!!

template <typename unary_function>
void element_apply_fast(unary_function f)

Applies the unary functor f to each non-zero element in this tensor:

A[i] = f(A[i]), with f(0) == 0.

Assumes (and checks) that f(0) == 0. The non-zeros can change. New non-zeros can be introduced, but this function iterates on the non-zeros only.

template <typename unary_functor>
void element_apply(unary_functor f)

Applies the unary functor f to all elements in this tensor, as if it were a dense tensor.

This is useful when f(0) != 0, but it is slow because it doesn’t take advantage of the sparsity.

A[i] = f(A[i])

Complexity: O(product of the bounds)

template <typename binary_functor>
void element_apply_fast(const SparseTensor &B, SparseTensor &C, binary_functor f, bool clearYesNo = true) const

Applies the binary functor f to couple of elements from this tensor and tensor B, at the same element, where no element of the couple is zero.

The result is stored in tensor C.

C[i] = f(A[i], B[i]), where A[i] != 0 AND B[i] != 0.

This works for f = multiplication, where f(x, 0) == f(0, x) == 0, for all x. It doesn’t work for addition.

Complexity: O(smaller number of non-zeros between this and B)

template <typename binary_functor>
void element_apply_nz(const SparseTensor &B, SparseTensor &C, binary_functor f, bool clearYesNo = true) const

Applies the binary functor f to couple of elements from this tensor and tensor B, at the same index, assuming that f(0, 0) == 0.

The result is stored in tensor C.

C[i] = f(A[i], B[i]), where A[i] != 0 OR B[i] != 0

This works for f = multiplication, and f = addition. It does not work if f(0, 0) != 0.

Complexity: O(sum of number of non-zeros between this and B)

template <typename binary_functor>
void element_apply(const SparseTensor &B, SparseTensor &C, binary_functor f) const

Applies the binary functor f to couple of elements from this tensor and tensor B, at the same index, without assuming anything on f.

The result is stored in tensor C.

C[i] = f(A[i], B[i])

This works in all cases, even if f(0, 0) != 0. It does not take advantage of the sparsity.

Complexity: O(product of the bounds)

template <typename IndexB, typename binary_functor>
void factor_apply_fast(const IndexB &dims, const SparseTensor<IndexB, Float> &B, binary_functor f)

In place factor apply (mutating)

A[i] = f(A[i], B[j]), where j = projection of i on dims, and A[i] != 0 AND B[j] != 0.

This works for multiplication, but not for addition, and not if f(0, 0) == 0.

Complexity: O(smaller number of non-zeros between this and B)

template <typename IndexB, typename binary_functor>
void factor_apply_nz(const IndexB &dims, const SparseTensor<IndexB, Float> &B, binary_functor f)

In place factor apply on non-zeros (mutating).

Works for addition and multiplication.

template <typename IndexB, typename binary_functor>
void factor_apply_fast(const IndexB &dims, const SparseTensor<IndexB, Float> &B, SparseTensor<Index, Float> &C, binary_functor f, bool clearYesNo = true) const

Binary factor apply (non-mutating)

C[i] = f(A[i], B[j]), where j = projection of i on dims, and A[i] != 0 AND B[j] != 0.

This works for multiplication, but not for addition, and not if f(0, 0) == 0.

Complexity: O(smaller number of non-zeros between this and B)

template <typename IndexB, typename binary_functor>
void factor_apply_nz(const IndexB &dims, const SparseTensor<IndexB, Float> &B, SparseTensor<Index, Float> &C, binary_functor f, bool clearYesNo = true) const

C[i] = f(A[i], B[j]), where j = projection of i on dims, and A[i] != 0 OR B[j] != 0.

This works for addition, but not if f(0, 0) != 0.

Complexity: O(sum of number of non-zeros between this and B)

template <typename IndexB, typename binary_functor>
void factor_apply(const IndexB &dims, const SparseTensor<IndexB, Float> &B, SparseTensor<Index, Float> &C, binary_functor f) const

C[i] = f(A[i], B[j]), where j = projection of i on dims.

There is no restriction on f, it works even if f(0, 0) != 0. Doesn’t take advantage of the sparsity.

Complexity: O(product of bounds)

template <typename Index2, typename IndexB, typename binary_functor>
void accumulate_nz(const Index2 &dims, SparseTensor<IndexB, Float> &B, binary_functor f, const Float &init = 0) const

C[j] = f(C[j], A[i]), where j = projection of i on L dims.

Works only on the non-zeros, assumes f(0, 0) = 0 ?? Use this version AND init = 1 for multiplication.

Complexity: O(number of non-zeros)

Examples: If s2 is a 2D sparse tensor with dimensions (4, 5), and s1 a 1D sparse tensor (vector), then:

  • accumulate_nz(I1(0), s1, plus<float>(), 0) accumulates vertically, and s1 has size 5.
  • accumulate_nz(I1(1), s1, plus<float>(), 0) accumulates horizontally, and s1 has size 4.

template <typename Index2, typename IndexB, typename binary_functor>
void accumulate(const Index2 &dims, SparseTensor<IndexB, Float> &B, binary_functor f, const Float &init = 0) const

B[j] = f(B[j], A[i]), where j = projection of i on L dims.

Works on all the values, including the zeros, so it is inappropriate for multiplication, since the zeros will produce zeros in the output, even if init != 0.

No restriction on f, doesn’t take advantage of the sparsity.

Complexity: O(product of bounds)

template <typename Index2>
void normalize(const Index2 &dims)

In place (mutating) normalize.

Examples: S2.normalize(I1(UInt(0))): normalize vertically S2.normalize(I1(UInt(1))): normalize horizontally

template <typename IndexB, typename IndexC, typename binary_functor>
void outer_product_nz(const SparseTensor<IndexB, Float> &B, SparseTensor<IndexC, Float> &C, binary_functor f) const

Computes the outer product of this sparse tensor and B, puts the result in C:

C[i.j] = f(A[i], B[j]). Cijkpq = f(Aijk, Bpq)

Works only the non-zeros, assumes f(0, 0) = f(x, 0) = f(0, x) = 0. Works for multiplication, but not for addition.

Complexity: O(square of total number of non-zeros)

template <typename IndexB, typename IndexC, typename binary_functor>
void outer_product(const SparseTensor<IndexB, Float> &B, SparseTensor<IndexC, Float> &C, binary_functor f) const

Computes the outer product of this sparse tensor and B, puts the result in C:

C[i.j] = f(A[i], B[j]).

Doesn’t assume anything on f, works in all cases, but remarkably slow.

Complexity: O(square of product of bounds)

template <typename IndexB, typename binary_functor>
void contract_nz(const UInt dim1, const UInt dim2, SparseTensor<IndexB, Float> &B, binary_functor f, const Float &init = 0) const

Computes the contraction of this sparse tensor along the two given dimensions:

B[ikl...] = accumulate using f(j, A[ijkl...j...]), where j shows at positions dim1 and dim2 of A. Cikq = f(Aiuk, Buq)

Works only on the non-zeros, assumes f(0, 0) = 0 ??

Complexity: O(number of non-zeros)

template <typename IndexB, typename binary_functor>
void contract(const UInt dim1, const UInt dim2, SparseTensor<IndexB, Float> &B, binary_functor f, const Float &init = 0) const

Computes the contraction of this sparse tensor along the two given dimensions:

B[ikl...] = accumulate using f(j, A[ijkl...j...]), where j shows at positions dim1 and dim2 of A.

No assumption on f.

Complexity: O(product of bounds)

template <typename IndexB, typename IndexC, typename binary_functor1, typename binary_functor2>
void inner_product_nz(const UInt dim1, const UInt dim2, const SparseTensor<IndexB, Float> &B, SparseTensor<IndexC, Float> &C, binary_functor1 f, binary_functor2 g, const Float &init = 0) const

Computes the inner product of this sparse tensor and B, put the result in C:

C[k] = accumulate using g(product using f of B[i], C[j])

Works only on the non-zeros.

Complexity: O(square of number of non-zeros in one dim)

template <typename IndexB, typename IndexC, typename binary_functor1, typename binary_functor2>
void inner_product(const UInt dim1, const UInt dim2, const SparseTensor<IndexB, Float> &B, SparseTensor<IndexC, Float> &C, binary_functor1 f, binary_functor2 g, const Float &init = 0) const

Computes the inner product of this sparse tensor and B, put the result in C:

C[k] = accumulate using g(product using f of B[i], C[j]) Aijk, Bpq, i, p Tijkpq = f(Aijk, Bpq) Cikq = g(Tiukuq)

Complexity: O( ?? )

template <typename Index1A, typename IndexB, typename IndexC, typename binary_functor1, typename binary_functor2>
void product3(const Index1A &dimsA, const Index1A &dimsB, const SparseTensor<IndexB, Float> &B, SparseTensor<IndexC, Float> &C, binary_functor1 f) const

Another type of product.

void print(std::ostream &outStream) const

Prints out this tensor to a stream.

There are special formats for dim 1, 2 and 3, and beyond that only the non-zeros are printed out, with their indices.

template <typename Index2, typename IndexB>
void max(const Index2 &dims, SparseTensor<IndexB, Float> &B) const

Find the max of some sub-space of this sparse tensor.

Complexity: O(number of non-zeros)

Examples: If s2 is a 2D sparse tensor of size (4, 5), and s1 a 1D, then:

  • s2.max(I1(0), s1) finds the max of each column of s2 and puts it in the corresponding element of s1. s1 has size 5.
  • s2.max(I1(1), s1) finds the max of each row of s2 and puts it in the correspondin element of s1. s1 has size 4.

const std::pair<Index, Float> max() const

Finds the max of this sparse tensor, and the index of this min.

This funcion needed because SparseTensor doesn’t specialize to a scalar properly.

const Float sum() const

Returns the sum of all the non-zeros in this sparse tensor.

This funcion needed because SparseTensor doesn’t specialize to a scalar properly.

template <typename Index2, typename IndexB>
void sum(const Index2 &dims, SparseTensor<IndexB, Float> &B) const

Wrapper for accumulate with plus.

void addSlice(UInt which, UInt src, UInt dst)

Adds a slice to another.

void axby(const Float &a, const SparseTensor &B, const Float &b, SparseTensor &C) const

Adds two sparse tensors of the same rank and dimensions.

This is an element-wise addition.

void multiply(const Float &a)

Scales this sparse tensor by an arbitrary scalar a.

void multiply(const Float &a, SparseTensor &B) const

Scales this sparse tensor and put the result in B, leaving this spare tensor unchanged.

void normalize(const Float &tolerance = nupic::Epsilon)

Normalize by adding up the non-zeros across the whole tensor.

Doesn’t do anything if the sum of the tensor non-zeros adds up to 0.

Friends

template <typename I, typename F>
NTA_HIDDEN friend std::ostream& operator<<(std::ostream & outStream, const SparseTensor < I, F > & s)

Streaming operator.

See print().

template <typename I, typename F>
NTA_HIDDEN friend bool operator==(const SparseTensor < I, F > & A, const SparseTensor < I, F > & B)

Whether two sparse tensors are equal or not.

To be equal, they need to have the same number of dimensions, the same size along each dimensions, and the same non-zeros. Equality of floating point numbers is controlled by nupic::Epsilon.

template <typename I, typename F>
NTA_HIDDEN friend bool operator!=(const SparseTensor < I, F > & A, const SparseTensor < I, F > & B)

Whether two sparse tensors are different or not.

See operator==.

template <typename IndexA, typename IndexB>
class Elt

A small class to carry information about two non-zeros in an intersection or union or sparse tensors of arbitraty (possibly different) ranks.

If the ranks are different, IndexA and IndexB will have different sizes.

template <typename IndexA, typename IndexB>
struct NonZeros : public std::vector<Elt<IndexA, IndexB>>

A data structure to hold the non-zero intersection of two tensors of different dimensionalities.

Topology

Neighborhood

class Neighborhood

A class that lets you iterate over all points within the neighborhood of a point.

Usage: UInt center = 42; for (UInt neighbor : Neighborhood(center, 10, {100, 100})) { if (neighbor == center) { // Note that the center is included in the neighborhood! } else { // Do something with the neighbor. } }

A point’s neighborhood is the n-dimensional hypercube with sides ranging [center - radius, center + radius], inclusive. For example, if there are two dimensions and the radius is 3, the neighborhood is 6x6. Neighborhoods are truncated when they are near an edge.

Dimensions aren’t copied a reference is saved. Make sure the dimensions don’t get overwritten while this Neighborhood instance exists.

This is designed to be fast. It walks the list of points in the neighborhood without ever creating a list of points.

This still could be faster. Because it handles an arbitrary number of dimensions, it has to allocate vectors. It would be faster to have a Neighborhood1D, Neighborhood2D, etc., so that all computation could occur on the stack, but this would put a burden on callers to handle different dimensions counts. Or it would require using polymorphism, using pointers/references and putting the Neighborhood on the heap, which defeats the purpose of avoiding the vector allocations.

Return
An object which supports C++ range-based for loops. Each iteration of the loop returns a point in the neighborhood. Each point is expressed as a single index.
Parameters
  • centerIndex: The center of this neighborhood. The coordinates are expressed as a single index by using the dimensions as a mixed radix definition. For example, in dimensions 42x10, the point [1, 4] is index 1*420 + 4*10 = 460.
  • radius: The radius of this neighborhood about the centerIndex.
  • dimensions: The dimensions of the world outside this neighborhood.

WrappingNeighborhood

class WrappingNeighborhood

Like the Neighborhood class, except that the neighborhood isn’t truncated when it’s near an edge.

It wraps around to the other side.

Return
An object which supports C++ range-based for loops. Each iteration of the loop returns a point in the neighborhood. Each point is expressed as a single index.
Parameters
  • centerIndex: The center of this neighborhood. The coordinates are expressed as a single index by using the dimensions as a mixed radix definition. For example, in dimensions 42x10, the point [1, 4] is index 1*420 + 4*10 = 460.
  • radius: The radius of this neighborhood about the centerIndex.
  • dimensions: The dimensions of the world outside this neighborhood.