Runtime: 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

```C#
///

/// Converts the image into the expected data for the MNIST model.
///

private Tensor 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](https://github.com/eerhardt/TensorLinearAlgebra/blob/e3f98eebad6af91a851131164b89c6e02f3e19fd/LinearAlgebra.cs#L12)
```C#
        /// <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

```C#
namespace System.Numerics.Tensors
{
// All interface members will be implemented explicitly unless exposed below
public abstract class Tensor : ICollection, ICollection, IEnumerable, IEnumerable, IList, IList, IReadOnlyCollection, IReadOnlyList, IStructuralComparable, IStructuralEquatable
{
protected Tensor(Array fromArray, bool reverseStride);
protected Tensor(int length);
protected Tensor(ReadOnlySpan 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!

[danmosemsft]

@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: https://github.com/dotnet/corefxlab/pull/1806#discussion_r142194947

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).

[danmosemsft]

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#.

[danmosemsft]

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

[nietras]

Please see https://github.com/dotnet/corefxlab/issues/1938 for a critique of this API design.

[karelz]

API review comments:

• CompressedTensor
  
  
  
  • Indexer - changing recalculates the encoding - can we avoid that?
  
  
  • Change Memory-returning getters to ReadOnlyMemory (CompressedCounts and Indices)
  
  
• Tensor.Slice - does it have to be fast? Should we create TensorView struct?
• Deep copy vs. shallow copy and where we in general reuse underlying – should be clear from API name
• Arithmetic is troublesome - remove it for preview1
  
  
  
  • Tensor<T> should have where T : IComparable<T> instead
  
  
• CloneEmpty may need better name (Clone contradicts Empty)
• Linearized indexes - why are they exposed in public APIs? (GetValue, SetValue, IndexOf, CopyTo)
• GetArrayString rename to ToString (overriding object + overload with bool includeWhitespace)
• Compare is questionable (IStructuralComparable) - it may make sense on arrays, but unclear on multi-dimensional tensors

[karelz]

FYI:
The first API review discussion on 12/12 was recorded - see https://youtu.be/KKUjm8zaJBM?t=3014 (65 min duration)

The follow up 2h API review discussion on 12/14 was NOT recorded - see the notes above: https://github.com/dotnet/corefx/issues/25779#issuecomment-351883459

[jkotas]

Make it easy for Machine Learning library vendors like CNTK, Tensorflow, Caffe, Scikit-Learn to port their libraries over

Have we proved that the proposed API achieves this goal?

It seems that this API will very likely need iterating on before it is declared stable, similar to how we have been iterating on Span/Memory or pipelines to make them work well for ASP.NET Core.

[nietras]

It seems that this API will very likely need iterating on before it is declared stable, similar to how we have been iterating on Span/Memory or pipelines to make them work well for ASP.NET Core.

I very much agree with @jkotas that this proposal needs time to mature before making a proper proposal for the BCL. Not the least being real usage in different use cases.

One also has to consider what the target area is for this? Is it for running inference in production? Is it for "off-line" learning? Real time learning? Ease of use? Each area would have their own requirements,

I favor something that can in fact be used for inference in production with as low an overhead as possible, this means low level primitives with great performance is key, while ease of use is not the first priority. That can be build on top of that.

[helloguo]

How about abs, neg and pow? Other tensor operations listed in following references could be interesting as well.

Ref:
https://www.cntk.ai/pythondocs/_modules/cntk/tensor.html
https://www.tensorflow.org/api_docs/python/tf/Tensor
https://github.com/onnx/onnx/blob/master/onnx/defs/math/defs.cc

[fuglede]

A mathematician's nitpick on naming: A tensor is only represented by a multi-dimensional array (which is what this data structure represents) after a choice of basis, and its representation will depend on that choice. You wouldn't have named System.Numerics.Matrix System.Numerics.LinearTransformation.

[danmosemsft]

@tannergooding can give an update here.