Package weka.classifiers.lazy.AM.lattice

Class JohnsenJohanssonLattice

  • All Implemented Interfaces:
    Lattice
    public class JohnsenJohanssonLattice
extends java.lang.Object
implements Lattice
    The approximation algorithm from "Efficient Modeling of Analogy", Johnsen and Johansson, DOI 10.1007/978-3-540-30586-6_77. Terminology from the paper is as follows:
    • $p$: the subcontext whose count is being approximated
    • $size(p)$: the size of the subcontext $p$; or, the number of 0's in its label
    • $\mathcal{H}(p)$: the sets found by intersecting $p$ with any subcontext that has a different outcome; the labels of such intersections
    • $max(p)$: the cardinality of the union of all $x\in\mathcal{H}(p)$; the number of 0's in the union of the labels of all subcontexts in $\mathcal{H}(p)$
    • $\mathcal{H}_{limit(p)}$: the heterogeneous elements under $p$ in the lattice
    • $min(p)$: the size of the largest child of $p$; or, the number of 0's in the label of the subcontext whose label has the most 0's and matches all of the 1's in $p$'s label.
    We estimate the count of each subcontext by randomly unioning sets of subcontexts from $\{x_s\}$ and checking for heterogeneity (union means OR'ing labels). The count of a subcontext $p$ is the size of its power set minus the heterogeneous elements in this set (or $|\wp(p)| - |\mathcal{H}_{limit(p)}|$). We use these bounds in approximating $|\mathcal{H}_{limit(p)}|$:
    • lower bound ($lb(p)$): the cardinality of the powerset of $min(p)$.
    • upper bound ($ub(p)$): $\sum_{k=1}^{min(p)}{max(p)\choose k}$
    The estimate $\hat{h}_p$ of $|\mathcal{H}_{limit(p)}|$ is computed by sampling random sets of subcontexts ${x_s}$ and combining them with : $\frac{|\{x_s \in \mathcal{H}(p)|}{|\{x_s\}|}=\frac{\hat{h}_p}{ub(p)}$ or $\hat{h}_p = \frac{ub(p)|x_s\in \mathcal{H}(p)|}{|\{x_s\}|}$
    TODO: maybe if H(p) is small enough we could do exact counting with include-exclude

    • Method Detail

      • fill

        public void fill​(SubcontextList sublist)
          throws java.lang.InterruptedException,
                 java.util.concurrent.ExecutionException
        Description copied from interface: Lattice
        Fill the lattice with given subcontexts. This is meant to be done only once for a given Lattice instance.
        Specified by:
        fill in interface Lattice
        Throws:
        java.lang.InterruptedException
        java.util.concurrent.ExecutionException

      • getSupracontexts

        public java.util.Set<Supracontext> getSupracontexts()
        Specified by:
        getSupracontexts in interface Lattice
        Returns:
        The list of supracontexts that were created by filling the supracontextual lattice. From this, you can compute the analogical set.