1# Copyright 2016 The TensorFlow Authors. All Rights Reserved. 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14# ============================================================================== 15"""Ops to work with `SparseTensor`.""" 16 17from __future__ import absolute_import 18from __future__ import division 19from __future__ import print_function 20 21from tensorflow.python.framework import dtypes 22from tensorflow.python.framework import ops 23from tensorflow.python.framework import sparse_tensor 24from tensorflow.python.ops import array_ops 25from tensorflow.python.ops import math_ops 26from tensorflow.python.util import compat 27 28 29def _multiplier_helper(shape): 30 """Returns moving offset for each dimension given shape.""" 31 multipliers = [] 32 for dim in reversed(shape): 33 if multipliers: 34 multipliers.append(dim * multipliers[-1]) 35 else: 36 multipliers.append(dim) 37 multipliers.reverse() 38 return multipliers 39 40 41def _ignore_value_tensor(dtype, ignore_value=None): 42 """Create `Tensor` from provided `ignore_value` and `dtype`.""" 43 if ignore_value is None: 44 if dtype == dtypes.string: 45 # Exception due to TF strings are converted to numpy objects by default. 46 ignore_value = "" 47 else: 48 # NOTE: `as_numpy_dtype` is a property, so with the parentheses this is 49 # constructing a new numpy object of the given type, which yields the 50 # default value for that type. 51 ignore_value = dtype.as_numpy_dtype() 52 return math_ops.cast(ignore_value, dtype, name="ignore_value") 53 54 55def dense_to_sparse_tensor(dense_tensor, ignore_value=None): 56 """Converts dense `Tensor` to `SparseTensor`, dropping `ignore_value` cells. 57 58 Args: 59 dense_tensor: A `Tensor`. 60 ignore_value: Entries in `dense_tensor` equal to this value will be 61 absent from the return `SparseTensor`. If `None`, default value of 62 `dense_tensor` dtype will be used (e.g. '' for `str`, 0 for `int`). 63 64 Returns: 65 A `SparseTensor` with the same shape as `dense_tensor`. 66 67 Raises: 68 ValueError: when `dense_tensor`'s rank is `None`. 69 """ 70 with ops.name_scope("DenseToSparseTensor"): 71 dense_tensor = ops.convert_to_tensor(dense_tensor) 72 ignore_value = _ignore_value_tensor(dense_tensor.dtype, ignore_value) 73 indices = array_ops.where( 74 math_ops.not_equal(dense_tensor, ignore_value), name="indices") 75 return sparse_tensor.SparseTensor( 76 indices=indices, 77 values=array_ops.gather_nd(dense_tensor, indices, name="values"), 78 dense_shape=array_ops.shape( 79 dense_tensor, out_type=dtypes.int64, name="dense_shape")) 80 81 82def indicators_to_sparse_ids(indicators, ignore_value=None, dtype=dtypes.int64): 83 """Convert a dense indicator tensor to sparse IDs. 84 85 This is commonly used for converting a dense classification label to sparse. 86 In the following example, we have an input of shape (2, 2, num_classes), 87 where num_classes=4. 88 89 ```python 90 indicators = [ 91 [ 92 [0, 0, 1, 0], 93 [0, 0, 0, 0] 94 ], [ 95 [1, 0, 1, 1], 96 [0, 0, 1, 0] 97 ] 98 ] 99 sparse_ids = indicator_to_sparse_ids(indicators) 100 ``` 101 102 `sparse_ids` in "jagged" format: 103 [ 104 [ 105 [2], 106 [] 107 ], [ 108 [0, 2, 3], 109 [2] 110 ] 111 ] 112 113 `sparse_ids` in `SparseTensor` format: 114 ```python 115 { 116 indices: [[0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 1, 0]], 117 values: [2, 0, 2, 3, 2], 118 dense_shape: [2, 2, 3] 119 } 120 ``` 121 122 Args: 123 indicators: Dense `Tensor` of shape `(d0, ..., dn, num_classes)`. 124 `ignore_value` values are ignored. For other values (typically, ones), the 125 index along the last dimension is returned. 126 ignore_value: Entries in `indicators` equal to this value will be 127 absent from the returned `SparseTensor`. If `None`, default value of 128 `indicators` dtype will be used (e.g. '' for `str`, 0 for `int`). 129 dtype: Type of result, must be integer type. 130 131 Returns: 132 `SparseTensor` of type `dtype` and shape `(d0, ..., dn, max_num_labels)`, 133 where `max_num_labels` is the maximum number of non-zero values in any 134 row (in the example above, row (1, 1) has 3 non-zero values, so the result 135 shape is (2, 2, 3)). The values of this `SparseTensor` are in the range 136 `[0, num_classes)` and correspond to the index of non-ignore values along 137 the last dimension of `indicators`. 138 139 Raises: 140 ValueError: if `dtype` is not integer. 141 """ 142 if not dtype.is_integer: 143 raise ValueError("Invalid dtype {} not integer.".format(dtype)) 144 with ops.name_scope( 145 None, "indicators_to_sparse_ids", (indicators, ignore_value)): 146 # Convert indicators to binary ones and zeros. We use int64 since 147 # SparseTensor requires int64 indices. 148 indicators = ops.convert_to_tensor(indicators, name="indicators") 149 missing_indicators = math_ops.equal( 150 indicators, _ignore_value_tensor(indicators.dtype, ignore_value), 151 name="missing") 152 zeros_like_indicators = array_ops.zeros_like( 153 indicators, dtype=dtypes.int64, name="zeros") 154 binary_indicators = array_ops.where( 155 missing_indicators, zeros_like_indicators, 156 array_ops.ones_like(indicators, dtype=dtypes.int64, name="ones"), 157 name="binary_indicators") 158 159 # Use cumsum along the last dimension to generate per-row indexes. 160 # Note that these are 1-based (since 0 indicates missing values), so they're 161 # off-by-1 from the actual indices. We'll subtract 1 below. Since they're 162 # off-by-one, the max value is the size of the last dimension (i.e., 163 # last_index + 1). 164 row_index_indicators = array_ops.where( 165 missing_indicators, zeros_like_indicators, 166 math_ops.cumsum(binary_indicators, axis=-1), "row_index_indicators") 167 result_last_dim = array_ops.reshape( 168 math_ops.reduce_max(row_index_indicators), shape=(1,), 169 name="result_last_dim") 170 171 # Convert to a SparseTensor. The values of this SparseTensor are the last 172 # indices of our result, and the last indices of this SparseTensor (i.e., 173 # the class IDs indicated by `indicators`) are the values of our result, so 174 # we use tensor slicing and concat to swap them. 175 sparse_row_index_indicators = dense_to_sparse_tensor( 176 row_index_indicators, ignore_value=0) 177 return sparse_tensor.SparseTensor( 178 indices=array_ops.concat(( 179 sparse_row_index_indicators.indices[:, :-1], 180 array_ops.reshape(sparse_row_index_indicators.values - 1, (-1, 1)) 181 ), axis=1, name="indices"), 182 values=math_ops.cast( 183 sparse_row_index_indicators.indices[:, -1], dtype=dtype, 184 name="values"), 185 dense_shape=array_ops.concat( 186 (sparse_row_index_indicators.dense_shape[0:-1], result_last_dim), 187 axis=0, name="dense_shape")) 188 189 190def sparse_row_envelope(sparse_input, row_axis=0, col_axis=1, name=None): 191 """Returns the length of each 'row' in a `SparseTensor`. 192 193 For example, if `sparse_input` has indices `[[0,0], [2, 0], [2, 1], [2, 2]]` 194 and shape `[3, 3]`, this function will return `[1, 0, 3]`. 195 196 Args: 197 sparse_input: a `SparseTensor` of rank at least 2. 198 row_axis: An integer. The axis for the row of the envelope matrix. Default 199 is 0. 200 col_axis: An integer. The axis for the col of the envelope matrix. Default 201 is 1. 202 name: A name for the operation (optional). 203 204 Returns: 205 A one-dimensional `Tensor` whose entries correspond to the length of each 206 row of `SparseTensor`. 207 208 Raises: 209 ValueError: If row_axis and col_axis are the same axis or they are not 210 integers. 211 """ 212 if not (isinstance(row_axis, compat.integral_types) and 213 isinstance(col_axis, compat.integral_types)): 214 raise ValueError("`row_axis` and `col_axis` must be integers.") 215 216 if row_axis == col_axis: 217 raise ValueError("Row and column can not be the same axis.") 218 219 with ops.name_scope(name, "sparse_row_envelope", [sparse_input]): 220 indices = sparse_input.indices 221 row_indices = indices[:, row_axis] 222 col_indices = indices[:, col_axis] 223 num_rows = math_ops.cast(sparse_input.dense_shape[row_axis], dtypes.int32) 224 row_envelope = math_ops.unsorted_segment_max( 225 col_indices + 1, row_indices, num_rows, name=name) 226 zeros = array_ops.zeros_like(row_envelope) 227 return array_ops.where(row_envelope > zeros, row_envelope, zeros) 228