Skip to content

combinatorial_expansion

Bases: transformation

The combinatorial data expansion function.

It performs the combinatorial data expansion of the input vector, and returns the expansion result. The class inherits from the base expansion class (i.e., the transformation class in the module directory).

...

Notes

For input vector \(\mathbf{x} \in R^m\), its combinatorial data expansion can be represented as follows: $$ \begin{equation} \kappa(\mathbf{x}) = \left[ {\mathbf{x} \choose 1}, {\mathbf{x} \choose 2}, \cdots, {\mathbf{x} \choose d} \right] \in {R}^D. \end{equation} $$

Formally, given a data instance featured by a variable set \(\mathcal{X} = \{X_1, X_2, \cdots, X_m\}\) (here, we use the upper-case \(X_i\) to denote the variable of the \(i_{th}\) feature), we can represent the possible combinations of \(d\) terms selected from \(\mathcal{X}\) as follows: $$ \begin{equation} {\mathcal{X} \choose d} = { \mathcal{C} | \mathcal{C} \subset \mathcal{X} \land |\mathcal{C}| = d }, \end{equation} $$ where \(\mathcal{C}\) denotes a subset of \(\mathcal{X}\) containing no duplicated elements and the size of the output set \({\mathcal{X} \choose d}\) will be equal to \({m \choose d}\).

Some simple examples with \(d=1\), \(d=2\) and \(d=3\) are illustrated as follows: $$ \begin{align} d = 1:\ \ &{\mathcal{X} \choose 1} = \{\{X_i\} | X_i \in \mathcal{X} \},\\ d = 2:\ \ &{\mathcal{X} \choose 2} = \{\{X_i, X_j\} | X_i, X_j \in \mathcal{X} \land X_i \neq X_j \},\\ d = 3:\ \ &{\mathcal{X} \choose 3} = \{\{X_i, X_j, X_k\} | X_i, X_j, X_k \in \mathcal{X} \land X_i \neq X_j \land X_i \neq X_k \land X_j \neq X_k \}. \end{align} $$

For combinatorial data expansion, its output expansion dimensions will be \(D = \sum_{i=1}^d i \cdot {m \choose i}\), where \(d\) denotes the combinatorial expansion order parameter.

By default, the input and output can also be processed with the optional pre- or post-processing functions in the gaussian rbf expansion function.

Attributes:

Name Type Description
name str, default = 'combinatorial_expansion'

The name of the combinatorial expansion function.
d int, default = 2

The combinatorial expansion order.
with_replacement bool, default = False

The with_replacement tag for the random combination.

Methods:

Name Description
__init__

It performs the initialization of the expansion function.
calculate_D

It calculates the expansion space dimension D based on the input dimension parameter m.
forward

It implements the abstract forward method declared in the base expansion class.
Source code in tinybig/expansion/combinatorial_expansion.py 
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
class combinatorial_expansion(transformation):
    r"""
    The combinatorial data expansion function.

    It performs the combinatorial data expansion of the input vector, and returns the expansion result.
    The class inherits from the base expansion class (i.e., the transformation class in the module directory).

    ...

    Notes
    ----------
    For input vector $\mathbf{x} \in R^m$, its combinatorial data expansion can be represented as follows:
    $$
    \begin{equation}
        \kappa(\mathbf{x}) = \left[ {\mathbf{x} \choose 1}, {\mathbf{x} \choose 2}, \cdots, {\mathbf{x} \choose d} \right] \in {R}^D.
    \end{equation}
    $$

    Formally, given a data instance featured by a variable set $\mathcal{X} = \{X_1, X_2, \cdots, X_m\}$
    (here, we use the upper-case $X_i$ to denote the variable of the $i_{th}$ feature),
    we can represent the possible combinations of $d$ terms selected from $\mathcal{X}$ as follows:
    $$
        \begin{equation}
            {\mathcal{X} \choose d} = \{ \mathcal{C} | \mathcal{C} \subset \mathcal{X} \land |\mathcal{C}| = d \},
        \end{equation}
    $$
    where $\mathcal{C}$ denotes a subset of $\mathcal{X}$ containing no duplicated elements and
    the size of the output set ${\mathcal{X} \choose d}$ will be equal to ${m \choose d}$.

    Some simple examples with $d=1$, $d=2$ and $d=3$ are illustrated as follows:
    $$
        \begin{align}
            d = 1:\ \  &{\mathcal{X} \choose 1} = \\{\\{X_i\\} | X_i \in \mathcal{X} \\},\\\\
            d = 2:\ \  &{\mathcal{X} \choose 2} = \\{\\{X_i, X_j\\} | X_i, X_j \in \mathcal{X} \land X_i \neq X_j \\},\\\\
            d = 3:\ \  &{\mathcal{X} \choose 3} = \\{\\{X_i, X_j, X_k\\} | X_i, X_j, X_k \in \mathcal{X} \land X_i \neq X_j \land X_i \neq X_k \land X_j \neq X_k \\}.
        \end{align}
    $$

    For combinatorial data expansion, its output expansion dimensions will be $D = \sum_{i=1}^d i \cdot {m \choose i}$,
    where $d$ denotes the combinatorial expansion order parameter.

    By default, the input and output can also be processed with the optional pre- or post-processing functions
    in the gaussian rbf expansion function.

    Attributes
    ----------
    name: str, default = 'combinatorial_expansion'
        The name of the combinatorial expansion function.
    d: int, default = 2
        The combinatorial expansion order.
    with_replacement: bool, default = False
        The with_replacement tag for the random combination.

    Methods
    ----------
    __init__
        It performs the initialization of the expansion function.

    calculate_D
        It calculates the expansion space dimension D based on the input dimension parameter m.

    forward
        It implements the abstract forward method declared in the base expansion class.

    """
    def __init__(self, name: str = 'combinatorial_expansion', d: int = 2, with_replacement: bool = False, *args, **kwargs):
        r"""
        The initialization method of the combinatorial expansion function.

        It initializes a combinatorial expansion object based on the input function name.
        This method will also call the initialization method of the base class as well.

        Parameters
        ----------
        name: str, default = 'combinatorial_expansion'
            The name of the combinatorial expansion function.
        d: int, default = 2
            The order of random combinations.
        with_replacement: bool, default = False
            The replacement boolean tag.

        Returns
        ----------
        transformation
            The combinatorial expansion function.
        """
        super().__init__(name=name, *args, **kwargs)
        self.d = d
        self.with_replacement = with_replacement

    def calculate_D(self, m: int):
        r"""
        The expansion dimension calculation method.

        It calculates the intermediate expansion space dimension based on the input dimension parameter m.
        For the combinatorial expansion function, the expansion space dimension will be
        $$ D = \sum_{i=1}^d i \cdot {m \choose i}. $$

        Parameters
        ----------
        m: int
            The dimension of the input space.

        Returns
        -------
        int
            The dimension of the expansion space.
        """
        assert type(self.d) is int and self.d >= 1
        return int(sum([r*comb(m, r) for r in range(1, self.d+1)]))

    @staticmethod
    def random_combinations(x: torch.Tensor, r: int = 2, with_replacement: bool = False):
        """
        The random combination generation method.

        It generates the random combinations of $r$ elements in the input data vector, where $r$ is a provided parameter.
        The method will call the torch.combinations method.

        Parameters
        ----------
        x: torch.Tensor
            The input data vector.
        r: int, default = 2
            The number of elements to be combined.
        with_replacement: bool, default = False
            The replacement boolean tag.

        Returns
        -------
        torch.Tensor
            The tensor including all the combinations of elements of size r.
        """
        assert 0 <= r <= x.numel()
        return torch.combinations(input=x, r=r, with_replacement=with_replacement)

    @staticmethod
    def combinatorial(x: torch.Tensor, d: int = 2, device='cpu', with_replacement: bool = False, *args, **kwargs):
        """
        The combinatorial generation method.

        It generates the random combinations of elements from the input data vector.
        The number of combined elements ranges from 1 to the provided order parameter d.

        Parameters
        ----------
        x: torch.Tensor
            The input data vector.
        d: int, default = 2
            The order of the random combinations.
        device: str, default = 'cpu'
            The device to perform and host the combinations.
        with_replacement: bool, default = False
            The replacement boolean tag.
        Returns
        -------
        torch.Tensor
            The tensor including all the combinations of elements of sizes from 1 to d.
        """
        # x: [batch, m]
        if len(x.shape) == 2:
            expansion = []
            for r in range(1, d + 1):
                degree_expansion = []
                for i in range(x.size(0)):
                    degree_expansion.append(combinatorial_expansion.random_combinations(x=x[i,:], r=r, with_replacement=with_replacement))
                expansion.append(degree_expansion)
            # expansion: [0:d-1, 0:batch-1, 0:(m choose d)-1]
            return expansion
        elif len(x.shape) == 1:
            # x: [m]
            expansion = []
            for r in range(1, d + 1):
                expansion.append(combinatorial_expansion.random_combinations(x=x, r=r, with_replacement=with_replacement))
            # expansion: [0:d-1, 0:(m choose d)-1]
            return expansion
        else:
            raise ValueError("Input x can only be 2d or 1d, higher dimensional inputs are not supported yet...")

    def forward(self, x: torch.Tensor, device='cpu', with_replacement: bool = False, *args, **kwargs):
        r"""
        The forward method of the combinatorial expansion function.

        It performs the combinatorial data expansion of the input data and returns the expansion result as
        $$
        \begin{equation}
            \kappa(\mathbf{x}) = \left[ {\mathbf{x} \choose 1}, {\mathbf{x} \choose 2}, \cdots, {\mathbf{x} \choose d} \right] \in {R}^D.
        \end{equation}
        $$


        Parameters
        ----------
        x: torch.Tensor
            The input data vector.
        device: str, default = 'cpu'
            The device to perform the data expansion.
        with_replacement: bool, default = False
            The replacement boolean tag.

        Returns
        ----------
        torch.Tensor
            The expanded data vector of the input.
        """
        with_replacement = with_replacement if with_replacement is not None else self.with_replacement
        return self.combinatorial(x=x, d=self.d, device=device, with_replacement=with_replacement, *args, **kwargs)

__init__(name='combinatorial_expansion', d=2, with_replacement=False, *args, **kwargs)

The initialization method of the combinatorial expansion function.

It initializes a combinatorial expansion object based on the input function name. This method will also call the initialization method of the base class as well.

Parameters:

Name Type Description Default
name str

The name of the combinatorial expansion function.

 'combinatorial_expansion'
d int

The order of random combinations.

 2
with_replacement bool

The replacement boolean tag.

 False

Returns:

Type Description
transformation

The combinatorial expansion function.
Source code in tinybig/expansion/combinatorial_expansion.py 
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
def __init__(self, name: str = 'combinatorial_expansion', d: int = 2, with_replacement: bool = False, *args, **kwargs):
    r"""
    The initialization method of the combinatorial expansion function.

    It initializes a combinatorial expansion object based on the input function name.
    This method will also call the initialization method of the base class as well.

    Parameters
    ----------
    name: str, default = 'combinatorial_expansion'
        The name of the combinatorial expansion function.
    d: int, default = 2
        The order of random combinations.
    with_replacement: bool, default = False
        The replacement boolean tag.

    Returns
    ----------
    transformation
        The combinatorial expansion function.
    """
    super().__init__(name=name, *args, **kwargs)
    self.d = d
    self.with_replacement = with_replacement

calculate_D(m)

The expansion dimension calculation method.

It calculates the intermediate expansion space dimension based on the input dimension parameter m. For the combinatorial expansion function, the expansion space dimension will be $$ D = \sum_{i=1}^d i \cdot {m \choose i}. $$

Parameters:

Name Type Description Default
m int

The dimension of the input space.

 required

Returns:

Type Description
int

The dimension of the expansion space.
Source code in tinybig/expansion/combinatorial_expansion.py 
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
def calculate_D(self, m: int):
    r"""
    The expansion dimension calculation method.

    It calculates the intermediate expansion space dimension based on the input dimension parameter m.
    For the combinatorial expansion function, the expansion space dimension will be
    $$ D = \sum_{i=1}^d i \cdot {m \choose i}. $$

    Parameters
    ----------
    m: int
        The dimension of the input space.

    Returns
    -------
    int
        The dimension of the expansion space.
    """
    assert type(self.d) is int and self.d >= 1
    return int(sum([r*comb(m, r) for r in range(1, self.d+1)]))

combinatorial(x, d=2, device='cpu', with_replacement=False, *args, **kwargs) staticmethod

The combinatorial generation method.

It generates the random combinations of elements from the input data vector. The number of combined elements ranges from 1 to the provided order parameter d.

Parameters:

Name Type Description Default
x Tensor

The input data vector.

 required
d int

The order of the random combinations.

 2
device

The device to perform and host the combinations.

 'cpu'
with_replacement bool

The replacement boolean tag.

 False

Returns:

Type Description
Tensor

The tensor including all the combinations of elements of sizes from 1 to d.
Source code in tinybig/expansion/combinatorial_expansion.py 
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
@staticmethod
def combinatorial(x: torch.Tensor, d: int = 2, device='cpu', with_replacement: bool = False, *args, **kwargs):
    """
    The combinatorial generation method.

    It generates the random combinations of elements from the input data vector.
    The number of combined elements ranges from 1 to the provided order parameter d.

    Parameters
    ----------
    x: torch.Tensor
        The input data vector.
    d: int, default = 2
        The order of the random combinations.
    device: str, default = 'cpu'
        The device to perform and host the combinations.
    with_replacement: bool, default = False
        The replacement boolean tag.
    Returns
    -------
    torch.Tensor
        The tensor including all the combinations of elements of sizes from 1 to d.
    """
    # x: [batch, m]
    if len(x.shape) == 2:
        expansion = []
        for r in range(1, d + 1):
            degree_expansion = []
            for i in range(x.size(0)):
                degree_expansion.append(combinatorial_expansion.random_combinations(x=x[i,:], r=r, with_replacement=with_replacement))
            expansion.append(degree_expansion)
        # expansion: [0:d-1, 0:batch-1, 0:(m choose d)-1]
        return expansion
    elif len(x.shape) == 1:
        # x: [m]
        expansion = []
        for r in range(1, d + 1):
            expansion.append(combinatorial_expansion.random_combinations(x=x, r=r, with_replacement=with_replacement))
        # expansion: [0:d-1, 0:(m choose d)-1]
        return expansion
    else:
        raise ValueError("Input x can only be 2d or 1d, higher dimensional inputs are not supported yet...")

forward(x, device='cpu', with_replacement=False, *args, **kwargs)

The forward method of the combinatorial expansion function.

It performs the combinatorial data expansion of the input data and returns the expansion result as $$ \begin{equation} \kappa(\mathbf{x}) = \left[ {\mathbf{x} \choose 1}, {\mathbf{x} \choose 2}, \cdots, {\mathbf{x} \choose d} \right] \in {R}^D. \end{equation} $$

Parameters:

Name Type Description Default
x Tensor

The input data vector.

 required
device

The device to perform the data expansion.

 'cpu'
with_replacement bool

The replacement boolean tag.

 False

Returns:

Type Description
Tensor

The expanded data vector of the input.
Source code in tinybig/expansion/combinatorial_expansion.py 
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
def forward(self, x: torch.Tensor, device='cpu', with_replacement: bool = False, *args, **kwargs):
    r"""
    The forward method of the combinatorial expansion function.

    It performs the combinatorial data expansion of the input data and returns the expansion result as
    $$
    \begin{equation}
        \kappa(\mathbf{x}) = \left[ {\mathbf{x} \choose 1}, {\mathbf{x} \choose 2}, \cdots, {\mathbf{x} \choose d} \right] \in {R}^D.
    \end{equation}
    $$


    Parameters
    ----------
    x: torch.Tensor
        The input data vector.
    device: str, default = 'cpu'
        The device to perform the data expansion.
    with_replacement: bool, default = False
        The replacement boolean tag.

    Returns
    ----------
    torch.Tensor
        The expanded data vector of the input.
    """
    with_replacement = with_replacement if with_replacement is not None else self.with_replacement
    return self.combinatorial(x=x, d=self.d, device=device, with_replacement=with_replacement, *args, **kwargs)

random_combinations(x, r=2, with_replacement=False) staticmethod

The random combination generation method.

It generates the random combinations of \(r\) elements in the input data vector, where \(r\) is a provided parameter. The method will call the torch.combinations method.

Parameters:

Name Type Description Default
x Tensor

The input data vector.

 required
r int

The number of elements to be combined.

 2
with_replacement bool

The replacement boolean tag.

 False

Returns:

Type Description
Tensor

The tensor including all the combinations of elements of size r.
Source code in tinybig/expansion/combinatorial_expansion.py 
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
@staticmethod
def random_combinations(x: torch.Tensor, r: int = 2, with_replacement: bool = False):
    """
    The random combination generation method.

    It generates the random combinations of $r$ elements in the input data vector, where $r$ is a provided parameter.
    The method will call the torch.combinations method.

    Parameters
    ----------
    x: torch.Tensor
        The input data vector.
    r: int, default = 2
        The number of elements to be combined.
    with_replacement: bool, default = False
        The replacement boolean tag.

    Returns
    -------
    torch.Tensor
        The tensor including all the combinations of elements of size r.
    """
    assert 0 <= r <= x.numel()
    return torch.combinations(input=x, r=r, with_replacement=with_replacement)