Strange error with numpy.ndarray inherited states

[Romain Laby]

Hello guys, 

if this forum is still up, I have a question about an error I got while using hill_climbing problem solver from simpleai.

I try to learn a bayesian network structure, so the states used my implementation of Problem interface are instances of a class BayesNetStruct I've defined, and BayesNetStruct inherites from numpy.ndarray.

while calling hill_climbing, I receive that error :

Traceback (most recent call last):

  File "/usr/anaconda/lib/python2.7/site-packages/IPython/core/interactiveshell.py", line 3035, in run_code

    exec(code_obj, self.user_global_ns, self.user_ns)

  File "<ipython-input-2-1bb833ebede0>", line 27, in <module>

    result = problem.solve_hillclimbing(5)

  File "/var/svn/these-laby/py-script/pgm/my_bayesnet/local_search.py", line 94, in solve_hillclimbing

    return hill_climbing(self, iterations_limit, viewer)

  File "/usr/anaconda/lib/python2.7/site-packages/simpleai/search/local.py", line 90, in hill_climbing

    viewer=viewer)

  File "/usr/anaconda/lib/python2.7/site-packages/simpleai/search/local.py", line 310, in _local_search

    fringe_expander(fringe, iteration, viewer)

  File "/usr/anaconda/lib/python2.7/site-packages/simpleai/search/local.py", line 51, in _first_expander

    fringe.extend(neighbors)

  File "/usr/anaconda/lib/python2.7/site-packages/simpleai/search/utils.py", line 45, in extend

    self.append(x)

  File "/usr/anaconda/lib/python2.7/site-packages/simpleai/search/utils.py", line 38, in append

    self.queue.remove(heapq.nlargest(1, self.queue)[0])

ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

I'm trying to debug that, but I don't find any mistake in my codes.

So my question is if simpleai basically support complex states, like ndarray inherited class ?

Thanks in advance !

[fisa]

Hi!

This sounds strange, I'll debug it later today and let you know what I find, maybe even deploy a hotfix if it's a bug.

--
Has recibido este mensaje porque estás suscrito al grupo "simpleai" de Grupos de Google.
Para anular la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a simpleai+u...@googlegroups.com.
Para acceder a más opciones, visita https://groups.google.com/d/optout.

--

--
fisa  -  Juan Pedro Fisanotti

[fisa]

Hey, I had a very complicated week, sorry for the delay!

Also, the problem isn't so clear as I thought it was. But the good news is that I have some ideas on the possible causes.

Questions:

- are you passing an instance of a class inheriting from Problem to hill_climbing?

- does that class implement the value(self, state) method? what does it returns? it should be a number, and I suspect it's returning something like a numpy array

[Romain Laby]

Hey Juan, 

thanks for your answer ! 

- are you passing an instance of a class inheriting from Problem to hill_climbing?

Yes, in fact it's an instance of SearchProblem, as I've seen in the doc in the HelloWorld example.

 - does that class implement the value(self, state) method? what does it returns? it should be a number, and I suspect it's returning something like a numpy array

also yes, I've checked that the method is returning a float, i aactually reimplaced it by a random number generator to better isolate the error. Still there !

Maybe I can give you some piece of my code to better inverstigate.

I've reimplace my class by a simple string, and the error vanishes, so it's linked with my state class definition.

Here is the Problem definition (sorry for french comments !):

from itertools import combinations
from simpleai.search import SearchProblem
from simpleai.search.local import hill_climbing
# from pgm.my_bayesnet.scores import bic_score


class LocalSearch(SearchProblem):

    def __init__(self, data, *args, **kwargs):
        """
        seules les données sont nécessaires, afin de pouvoir scorer
        en respectant l'interface
        """
        super(LocalSearch, self).__init__(*args, **kwargs)
        self.data = data

    def actions(self, state):
        """
        les actions possibles sont l'ajout, la suppression ou le retournement
        d'un arc. La vérification que l'ajout ou le retournement d'arcs ne
        crée pas de cycle n'est pas fait ici, mais dans le result.

        une action est un triplet de variables (ix_a, ix_b, act), avec
        act = "add", "del", "rev" indiquant l'un des 3 moficications
        possible pour l'arc (a,b)
        """
        acts = []
        for i, j in combinations(range(state.shape[0]), 2):
            if state[i, j] == 0:
                acts.append((i, j, "add"))
                acts.append((j, i, "add"))
            else:
                acts.append((i, j, "del"))
                acts.append((i, j, "rev"))
        return acts

    def result(self, state, action):
        """
        retourne un nouvel état en appliquant l'action considérée
        """
        ni, nj, val = action
        try:
            if val == "add":
                return state.add_edge(ni, nj, on_copy=True)
            elif val == "del":
                return state.delete_edge(ni, nj, on_copy=True)
            else:
                return state.reverse_edge(ni, nj, on_copy=True)
        except AttributeError:
            return None

    def value(self, state):
        """
        Renvoie le score bic de la solution courante.
        Un socre élevé est meilleur.
        Si la solution a un cycle, on renvoie -infini. Ca ne risque pas de
        fausser l'algorithme (par exemple, si tous les candidats on un cycle),
        puisque la solution actuelle est correcte et ne présente pas de cycle.
        """
        import numpy as np
        return np.random.rand()
        # if state is None:
        #     return -float("inf")
        # if state.is_acyclic():
        #     return bic_score(state, self.data)
        # return -float("inf")

    def solve_hillclimbing(self, iterations_limit=0, viewer=None):
        """
        résolution du problème
        """
        return hill_climbing(self, iterations_limit, viewer)

 and the state class definition (its a directed graph structure, so a simple numpy.array adjacency matrix with some methods and attribute, like edge addition etc):

import numpy as np

class AdjacencyBayesStruct(np.ndarray):

    def __new__(cls, a, dtype=int, n_values=None):
        obj = np.asarray(a, dtype).view(cls)
        obj.n_values = n_values
        obj.topological_order = None
        return obj

    def __array_finalize__(self, obj):
        if obj is None:
            return
        self.n_values = getattr(obj, 'n_values', None)
        if self.n_values is None:
            self.n_values = 2 * np.ones(self.shape[0])
        self.topological_order = None

    def __copy__(self):
        return AdjacencyBayesStruct(self.copy(), dtype=self.dtype,
                                    n_values=self.n_values)

    def add_node(self, n_values):
        """
        <private> ajout d'un noeud à la structure
        """
        copy = self.__copy__()
        copy.reshape((self.shape[0] + 1, self.shape[1] + 1))
        copy[-1, :] = 0
        copy[:, -1] = 0
        copy.n_values = np.r_[self.n_values, n_values]
        return copy

    def remove_node(self, ix_node):
        """
        supprime un noeud, retourne une copie
        """
        copy = np.delete(self, ix_node, 0)
        copy = np.delete(copy, ix_node, 1)
        new_values = np.delete(self.values, ix_node)
        return AdjacencyBayesStruct(copy, n_values=new_values)

    def add_edge(self, ix_child, ix_parent, on_copy=True):
        """
        ajoute un arc entre child et parent
        """
        if ix_parent == ix_child:
            raise ValueError("add edge with parent=child")
        if on_copy:
            copy = self.__copy__()
            copy[ix_parent, ix_child] = 1
            copy[ix_child, ix_parent] = -1
            copy._build_topo_order()
            if not copy.is_acyclic():
                raise CyclicGraphException()
            return copy
        self[ix_parent, ix_child] = 1
        self[ix_child, ix_parent] = -1
        self._build_topo_order()
        if not self.is_acyclic():
            self[ix_parent, ix_child] = 0
            self[ix_child, ix_parent] = 0
            self._build_topo_order()
            raise CyclicGraphException()
        return self

    def remove_edge(self, ix_child, ix_parent, on_copy=True):
        """
        enlève un arc entre child et parent
        """
        if ix_parent == ix_child:
            raise ValueError("remove edge with parent=child")
        if on_copy:
            copy = self.__copy__()
            copy[ix_child, ix_parent] = 0
            copy[ix_parent, ix_child] = 0
            return copy
        self[ix_child, ix_parent] = 0
        self[ix_parent, ix_child] = 0
        return self

    def reverse_edge(self, ix_child, ix_parent, on_copy=True):
        """
        renverse un arc entre
        """
        if ix_parent == ix_child:
            raise ValueError("reverse edge with parent=child")
        if on_copy:
            copy = self.__copy__()
            copy[ix_child, ix_parent] = 1
            copy[ix_parent, ix_child] = -1
            copy._build_topo_order()
            if not copy.is_acyclic():
                raise CyclicGraphException()
            return copy
        self[ix_child, ix_parent] = 1
        self[ix_parent, ix_child] = -1
        self._build_topo_order()
        if not self.is_acyclic():
            self[ix_child, ix_parent] = 1
            self[ix_parent, ix_child] = -1
            self._build_topo_order()
            raise CyclicGraphException()
        return self

    def is_acyclic(self):
        """
        check if self est acyclic ou pas,
        il y a un cycle s'il n'est pas possible de trouver un order
        """
        if self.topological_order is None:
            self._build_topo_order()
        return len(self.topological_order) > 0

    def _build_topo_order(self):
        """
        Tentative de construction d'un ordonancement topologique
        """
        topo = []
        isnotchilds = [ix_node for ix_node in xrange(self.shape[0])
                      if -1 not in self[ix_node, :]]
        copy = self.__copy__()
        while isnotchilds:
            topo.append(isnotchilds.pop())
            for m in [ix for ix in xrange(copy.shape[0])
                      if copy[topo[-1], ix] == 1]:
                copy.remove_edge(m, topo[-1], False)
                if -1 not in copy[m, :]:
                    isnotchilds.append(m)
        if np.sum(np.abs(copy)) == 0:
            self.topological_order = np.array(topo)
        else:
            self.topological_order = []

class CyclicGraphException(Exception):
    pass

finally, the lauch script, based on the classic Student Example:

import pandas as pd
import numpy as np

# génération de data, façon lourdingue
size = 1000
df = pd.DataFrame({"Difficulty": np.random.choice([0, 1], size=size,
                                                  p=[.6, .4]),
                   "Intelligence": np.random.choice([0, 1], size=size,
                                                    p=[.7, .3])})
sat = {0: [.95, .05], 1: [.2, .8]}
df["SAT"] = df.apply(lambda ctx: np.random.choice(
    [0, 1], p=sat[ctx["Intelligence"]]), axis=1)
grade = {(0, 0): [.3, .4, .3], (1, 0): [.05, .25, .7],
         (0, 1): [.9, .08, .02], (1, 1): [.5, .3, .2]}
df["grade"] = df.apply(lambda ctx: np.random.choice(
    [0, 1, 2], p=grade[(ctx["Difficulty"], ctx["Intelligence"])]), axis=1)
letter = {0: [.1, .9], 1: [.4, .6], 2: [.99, .01]}
df["letter"] = df.apply(
    lambda ctx: np.random.choice([0, 1], p=letter[ctx["grade"]]), axis=1)


bn0 = AdjacencyBayesStruct(np.zeros((5, 5)), n_values=[2, 2, 2, 3, 2])
problem = LocalSearch(initial_state=bn0, data=df)
result = problem.solve_hillclimbing(5)

these lines are reproducing the error. Tell me if it shed more light on the error...

Thanks for your help and time !

Best,

Romain

[fisa]

No problem with the french comments! :) And sorry if my english isn't very good, I'm not a native english speaker either, hehe.

I identified the cause of the problem.

During the search process, in different places simpleai needs to compare equality of problem states. This is done with a simple state_x == state_y operation.

In the hill climbing case, this happens while using a bounded queue. I know that a queue sounds "overkill" for hill climbing, but this algorithm is just a special case of a more general algorithm, which allows you to have more than 1 state at each given time. That's why we need a bounded queue, instead of a single variable. At each iteration of hill climbing, the old node will be removed from the queue, replaced by the new one.

When removing nodes from that queue the mentioned equality comparison takes place: call to list.remove(a node instance), which triggers a call to the __eq__ of the node, where the states are compared.

Your state is an instance of something that doesn't allow to be compared using ==. Hence the problem while trying to execute the second iteration in hill climbing.

I'm trying to find a way of doing that without triggering a call to node.__eq__, but wasn't lucky with that so far.

In the meantime, does it sound logical to you to require the state to be comparable using ==? Does it make sense? Is it doable?

[fisa]

Update: there is a way to fix the issue from the simpleai side, but I'm not sure on the performance implications of the fix. So the questions of the last mail are still valid :)

[Romain Laby]

Hi Juan,

yes its pretty easy to override the __eq__ method. I've just done it, the error is gone ! Before the overriding, the __eq__ method from super class was checking equality component by component, and was returning a boolean matrix instead of a single boolean. I wasn't enough carefull, I should have made the override sooner, my bad ^^
I'll make the correction in my original code and let you know if it works.

...

[fisa]

No problem! Glad you have a solution then, and it's good to know this "requirement" exists, for future cases.

--

Has recibido este mensaje porque estás suscrito al grupo "simpleai" de Grupos de Google.
Para anular la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a simpleai+u...@googlegroups.com.
Para acceder a más opciones, visita https://groups.google.com/d/optout.

[andrew schell]

HI Roman,

     Was this issue resolved or can you give an update?

[andrew schell]

I am new to the Group and I'm a few months into assembling the Norvig/Russel Ai with a more agents that include Cognition and short term memory.

Have a great day.

On Tuesday, March 8, 2016 at 7:48:23 AM UTC-8, Romain Laby wrote: