Add a BCL tensor API to represent multi-dimensional data for machine learning

[eerhardt]

Rationale

See https://blogs.msdn.microsoft.com/dotnet/2017/11/15/introducing-tensor-for-multi-dimensional-machine-learning-and-ai-data/ for rationale.

The main tagline: The motivation behind introducing Tensor is to make it easy for Machine Learning library vendors like CNTK, Tensorflow, Caffe, Scikit-Learn to port their libraries over to .NET with minimal dependencies in place.

Usage:

Scenario 1 - convert an Bitmap to Tensor to prepare the data to pass into a machine learning algorithm. Taken from here

        /// <summary>
        /// Converts the image into the expected data for the MNIST model.
        /// </summary>
        private Tensor<float> ConvertImageToTensorData(Bitmap image)
        {
            int width = _mnistInput.Shape.Dimensions[0];
            int height = _mnistInput.Shape.Dimensions[1];
            image = ResizeImage(image, new Size(width, height));

            Tensor<float> imageData = new DenseTensor<float>(new[] { width, height }, reverseStride: true); // CNTK uses ColumnMajor layout

            for (int x = 0; x < width; x++)
            {
                for (int y = 0; y < height; y++)
                {
                    Color color = image.GetPixel(x, y);
                    float pixelValue = (color.R + color.G + color.B) / 3;

                    // Turn to black background and white digit like MNIST model expects
                    imageData[x, y] = (255 - pixelValue);
                }
            }

            return imageData;
        }

Scenario 2 - Pass Tensor data into a native library that does math operations. Taken from here

        /// <summary>
        /// Solves the system of linear equations AX = B for X, where A, B, and X are general matrices.
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static DenseTensor<double> Solve(DenseTensor<double> a, DenseTensor<double> b)
        {
            if (a.Rank != 2) throw new ArgumentException("a must be a square matrix", nameof(a));
            if (a.Dimensions[0] != a.Dimensions[1]) throw new ArgumentException("a must be a square matrix", nameof(a));
            if (b.Rank != 2) throw new ArgumentException("b must be a matrix", nameof(b));
            if (a.Dimensions[0] != b.Dimensions[0]) throw new ArgumentException("The number of rows in b must match the number of rows in a", nameof(b));

            // need to clone the inputs because LAPack will mutate the values
            var aClone = (DenseTensor<double>)a.Clone();
            var bClone = (DenseTensor<double>)b.Clone();

            unsafe
            {
                Span<int> pivotIntegers = stackalloc int[a.Dimensions[1]];
                fixed (double* aPtr = &aClone.Buffer.Span.DangerousGetPinnableReference())
                fixed (double* bPtr = &bClone.Buffer.Span.DangerousGetPinnableReference())
                fixed (int* ipiv = &pivotIntegers.DangerousGetPinnableReference())
                {
                    LAPACKE_dgesv(
                        a.IsReversedStride ? LAPACK_COL_MAJOR : LAPACK_ROW_MAJOR, 
                        a.Dimensions[0], 
                        b.Dimensions[1], 
                        aPtr, 
                        a.Dimensions[1], 
                        ipiv, 
                        bPtr, 
                        b.Dimensions[1]);
                }
            }

            return bClone;
        }

        [DllImport("liblapacke.dll")]
        static extern unsafe int LAPACKE_dgesv(int matrix_layout, int n, int nrhs, double* a, int lda, int* ipvt, double* bx, int ldb);
    }

Proposed API

namespace System.Numerics.Tensors
{
    // All interface members will be implemented explicitly unless exposed below
    public abstract class Tensor<T> : ICollection, ICollection<T>, IEnumerable, IEnumerable<T>, IList, IList<T>, IReadOnlyCollection<T>, IReadOnlyList<T>, IStructuralComparable, IStructuralEquatable
    {
        protected Tensor(Array fromArray, bool reverseStride);
        protected Tensor(int length);
        protected Tensor(ReadOnlySpan<int> dimensions, bool reverseStride);

        public ReadOnlySpan<int> Dimensions { get; }
        public bool IsFixedSize { get; }
        public bool IsReadOnly { get; }
        public bool IsReversedStride { get; }
        public long Length { get; }
        public int Rank { get; }
        public ReadOnlySpan<int> Strides { get; }

        public virtual T this[params int[] indices] { get; set; }
        public virtual T this[ReadOnlySpan<int> indices] { get; set; }

        public abstract Tensor<T> Clone();
        public virtual Tensor<T> CloneEmpty();
        public virtual Tensor<T> CloneEmpty(ReadOnlySpan<int> dimensions);
        public virtual Tensor<TResult> CloneEmpty<TResult>();
        public abstract Tensor<TResult> CloneEmpty<TResult>(ReadOnlySpan<int> dimensions);

        protected virtual bool Contains(T item);
        protected virtual void CopyTo(T[] array, int arrayIndex);
        protected virtual int IndexOf(T item);

        public virtual void Fill(T value);

        public string GetArrayString(bool includeWhitespace=true);

        public Tensor<T> GetDiagonal();
        public Tensor<T> GetDiagonal(int offset);

        public Tensor<T> GetTriangle();
        public Tensor<T> GetTriangle(int offset);

        public Tensor<T> GetUpperTriangle();
        public Tensor<T> GetUpperTriangle(int offset);

        public abstract T GetValue(int index);
        public abstract void SetValue(int index, T value);

        public Tensor<T> MatrixMultiply(Tensor<T> right);

        public abstract Tensor<T> Reshape(ReadOnlySpan<int> dimensions);

        public Tensor<T> Slice(params Range[] ranges);
        public virtual Tensor<T> Slice(ReadOnlySpan<Range> ranges);

        public virtual CompressedSparseTensor<T> ToCompressedSparseTensor();
        public virtual DenseTensor<T> ToDenseTensor();
        public virtual SparseTensor<T> ToSparseTensor();

        public static int Compare(Tensor<T> left, Tensor<T> right);
        public static bool Equals(Tensor<T> left, Tensor<T> right);

        public static Tensor<T> operator +(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator +(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator &(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator &(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator |(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator |(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator --(Tensor<T> tensor);
        public static Tensor<T> operator /(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator /(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator ^(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator ^(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator ++(Tensor<T> tensor);
        public static Tensor<T> operator <<(Tensor<T> tensor, int value);
        public static Tensor<T> operator %(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator %(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator *(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator *(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator >>(Tensor<T> tensor, int value);
        public static Tensor<T> operator -(Tensor<T> left, Tensor<T> right);
        public static Tensor<T> operator -(Tensor<T> tensor, T scalar);
        public static Tensor<T> operator -(Tensor<T> tensor);
        public static Tensor<T> operator +(Tensor<T> tensor);
    }

    public class DenseTensor<T> : Tensor<T>
    {
        public DenseTensor(int length);
        public DenseTensor(Memory<T> memory, ReadOnlySpan<int> dimensions, bool reverseStride=false);
        public DenseTensor(ReadOnlySpan<int> dimensions, bool reverseStride=false);

        public Memory<T> Buffer { get; }

        public override Tensor<T> Clone();
        public override Tensor<TResult> CloneEmpty<TResult>(ReadOnlySpan<int> dimensions);

        protected override void CopyTo(T[] array, int arrayIndex);
        protected override int IndexOf(T item);

        public override T GetValue(int index);
        public override void SetValue(int index, T value);

        public override Tensor<T> Reshape(ReadOnlySpan<int> dimensions);
    }

    public class CompressedSparseTensor<T> : Tensor<T>
    {
        public CompressedSparseTensor(Memory<T> values, Memory<int> compressedCounts, Memory<int> indices, int nonZeroCount, ReadOnlySpan<int> dimensions, bool reverseStride=false);
        public CompressedSparseTensor(ReadOnlySpan<int> dimensions, bool reverseStride=false);
        public CompressedSparseTensor(ReadOnlySpan<int> dimensions, int capacity, bool reverseStride=false);

        public int Capacity { get; }
        public Memory<int> CompressedCounts { get; }
        public Memory<int> Indices { get; }
        public int NonZeroCount { get; }
        public Memory<T> Values { get; }

        public override T this[ReadOnlySpan<int> indices] { get; set; }

        public override Tensor<T> Clone();
        public override Tensor<TResult> CloneEmpty<TResult>(ReadOnlySpan<int> dimensions);

        public override T GetValue(int index);
        public override void SetValue(int index, T value);

        public override Tensor<T> Reshape(ReadOnlySpan<int> dimensions);

        public override CompressedSparseTensor<T> ToCompressedSparseTensor();
        public override DenseTensor<T> ToDenseTensor();
        public override SparseTensor<T> ToSparseTensor();
    }

    public class SparseTensor<T> : Tensor<T>
    {
        public SparseTensor(ReadOnlySpan<int> dimensions, bool reverseStride=false, int capacity=0);

        public int NonZeroCount { get; }

        public override Tensor<T> Clone();
        public override Tensor<TResult> CloneEmpty<TResult>(ReadOnlySpan<int> dimensions);

        public override T GetValue(int index);
        public override void SetValue(int index, T value);

        public override Tensor<T> Reshape(ReadOnlySpan<int> dimensions);

        public override CompressedSparseTensor<T> ToCompressedSparseTensor();
        public override DenseTensor<T> ToDenseTensor();
        public override SparseTensor<T> ToSparseTensor();
    }

    public static class ArrayTensorExtensions
    {
        public static CompressedSparseTensor<T> ToCompressedSparseTensor<T>(this Array array, bool reverseStride=false);
        public static CompressedSparseTensor<T> ToCompressedSparseTensor<T>(this T[,,] array, bool reverseStride=false);
        public static CompressedSparseTensor<T> ToCompressedSparseTensor<T>(this T[,] array, bool reverseStride=false);
        public static CompressedSparseTensor<T> ToCompressedSparseTensor<T>(this T[] array);

        public static SparseTensor<T> ToSparseTensor<T>(this Array array, bool reverseStride=false);
        public static SparseTensor<T> ToSparseTensor<T>(this T[,,] array, bool reverseStride=false);
        public static SparseTensor<T> ToSparseTensor<T>(this T[,] array, bool reverseStride=false);
        public static SparseTensor<T> ToSparseTensor<T>(this T[] array);

        public static DenseTensor<T> ToTensor<T>(this Array array, bool reverseStride=false);
        public static DenseTensor<T> ToTensor<T>(this T[,,] array, bool reverseStride=false);
        public static DenseTensor<T> ToTensor<T>(this T[,] array, bool reverseStride=false);
        public static DenseTensor<T> ToTensor<T>(this T[] array);
    }

    public static class Tensor
    {
        public static Tensor<T> Add<T>(Tensor<T> left, Tensor<T> right);
        public static void Add<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> Add<T>(Tensor<T> tensor, T scalar);
        public static void Add<T>(Tensor<T> tensor, T scalar, Tensor<T> result);

        public static Tensor<T> And<T>(Tensor<T> left, Tensor<T> right);
        public static void And<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> And<T>(Tensor<T> tensor, T scalar);
        public static void And<T>(Tensor<T> tensor, T scalar, Tensor<T> result);

        public static Tensor<T> Contract<T>(Tensor<T> left, Tensor<T> right, int[] leftAxes, int[] rightAxes);
        public static void Contract<T>(Tensor<T> left, Tensor<T> right, int[] leftAxes, int[] rightAxes, Tensor<T> result);

        public static Tensor<T> CreateFromDiagonal<T>(Tensor<T> diagonal);
        public static Tensor<T> CreateFromDiagonal<T>(Tensor<T> diagonal, int offset);

        public static Tensor<T> CreateIdentity<T>(int size);
        public static Tensor<T> CreateIdentity<T>(int size, bool columMajor);
        public static Tensor<T> CreateIdentity<T>(int size, bool columMajor, T oneValue);

        public static Tensor<T> Decrement<T>(Tensor<T> tensor);
        public static void Decrement<T>(Tensor<T> tensor, Tensor<T> result);

        public static Tensor<T> Divide<T>(Tensor<T> left, Tensor<T> right);
        public static void Divide<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> Divide<T>(Tensor<T> tensor, T scalar);
        public static void Divide<T>(Tensor<T> tensor, T scalar, Tensor<T> result);

        public static Tensor<Boolean> Equals<T>(Tensor<T> left, Tensor<T> right);
        public static void Equals<T>(Tensor<T> left, Tensor<T> right, Tensor<Boolean> result);

        public static Tensor<Boolean> GreaterThan<T>(Tensor<T> left, Tensor<T> right);
        public static void GreaterThan<T>(Tensor<T> left, Tensor<T> right, Tensor<Boolean> result);

        public static Tensor<Boolean> GreaterThanOrEqual<T>(Tensor<T> left, Tensor<T> right);
        public static void GreaterThanOrEqual<T>(Tensor<T> left, Tensor<T> right, Tensor<Boolean> result);

        public static Tensor<T> Increment<T>(Tensor<T> tensor);
        public static void Increment<T>(Tensor<T> tensor, Tensor<T> result);

        public static Tensor<T> LeftShift<T>(Tensor<T> tensor, int value);
        public static void LeftShift<T>(Tensor<T> tensor, int value, Tensor<T> result);

        public static Tensor<Boolean> LessThan<T>(Tensor<T> left, Tensor<T> right);
        public static void LessThan<T>(Tensor<T> left, Tensor<T> right, Tensor<Boolean> result);

        public static Tensor<Boolean> LessThanOrEqual<T>(Tensor<T> left, Tensor<T> right);
        public static void LessThanOrEqual<T>(Tensor<T> left, Tensor<T> right, Tensor<Boolean> result);

        public static Tensor<T> Modulo<T>(Tensor<T> left, Tensor<T> right);
        public static void Modulo<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> Modulo<T>(Tensor<T> tensor, T scalar);
        public static void Modulo<T>(Tensor<T> tensor, T scalar, Tensor<T> result);

        public static Tensor<T> Multiply<T>(Tensor<T> left, Tensor<T> right);
        public static void Multiply<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> Multiply<T>(Tensor<T> tensor, T scalar);
        public static void Multiply<T>(Tensor<T> tensor, T scalar, Tensor<T> result);

        public static Tensor<Boolean> NotEquals<T>(Tensor<T> left, Tensor<T> right);
        public static void NotEquals<T>(Tensor<T> left, Tensor<T> right, Tensor<Boolean> result);

        public static Tensor<T> Or<T>(Tensor<T> left, Tensor<T> right);
        public static void Or<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> Or<T>(Tensor<T> tensor, T scalar);
        public static void Or<T>(Tensor<T> tensor, T scalar, Tensor<T> result);

        public static Tensor<T> RightShift<T>(Tensor<T> tensor, int value);
        public static void RightShift<T>(Tensor<T> tensor, int value, Tensor<T> result);

        public static Tensor<T> Subtract<T>(Tensor<T> left, Tensor<T> right);
        public static void Subtract<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> Subtract<T>(Tensor<T> tensor, T scalar);
        public static void Subtract<T>(Tensor<T> tensor, T scalar, Tensor<T> result);

        public static Tensor<T> UnaryMinus<T>(Tensor<T> tensor);
        public static void UnaryMinus<T>(Tensor<T> tensor, Tensor<T> result);

        public static Tensor<T> UnaryPlus<T>(Tensor<T> tensor);
        public static void UnaryPlus<T>(Tensor<T> tensor, Tensor<T> result);

        public static Tensor<T> Xor<T>(Tensor<T> left, Tensor<T> right);
        public static void Xor<T>(Tensor<T> left, Tensor<T> right, Tensor<T> result);
        public static Tensor<T> Xor<T>(Tensor<T> tensor, T scalar);
        public static void Xor<T>(Tensor<T> tensor, T scalar, Tensor<T> result);
    }
}

namespace System
{
    struct Range
    {
        public Range(int start, int end);
        public int Start { get; }
        public int End { get; }
    }
}

Details

• A Range type is needed in order to support the Tensor.Slice method. The proposal is to introduce a System.Range struct to the System.Memory package. Note that this Range is also necessary for the new range syntax proposed for C#.
• Tensor doesn't need a long Range type, because all the dimensions are represented by int.
• It would be very convenient to have unbounded Ranges in both start and end for Tensor, so users can easily say "I want all rows with these columns", or "I want all columns with these rows", etc.
• I haven't found a concrete user scenario for Ranges with "steps" (ex. "I want every other row" or "every fourth row"). The current proposal is to not support slicing with steps in v1.

[karelz]

@eerhardt does it need to go through API review?

[eerhardt]

I think it already went through a first round, but yes, we should do a final/official API review.

The proposal is to use the APIs that are public in corefxlab.

[karelz]

Can you please post the API shape here? Or link to it if it is "too big". Then mark the issue as api-ready-for-review? Please ping Immo to schedule it, thanks!

[danmoseley]

@tannergooding not sure whether you've already given feedback on this API, or whether it's the sort of API that interests you.

[tannergooding]

I've been following it (but not very closely).

The API shape overall looks reasonable to me.

• nit: it would be helpful to add a newline between the logical API groupings (i.e. between ToCompressedSparseTensor and ToSparseTensor or between the constructors, properties, and methods, etc)

My feedback:
ArrayTensorExtensions.ToTensor should be ArrayTensorExtensions.ToDenseTensor, to match the naming of the other To*Tensor methods (and also to match Tensor.ToDenseTensor).

I would prefer if the Clone methods were explicit (i.e. DeepClone or ShallowClone)

Why GetValue and SetValue instead of an indexer?

Do we know if the C# language feature is going to be Range or Range<T>?

[terrajobst]

This looks like an API that we'll need 2 hours for.

@eerhardt @OliaG How soon does this need to happen?

[eerhardt]

This looks like an API that we'll need 2 hours for.

Yes, it is a larger API and will take some time. Especially the discussion around the Range type.

How soon does this need to happen?

The plan is to ship this in .NET Core 2.1. I'd like to get it into the first preview so it has more bake time, and more chance of getting feedback.

[eerhardt]

nit: it would be helpful to add a newline between the logical API groupings (i.e. between ToCompressedSparseTensor and ToSparseTensor or between the constructors, properties, and methods, etc)

Good call. Fixed.

ArrayTensorExtensions.ToTensor should be ArrayTensorExtensions.ToDenseTensor, to match the naming of the other To*Tensor methods (and also to match Tensor.ToDenseTensor).

I had the same feedback, but @ericstj's thoughts were: dotnet/corefxlab#1806 (comment)

I would prefer if the Clone methods were explicit (i.e. DeepClone or ShallowClone)

I have no strong opinion either way. I can let the API review team decide. Here are my initial thoughts:

• The typical usage is to use numbers in a Tensor, which "Clone" may be explicit enough for numbers.
• ShallowCloneEmpty sounds odd to me.

Why GetValue and SetValue instead of an indexer?

There are indexers for the n-dimensional indices. GetValue and SetValue are for the linearized index, for the cases where a caller already has the linearized index and doesn't want/need to convert them into n-dimensional indices (which then get turned back into the linearized index under the covers).

Do we know if the C# language feature is going to be Range or Range?

I took the above proposal from their proposal (minus the IEnumerable part, since I don't need that).

[danmoseley]

Presumably we need Roslyn to confirm the Range type, since they're going to adopt it. @khyperia

[tannergooding]

I had the same feedback, but @ericstj's thoughts were: dotnet/corefxlab#1806 (comment)

I feel like that violates one of the .NET Naming Guidelines (https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/), but I don't have time to go searching through and finding it right now.

[terrajobst]

@tannergooding

It doesn't violate the naming convention because ToTensor() does a return an instance of the Tensor<T> class -- it's just a more specific subclass.

[tannergooding]

@terrajobst: Having a method with a signature of <SubType> To<Type>(), at least to me, is not intuitive.

I would have expected the signature of an API called ToTensor() to be Tensor<T> ToTensor(). Then it would be returning Tensor as part of its public contract, but could internally return a different subtype and still be accurate.

Think of it this way: If Tensor<T> was not abstract, then DenseTensor<T> ToTensor() would prevent the existence of Tensor<T> ToTensor(), since overloading by return type isn't allowed in C#.

[danmoseley]

@jaredpar @nguerrera FYI this proposes to depend on Range so we should coordinate on implementation.