hex.gram

Class Gram

java.lang.Object

water.Iced<Gram>

hex.gram.Gram

All Implemented Interfaces:

java.io.Externalizable, java.io.Serializable, java.lang.Cloneable, water.Freezable<Gram>

public final class Gram
extends water.Iced<Gram>

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Gram.Cholesky
static class	Gram.CollinearColumnsException
static class	Gram.GramTask Task to compute gram matrix normalized by the number of observations (not counting rows with NAs).
static class	Gram.InPlaceCholesky
static class	Gram.NonSPDMatrixException
static class	Gram.OuterGramTask Task to compute outer product of a matrix normalized by the number of observations (not counting rows with NAs).

Field Summary

Fields

Modifier and Type	Field and Description
double[]	_diag
double	_diagAdded
int	_diagN
double[][]	_frame2DProduce
double[][]	_xx

Constructor Summary

Constructors

Constructor and Description
Gram(DataInfo dinfo)
Gram(int N, int diag, int dense, int sparse, boolean hasIntercept)

Method Summary

Methods

Modifier and Type	Method and Description
void	add(Gram grm)
void	addDiag(double d)
void	addDiag(double[] ds)
void	addDiag(double d, boolean add2Intercept)
void	addRow(DataInfo.Row row, double w)
void	addRowDense(DataInfo.Row row, double w)
void	addRowSparse(DataInfo.Row r, double w)
Gram.Cholesky	cholesky(Gram.Cholesky chol)
Gram.Cholesky	cholesky(Gram.Cholesky chol, boolean parallelize, java.lang.String id) Compute the Cholesky decomposition.
Gram	deep_clone()
double	diagSum()
void	dropCols(int[] cols)
void	dropIntercept()
int[]	findZeroCols()
int	fullN()
double	get(int i, int j)
double[][]	getXX()
double[][]	getXX(boolean lowerDiag, boolean icptFist)
double[][]	getXX(double[][] xalloc)
double[][]	getXX(double[][] xalloc, boolean lowerDiag, boolean icptFist)
boolean	hasNaNsOrInfs()
void	mul(double x)
double[]	mul(double[] x)
void	mul(double[] x, double[] res)
Gram.Cholesky	qrCholesky(java.util.ArrayList<java.lang.Integer> dropped_cols, boolean standardized) Compute Cholesky decompostion by computing partial QR decomposition (R == LU).
double	sparseness()
java.lang.String	toString()

Methods inherited from class water.Iced

asBytes, clone, copyOver, frozenType, read, readExternal, readJSON, reloadFromBytes, toJsonString, write, writeExternal, writeJSON

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

_xx

public double[][] _xx

_diag

public double[] _diag

_frame2DProduce

public double[][] _frame2DProduce

_diagN

public int _diagN

_diagAdded

public double _diagAdded

Constructor Detail

Gram

public Gram(DataInfo dinfo)

Gram

public Gram(int N,
    int diag,
    int dense,
    int sparse,
    boolean hasIntercept)

Method Detail

dropIntercept

public void dropIntercept()

deep_clone

public Gram deep_clone()

fullN

public final int fullN()

addDiag

public void addDiag(double[] ds)

get

public double get(int i,
         int j)

addDiag

public void addDiag(double d)

addDiag

public void addDiag(double d,
           boolean add2Intercept)

sparseness

public double sparseness()

diagSum

public double diagSum()

qrCholesky

public Gram.Cholesky qrCholesky(java.util.ArrayList<java.lang.Integer> dropped_cols,
                       boolean standardized)

Compute Cholesky decompostion by computing partial QR decomposition (R == LU). The advantage of this method over the standard solve is that it can deal with Non-SPD matrices. Gram matrix comes out as Non-SPD if we have collinear columns. QR decomposition can identify collinear (redundant) columns and remove them from the dataset. QR computation: QR is computed using Gram-Schmidt elimination, using Gram matrix instead of the underlying dataset. Gram-schmidt decomposition can be computed as follows: (from "The Eelements of Statistical Learning") 1. set z0 = x0 = 1 (Intercept) 2. for j = 1:p for l = 1:j-1 gamma_jl = dot(x_l,x_j)/dot(x_l,x_l) zj = xj - sum(gamma_j[l]*x_l) if(zj ~= 0) xj was redundant (collinear) Zjs are orthogonal projections of xk and form base of the X space. (dot(z_i,z_j) == 0 for i != j) In the end, gammas contain (Scaled) R from the QR decomp which is == LU from cholesky decomp. Note that all of these operations can be be computed from the Gram matrix only, as gram matrix contains dot(x_i,x_j) for i = 1..N, j = 1..N We can obviously compute gamma_lk directly, instead of replacing xk with zk, we fix the gram matrix. When doing that, we need to replace dot(xi,xk) with dot(xi,zk) for all i. There are two cases, 1) dot(xk,xk) -> dot(zk,zk) dot(xk - sum(gamma_l*x_l,xk - sum(gamma_l*x_l) = dot(xk,xk) - 2* sum(gamma_l*dot(x_i,x_k) + sum(gamma_l*sum(gamma_k*dot(x_l,x_k))) (can be simplified using the fact that dot(zi,zj) == 0 for i != j 2) dot(xi,xk) -> dot(xi,zk) for i != k dot(xi, xj - sum(gamma_l*x_l)) = dot(xi, xj) - dot(xi,sum(gamma_l*x_l)) = dot(xi,xj) - sum(gamma_l*dot(xi,x_l)) (linear combination The algorithm then goes as follows: for j = 1:n for l = 1:j-1 compute gamma_jl update gram by replacing xk with zk = xk- sum(gamma_jl*s*xl);

Parameters:

dropped_cols - - empty list which will be filled with collinear columns removed during computation

Returns:

Cholesky - cholesky decomposition fo the gram

dropCols

public void dropCols(int[] cols)

findZeroCols

public int[] findZeroCols()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

cholesky

public Gram.Cholesky cholesky(Gram.Cholesky chol)

cholesky

public Gram.Cholesky cholesky(Gram.Cholesky chol,
                     boolean parallelize,
                     java.lang.String id)

Compute the Cholesky decomposition. In case our gram starts with diagonal submatrix of dimension N, we exploit this fact to reduce the complexity of the problem. We use the standard decomposition of the Cholesky factorization into submatrices. We split the Gram into 3 regions (4 but we only consider lower diagonal, sparse means diagonal region in this context): diagonal diagonal*dense dense*dense Then we can solve the Cholesky in 3 steps: 1. We solve the diagonal part right away (just do the sqrt of the elements). 2. The diagonal*dense part is simply divided by the sqrt of diagonal. 3. Compute Cholesky of dense*dense - outer product of Cholesky of diagonal*dense computed in previous step

Parameters:

chol -

Returns:

the Cholesky decomposition

getXX

public double[][] getXX()

getXX

public double[][] getXX(boolean lowerDiag,
               boolean icptFist)

getXX

public double[][] getXX(double[][] xalloc)

getXX

public double[][] getXX(double[][] xalloc,
               boolean lowerDiag,
               boolean icptFist)

add

public void add(Gram grm)

hasNaNsOrInfs

public final boolean hasNaNsOrInfs()

addRowSparse

public final void addRowSparse(DataInfo.Row r,
                double w)

addRow

public final void addRow(DataInfo.Row row,
          double w)

addRowDense

public final void addRowDense(DataInfo.Row row,
               double w)

mul

public void mul(double x)

mul

public double[] mul(double[] x)

mul

public void mul(double[] x,
       double[] res)