Suppose we have a sequence of $m$ tokens $(T_1, T_2, \ldots, T_m)$. We can split this sequence considering two parameters $w$ (which is the width of the window) and $x$ which is the overlap between windows. This is depicted in the following figure:

Token sequence and split

Now, suppose we have the function $f$ which takes as input a window and maps it into an $\mathbb{R}^N$ vector space:

enter image description here

This procedure is performed for all windows of a given sequence, based on parameters $w$ and $x$. In the end, I will have a cluster of points with a centroid:


Suppose that I want to find the windows that best represents the main structure of the original sequence (based on the mapping of the function $f$), then this can be thought as an optimization problem such that getting the minimum average distance between points and the centroid (I will omit the constant $\frac{1}{n}$)

$$\text{Minimize } J(w, x) = \displaystyle \sum_{k=1}^{n} \|v - x_k\| $$

$v$ is the centroid computed from the $n$ vectors obtained previously. The problem is that $n$ depends on $w$ and $x$

Subject to:

$$0 < w < |T|$$ $$w > x$$

$f$ could be any function, but in my case the $f$ I am using has the following properties:

  • If we have window $S_1$ and a window $S_2$ such that $|S_1| \lt |S_2|$, then $\|f(S_1)\|_2 < \|f(S_2)\|_2$
  • All components of the vectors resulting from $f(S)$ are greater or equal than zero.

I would like to find $w_{opt}$ and $x_{opt}$.

  • In summary, the input is the sequence $T$
  • Based on parameters $w$, $x$ and a mapping function $f$ we create a cluster of points.
  • I'd like to find $w_{opt}$ and $x_{opt}$ for a given $f$ such that $J(w, x) = \displaystyle \sum_{k=1}^{n} \|v - x_k\|$ is minimum.

I already tried to do this with a brute force approach but it is infeasible with the sizes I am getting for the main sequence (around 300-800 tokens)

  • $\begingroup$ Wouldn't the time complexity of the brute force algorithm be $|T|^3 \cdot N$? why it is infeasible? $\endgroup$ Commented Dec 28, 2021 at 6:12
  • $\begingroup$ The problem the combinatorics of $w$ and $x$. If I had each time I try an $x$ and $w$ pair, I have to do all the computations. Could you elaborate a little bit more on how would this be polynomial in time? $\endgroup$
    – dpalma
    Commented Dec 28, 2021 at 6:29
  • 1
    $\begingroup$ well, without doing anything fancy there is a $O(|T|^2 \cdot t(f) + |T|^2 N \log |T|)$ time algorithm, where $t(f)$ is time for computing $f(S)$. For $|T| = 800$, it should be good enough, given $N$ is not very large. It would be great if you could mention in the question, the time complexity of the algorithm that you have in mind. Please also state the value of $N$. $\endgroup$ Commented Dec 28, 2021 at 16:32
  • 1
    $\begingroup$ Your conditions basically don't restrict $f$ very much at all, so $f$ could be more or less arbitrary. Thus I suspect it is likely that Inuyasha Yagami's algorithm is going to be optimal, in the absence of further structure in $f$. $\endgroup$
    – D.W.
    Commented Dec 28, 2021 at 21:18
  • 1
    $\begingroup$ @InuyashaYagami In the end you were right, I had a bug on my brute force approach, in fact the brute force algorithm with $O(|T|^3\cdot N)$ will suffice for the search space I am aiming for, I think we can mark this as resolved. I would be interested in a more efficient approach though :) $\endgroup$
    – dpalma
    Commented Dec 29, 2021 at 1:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.