Log-Determinant Mutual Information¶
- class submodlib.functions.logDeterminantMutualInformation.LogDeterminantMutualInformationFunction(n, num_queries, lambdaVal, data_sijs=None, query_sijs=None, query_query_sijs=None, data=None, queryData=None, metric='cosine', magnificationEta=1)[source]¶
Implementation of the Log Determinant Mutual Information (LogDetMI) function.
Given a Submodular Mutual Information function, Log Determinant Mutual Information function is its instantiation using a
LogDeterminantFunction.Let \(S_{A, B}\) be the cross-similarity matrix between the items in sets \(A\) and \(B\). Also, denote \(S_{AB} = S_{A \cup B}\).
We construct a similarity matrix \(S^{\eta}\) (on a base matrix \(S\)) in such a way that the cross-similarity between \(A\) and \(Q\) is multiplied by \(\eta\) (i.e \(S^{\eta}_{A,Q} = \eta S_{A,Q}\)) to control the trade-off between query relevance and diversity. Higher values of \(\eta\) ensure greater query-relevance while lower values favor diversity.
Using a similarity matrix defined above and with \(f(A) = \log\det(S^{\eta}_{A})\), we have:
\[I_f(A; Q) = \log\det(S_{A}) -\log\det(S_{A} - \eta^2 S_{A,Q}S_{Q}^{-1}S_{A,Q}^T)\]- Parameters
n (int) – Number of elements in the ground set. Must be > 0.
num_queries (int) – Number of query points in the target.
lambdaVal (float) – Addition to \(s_{ii} (1)\) so that \(\log\) doesn’t become 0
data_sijs (numpy.ndarray, optional) – Similarity kernel between the elements of the ground set. Shape: n X n. When not provided, it is computed using data.
query_sijs (numpy.ndarray, optional) – Similarity kernel between the ground set and the queries. Shape: n X num_queries. When not provided, it is computed using data, queryData and metric.
query_query_sijs (numpy.ndarray, optional) – Similarity kernel between the query points. Shape: num_queries X num_queries. When not provided, it is computed using queryData.
data (numpy.ndarray, optional) – Matrix of shape n X num_features containing the ground set data elements. data[i] should contain the num-features dimensional features of element i. Mandatory if either of data_sijs or query_sijs is not provided. Ignored if both data_sijs and query_sijs are provided.
queryData (numpy.ndarray, optional) – Matrix of shape num_queries X num_features containing the query elements. queryData[i] should contain the num-features dimensional features of query i. It is optional (and is ignored if provided) if query_sijs has been provided.
metric (str, optional) – Similarity metric to be used for computing the similarity kernels. Can be “cosine” for cosine similarity or “euclidean” for similarity based on euclidean distance. Default is “cosine”.
magnificationEta (float, optional) – The value of the query-relevance vs diversity trade-off. Increasing \(\eta\) tends to increase query-relevance while reducing query-coverage and diversity. Default is 1.
- clearMemoization()¶
Clear the computed memoized statistics, if any.
- evaluate(X)¶
Computes the score of a set as per the above math.
- Parameters
X (set) – The set whose score needs to be computed. Must be a subset of effective ground set.
- Returns
The evaluation score of the given set.
- Return type
float
- evaluateWithMemoization(X)¶
Efficiently compute the function evaluation of a set assuming that memoized statistics for it are already computed.
- Parameters
X (set) – The set on which the function needs to be evaluated. It must be a subset of the effective ground set.
- Returns
The function evaluation score on the given set.
- Return type
float
- getEffectiveGroundSet()¶
Get the effective ground set of this object.
- marginalGain(X, element)¶
Computes the marginal gain in score of this function when a single item (element) is added to a set (X).
- Parameters
X (set) – Set on which the marginal gain of adding an element has to be calculated. It must be a subset of the effective ground set.
element (int) – Element for which the marginal gain is to be calculated. It must be from the effective ground set.
- Returns
Marginal gain of adding element to X.
- Return type
float
- marginalGainWithMemoization(X, element)¶
Efficiently find the marginal gain in score when a single item (element) is added to a set (X) assuming that memoized statistics for X are already computed.
- Parameters
X (set) – Set on which the marginal gain of adding an element has to be calculated. It must be a subset of the effective ground set and its memoized statistics should have already been computed.
element (int) – Element for which the marginal gain is to be calculated. It must be from the effective ground set.
- Returns
Marginal gain of adding element to X.
- Return type
float
- maximize(budget, optimizer='NaiveGreedy', stopIfZeroGain=False, stopIfNegativeGain=False, epsilon=0.1, verbose=False, show_progress=True, costs=None, costSensitiveGreedy=False)¶
Compute the optimal subset with maximum score for the given budget.
- Parameters
budget (int) – Desired size of the optimal set.
optimizer (string) – The optimizer that should be used to compute the optimal set. Can be ‘NaiveGreedy’, ‘StochasticGreedy’, LazyGreedy’ and ‘LazierThanLazyGreedy’.
stopIfZeroGain (bool) – Set to True if maximization should terminate as soon as gain of adding any other item becomes zero. When True, size of optimal set can thus be potentially less than the budget.
stopIfNegativeGain (bool) – Set to True if maximization should terminate as soon as the best gain in an iteration is negative. When True, this can potentially lead to optimal set of size less than the budget.
epsilon (float) – Used by Stochastic (Random) Greedy and Lazier Than Lazy Greedy to compute the size of the random set.
verbose (bool) – Set to True to trace/debug the execution of the maximization algorithm.
show_progress (bool) – Set to True to see progress a progress bar.
costs (list, optional) – List containing cost of each element of the ground set. Cost contributes to the budget. When costSensitiveGreedy is set to True, the marginal gain is divided by the cost to identify the next best element to add in every iteration. Default is None which means all ground set elements have cost = 1. It is possible to specify costs and yet have costSensitiveGreedy set to False. This would correspond use regular marginal gains, but the budget gets filled as per the costs of selected items.
costSensitiveGreedy (bool, optional) – When set to True, the next best candidate in every iteration is decided based on their marginal gain divided by cost. When True, it is mandatory to provide costs. Defaults to False.
- Returns
The optimal set of size budget.
- Return type
set
- setMemoization(X)¶
Compute and store the memoized statistics for subset X.
- Parameters
X (set) – The set for which memoized statistics need to be computed and set, overwriting any existing memoized statistics.
- updateMemoization(X, element)¶
Update the memoized statistics of a set X due to adding an element to it. Assumes that memoized statistics are already computed for X. Note that the element is not added to the set and only the memoized statistics are updated. The actual insertion of element to X is the responsibility of the caller.
- Parameters
X (set) – Set whose memoized statistics must already be computed and to which the element needs to be added for the sake of updating the memoized statistics.
element (int) – Element that is being added to X leading to update of memoized statistics. It must be from the effective ground set.