1
$\begingroup$

Suppose I have a set of number $S = \{0,\ldots,n-1\}$. I have to find a partition

$$P = {\arg \max}_{P \in \mathcal{P} \text{ and } P \text{ is a partition}} \operatorname{score}(P)$$

A partition is a set $P$ such that $S = \{i\; | T \in P, i \in T\}$) which gets maximum score.

The score is defined with this table

   0  1     2     3     4     5     6     7
0 [#, 0.55, 0.43, 0.30, 0.28, 0.74, 0.28, 0.26],
1 [   ####, 0.67, 0.40, 0.35, 0.77, 0.30, 0.31],
2 [         ####, 0.29, 0.28, 0.80, 0.21, 0.23],
3 [               ####, 0.39, 0.76, 0.29, 0.29],
4 [                     ####, 0.76, 0.25, 0.29],
5 [                           ####, 0.30, 0.31],
6 [                                 ####, 0.27],
7 [                                       ####]]

as

$$\operatorname{score}(P) := \prod_{\stackrel{i,j \in S^2}{i < j}} (q_{ij} \cdot a_{i,j} + (1-q_{ij}) \cdot (1-a_{i,j}))$$

where $q_{ij} = \begin{cases}1 &\text{if }i \text{ and } j \text{ are in the same set}\\ 0&\text{otherwise}\end{cases}$

For example, the Partition [[0, 1, 2], [3, 4, 5], [6, 7]] has a score of

\begin{align} &(0.55\cdot0.43)\cdot(0.70\cdot0.72\cdot0.26\cdot0.72\cdot0.74)\\ \cdot&(0.67)\cdot(0.60\cdot0.65\cdot0.23\cdot0.70\cdot0.69)\\ \cdot&(0.71\cdot0.72\cdot0.20\cdot0.79\cdot0.77)\\ \cdot&(0.39\cdot0.76)\cdot(0.71\cdot0.71)\\ \cdot&(0.76)\cdot(0.75\cdot0.71)\\ \cdot& (0.70\cdot0.69)\\ \cdot&(0.27) \end{align}

Note that a set with $n$ elements has $2^{n-1}$ partitions. So calculating this score is not possible this way with e.g. $|S|=100$.

How can I calculate this faster?


Note: This is for my website write-math.com. I want to add segmentation, that means I want to make my symbol classifier to become a formula recognizer. To do so, I am thinking about ways to recognize if two strokes belong to the same symbol (or not). The table represents what a classifier returns. Each value is guaranteed to be in [0,1]. For example, $a_{01}=0.55$ means the classifier thinks there is a 55% probability that stroke 0 and stroke 1 belong to the same symbol.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.