Repository: onnx/onnx
Pull request: Clarify definition of a tensor in IR docs
**Description**
Modify IR.md to include a mathematical definition of a tensor and some edge-case clarifications.

**Motivation and Context**
- Address uncertainties raised here: 
   - https://github.com/onnx/onnx/issues/3724
   - https://github.com/microsoft/onnxruntime-extensions/pull/175#discussion_r733942903


Problem statement:
Tensor dimensions of size zero
How should a tensor dimension of size zero be interpreted? Is that dimension ignored, or does the tensor have zero elements even if other dimensions are of non-zero size? I could not find this mentioned in the documentation.

The refernce output of backend test 'slice start out of bounds' has the shape (20,0,5) 
`onnx/onnx/backend/test/data/node/test_slice_start_out_of_bounds/test_data_set_0/output_0.pb `
The output is generated by slicing a tensor with one dimension reduced to size zero.

This is causing problems when generating C code where arrays are of size float[20][0][5]. I wonder if it is safe to just not produce any output from the node in the above test?

Hints from issue discussion:
Hi @kraiskil,
For a tensor whose shape consists zero dimension and non-zero dimension at the same time (e.g., (20, 0, 5)), the tensor has zero elements. And this behavior is similar to NumPy. This kind of tensors exist in some real-world models after Clip node.

But please note that this kind of tensors like (20, 0, 5) and (5, 0, 20), for example, are different tensors because of different shape, although they both have zero elements.

Actually, I cannot find related document about it in ONNX either. It would be helpful if ONNX can mention it in IR.md to prevent confusions. Thank you for brining this up!
Thanks for the clarification @jcwchen. 
That a tensor of size (20,0,5) is different from (5,0,20) sounds interesting. Is there a case where this is a useful distinction, or is more of a curiosity that can be ignored?
Ah yes, zero-element tensors are interesting and important to get right. Tensors with shapes (20, 0, 5) and (5, 0, 20) might seem the same (they both have no elements) but there are some real situations where the differing shape data for zero element tensors is important.

Suppose someone has a tensor of shape (100, 3, 128, 256) where the first dimension is a batch dimension and the last two are the height/width of an image.  Maybe they filter for entries with some criteria and get no results producing a tensor of shape (0, 3, 128, 256). If they use a Shape op to get the image dimensions, the dimensions 128 and 256 still must be preserved correctly. (A case very similar to this was the cause of a bug in tf2onnx.)

In a similar situation, the user might filter the images twice and concatenate the results. If one of those is empty, the dimensions still need to match for the concatenate to work.

That said, zero element tensors are rare and for practical purposes dealing with them correctly often doesn't matter. But when it does, errors can lead to bugs that are hard to find and may be difficult to fix without updating the ONNX spec for an op.

Mathematically, a tensor can be thought of as pair of sequences/arrays (V, S) where S is the shape of the tensor (a list of non-negative integers) and V is a list of values with length equal to the product of the dimensions in S.  Two tensors (V, S) and (V', S') are equal if and only if V = V' and S = S'.  This has some interesting implications:

 - S can contain dimensions of value 0. If any dimensions are 0, V must have length 0.
 - If S has length 0, V must have length 1, since the empty product is 1. In this case, the tensor represents a scalar.
 - If S has length 1, V has length equal to the single dimension in S. In this case, the tensor represents a vector.
 - A vector of length one has shape [1] and a single element. A scalar has shape [] and a single element. Scalars are _not_ vectors of length 1.

To make things additionally complicated, ONNX's Shape op returns a _tensor_, not a list as in numpy, which itself has a shape.

- For a tensor (V, S), Shape(V, S) produces a tensor with values S and shape of [len(S)].
- The shape of a scalar is []. The shape of _the shape_ of a scalar is [0].
- The tensor [1] is the only tensor where Shape(T) = T.
- For any tensor T, Shape(T) is rank 1. Shape(Shape(T)) has a single element containing the rank of T. Shape(Shape(Shape(T))) = [1].

One more thing, it is common to represent a tensor as a nested list ("ragged" representation). This generally works fine, but is problematic when zero dimensions are involved. You can represent a tensor of shape (5, 0) as [[], [], [], [], []] but (0, 5) is represented as [] which loses the information that the second dimension is 5.

- A nested list is not a complete representation of a tensor with dimensions of value zero.
I think that explanation could be put verbatim to the documentation! Thank you.

Commit message: Clarify definition of a tensor in IR docs

Signed-off-by: Tom Wildenhain <tomwi@microsoft.com>

Patch to review:
diff --git a/docs/IR.md b/docs/IR.md
index 73e96a6098e..ba8afde075d 100644
--- a/docs/IR.md
+++ b/docs/IR.md
@@ -316,6 +316,29 @@ The following data types are supported by ONNX for inputs and outputs of graphs
 
 Primitive numeric, string, and Boolean types MUST be used as elements of tensors.
 
+### Tensor Definition
+
+Tensors are a generalization of vectors and matrices; whereas vectors have one dimension, and matrices two, tensors can have any number of dimensions, including zero. A zero-dimensional tensor is logically equivalent to a scalar value.
+
+Mathematically, a tensor can be defined as pair of sequences/lists (V, S) where S is the shape of the tensor (a list of non-negative integers) and V is a list of values with length equal to the product of the dimensions in S. Two tensors (V, S) and (V', S') are equal if and only if V = V' and S = S'. The length of S is referred to as the rank.
+
+ - If S has length 0, V must have length 1, since the empty product is defined to be 1. In this case, the tensor represents a scalar.
+ - S can contain dimensions of value 0. If any dimensions are 0, V must have length 0.
+ - If S has length 1, V has length equal to the single dimension in S. In this case, the tensor represents a vector.
+ - A tensor representing a vector of length 1 has shape [1], while a tensor representing a scalar has shape []. They both have a single element, but scalars are _not_ vectors of length 1.
+
+A tensor's shape S is a list but can be converted to a tensor with values S and shape [R] where R is the rank of the tensor.
+
+ - For a tensor (V, S), the tensor representing its shape is (S, [R]).
+ - The shape of a scalar is []. The shape of the tensor representing the shape of a scalar is [0].
+ - The tensor [1] is the only tensor where the tensor representing its shape is equivalent to itself.
+
+#### Representation
+
+It is common to represent a tensor as a nested list. This generally works fine, but is problematic when zero dimensions are involved. A tensor of shape (5, 0) can be represented as [[], [], [], [], []], but (0, 5) is represented as [] which loses the information that the second dimension is 5.
+
+ - A nested list is not a complete representation of a tensor with dimensions of value zero.
+
 ### Tensor Element Types
 
 |Group|Types|Description|
@@ -333,7 +356,7 @@ The following types are used to define the types of graph and node inputs and ou
 
 |Variant | Type | Description |
 |---|---|---|
-ONNX|dense tensors|Tensors are a generalization of vectors and matrices; whereas vectors have one dimension, and matrices two, tensors can have any number of dimensions, including zero. A zero-dimensional tensor is logically equivalent to a scalar value.
+ONNX|dense tensors|Represents a Tensor. See definition above. 
 ONNX|sequence|Sequences are dense, ordered, collections of elements that are of homogeneous types.
 ONNX|map|Maps are associative tables, defined by a key type and a value type.
 ONNX|optional|Optionals are wrappers that may contain an element of tensor, sequence, or map type, or may be empty (containing none). [Details](ONNXTypes.md)


Code review comments:
diff_hunk: @@ -316,6 +316,29 @@ The following data types are supported by ONNX for inputs and outputs of graphs
 
 Primitive numeric, string, and Boolean types MUST be used as elements of tensors.
 
+### Tensor Definition
+
+Tensors are a generalization of vectors and matrices; whereas vectors have one dimension, and matrices two, tensors can have any number of dimensions, including zero. A zero-dimensional tensor is logically equivalent to a scalar value.
+
+Mathematically, a tensor can be defined as pair of sequences/lists (V, S) where S is the shape of the tensor (a list of non-negative integers) and V is a list of values with length equal to the product of the dimensions in S. Two tensors (V, S) and (V', S') are equal if and only if V = V' and S = S'. The length of S is referred to as the rank.
+
+ - If S has length 0, V must have length 1, since the empty product is defined to be 1. In this case, the tensor represents a scalar.
+ - S can contain dimensions of value 0. If any dimensions are 0, V must have length 0.
+ - If S has length 1, V has length equal to the single dimension in S. In this case, the tensor represents a vector.
+ - A tensor representing a vector of length 1 has shape [1], while a tensor representing a scalar has shape []. They both have a single element, but scalars are _not_ vectors of length 1.
+
+A tensor's shape S is a list but can be converted to a tensor with values S and shape [R] where R is the rank of the tensor.
+
+ - For a tensor (V, S), the tensor representing its shape is (S, [R]).
+ - The shape of a scalar is []. The shape of the tensor representing the shape of a scalar is [0].
path: docs/IR.md
text: @user1:
Can we split the second sentence into a separate point? And may be make it a more general claim, by saying:
```
- A shape is always represented by a tensor of rank 1 (that is, a vector)
- The shape of an empty vector is [0]
```

diff_hunk: @@ -316,6 +316,29 @@ The following data types are supported by ONNX for inputs and outputs of graphs
 
 Primitive numeric, string, and Boolean types MUST be used as elements of tensors.
 
+### Tensor Definition
+
+Tensors are a generalization of vectors and matrices; whereas vectors have one dimension, and matrices two, tensors can have any number of dimensions, including zero. A zero-dimensional tensor is logically equivalent to a scalar value.
+
+Mathematically, a tensor can be defined as pair of sequences/lists (V, S) where S is the shape of the tensor (a list of non-negative integers) and V is a list of values with length equal to the product of the dimensions in S. Two tensors (V, S) and (V', S') are equal if and only if V = V' and S = S'. The length of S is referred to as the rank.
path: docs/IR.md
text: @user1:
```suggestion
Mathematically, a tensor can be defined as a pair of sequences/lists (V, S) where S is the shape of the tensor (a list of non-negative integers) and V is a list of values with length equal to the product of the dimensions in S. Two tensors (V, S) and (V', S') are equal if and only if V = V' and S = S'. The length of S is referred to as the rank.
```