ForbiddenAndConjunction-related issue

[ixeixe]

Hello ConfigSpace package developers.
I'm having a problem with ForbiddenInClause and ForbiddenAndConjunction.
Here is an example:

import numpy as np
from openbox import space as sp
from ConfigSpace import ConfigurationSpace, Categorical, Float, Integer,Constant
from ConfigSpace import ForbiddenAndConjunction, ForbiddenEqualsClause, ForbiddenInClause

space = sp.Space()

lp2=Categorical('lp2', [1, 2, 8, 64])
A=Categorical('A', [1, 2, 8])
x=Categorical('x', [1, 2, 8])
tmp=Categorical('tmp', [1, 2, 8])
#I hope that
#When lp2=1, A and tmp cannot be in [1,2], and x cannot be in [1,2]
#When lp2=2, A and tmp cannot be in [1,8], and x cannot be in [1,8]
#When lp2=8, A and tmp cannot be in [1,2], and x cannot be in [1,2]
#When lp2=64, A and tmp cannot be in [1,2], and x cannot be in [1,2]
F1=ForbiddenAndConjunction(
    ForbiddenInClause(lp2,[1]),
    ForbiddenInClause(A,[2,8]),
    ForbiddenInClause(tmp,[2,8]),
    ForbiddenInClause(x,[2,8]))
F2=ForbiddenAndConjunction(
    ForbiddenInClause(lp2,[2]),
    ForbiddenInClause(A,[1,8]),
    ForbiddenInClause(tmp,[1,8]),
    ForbiddenInClause(x,[1,8]))
F3=ForbiddenAndConjunction(
    ForbiddenInClause(lp2,[8,64]),
    ForbiddenInClause(A,[1,2]),
    ForbiddenInClause(tmp,[1,2]),
    ForbiddenInClause(x,[1,2]))

F=[F1,F2,F3]
names = [lp2,A ,x ,tmp]
space.add_variables(names)
space.add(F)
space.sample_configuration(1)

The output is:

Configuration space object:
  Hyperparameters:
    A, Type: Categorical, Choices: {1, 2, 8}, Default: 1
    lp2, Type: Categorical, Choices: {1, 2, 8, 64}, Default: 1
    tmp, Type: Categorical, Choices: {1, 2, 8}, Default: 1
    x, Type: Categorical, Choices: {1, 2, 8}, Default: 1
  Forbidden Clauses:
    (Forbidden: lp2 in {1} && Forbidden: A in {2, 8} && Forbidden: tmp in {2, 8} && Forbidden: x in {2, 8})
    (Forbidden: lp2 in {2} && Forbidden: A in {1, 8} && Forbidden: tmp in {1, 8} && Forbidden: x in {1, 8})
    (Forbidden: lp2 in {8, 64} && Forbidden: A in {1, 2} && Forbidden: tmp in {1, 2} && Forbidden: x in {1, 2})

The result of sample space.sample_configuration (1) is:

 Configuration(values={
   'A': 2,
   'lp2': 2,
   'tmp': 8,
   'x': 8,
 })

But this does not conform to the forbidden clause F2.

F2=ForbiddenAndConjunction(
    ForbiddenInClause(lp2,[2]),
    ForbiddenInClause(A,[1,8]),
    ForbiddenInClause(tmp,[1,8]),
    ForbiddenInClause(x,[1,8]))

When lp2= 2, x should not be equal to 8, and y should not be equal to 8.
According to the Boolean calculation of your source code, the sampling configuration must trigger 4 clauses of F2 at the same time to achieve the effect I want, if only 3 clauses of F2 and less are triggered at the same time, it will also be successfully sampled, and the effect I want will not be achieved. Please how can I modify it to achieve 【When lp2=2, A and tmp cannot be in [1,8], and x cannot be in [1,8]】？
I look forward to your answers and thank you for your help!

[eddiebergman]

Hi @ixeixe,

This is likely an oversight on my part. We did some optimization work to ensure that we minimize the amount of forbiddens that need to be checked and my guess is that this is what causes the behaviour. I will try to look at it in the coming week but unfortunatly I am at an event and may not get time until the following week.

For reference, this is what is actually used during forbidden checks:

• space._dag.fast_forbidden_checks:

  ConfigSpace/src/ConfigSpace/_condition_tree.py

  Lines 361 to 393 in d5b82ae

  	# OPTIM: Mainly used for generating neighbors, do not use if validation
  	# the underlying forbidden is required to be displayed to the user
  	fast_forbidden_checks: list[ForbiddenLike] = field(
  	default_factory=list,
  	compare=False,
  	)
  	""" Many time, forbiddens are an AND conjunction of multiple
  	clauses, where the clauses are all on the same hyperparameters.
  	```
  	(classifier== 'adaboost' && preprocessor== 'densifier'),
  	(classifier== 'adaboost' && preprocessor== 'kitchen_sinks'),
  	(classifier== 'adaboost' && preprocessor == 'nystroem_sampler')
  	```
  	When performing operations of forbiddens, only a single array at a time,
  	the **slowest part is actually indexing into a numpy array like[so_idx]**,
  	even if just retrieving one index.
  	* Ref: https://stackoverflow.com/a/29311751/5332072
  	We can't get around indexing so the next best attempt is to reduce the amount
  	indexing required.
  	```
  	(classifier== 'adaboost'
  	&& preprocessor in ('nystroem_sampler', 'kitchen_sinks', 'densifier'))
  	```
  	We can't perfectly capture all possible forbidden clauses in this way, but
  	we make the assumption that shared forbiddens are more likely to occur on
  	_more shallow_ nodes, i.e. hp nodes that come before.
  	"""

You could print these out to see where the inconsisteny lies which would help in finding out the logical error I made.

For reference, this is the logic that takes a list of forbiddens and returns an optimized list of forbiddens.

ConfigSpace/src/ConfigSpace/_condition_tree.py

Lines 821 to 876 in d5b82ae

	def _optimized_forbiddens(
	self,
	forbiddens: list[ForbiddenLike],
	) -> list[ForbiddenLike]:
	# Please see .fast_forbidden_checks for more information
	to_optimize: dict[
	# First parent_name, with N-1 (hp_name, value)...
	tuple[str, tuple[tuple[str, f64], ...]],
	# unique parts of AND, list to for isin
	tuple[tuple[ForbiddenEqualsClause, ...], list[ForbiddenEqualsClause]],
	] = {}
	forbiddens_to_return: list[ForbiddenLike] = []
	and_conjunction_parts: list[list[ForbiddenEqualsClause]] = []
	for f in forbiddens:
	if isinstance(f, ForbiddenAndConjunction) and all(
	isinstance(c, ForbiddenEqualsClause) for c in f.components
	):
	and_conjunction_parts.append(
	sorted(
	f.components, # type: ignore
	key=lambda _x: self.index_of[_x.hyperparameter.name], # type: ignore
	),
	)
	else:
	forbiddens_to_return.append(f)
	for *firsts, last in and_conjunction_parts:
	shallowest_key = tuple(
	(x.hyperparameter.name, x.vector_value) for x in firsts
	)
	parent_key = last.hyperparameter.name
	joint_key = (parent_key, shallowest_key)
	if joint_key in to_optimize:
	_, conjunctions = to_optimize[joint_key]
	conjunctions.append(last)
	else:
	to_optimize[joint_key] = (tuple(firsts), [last])
	for _and_parts, equal_components in to_optimize.values():
	# Didn't share first parts such that we could group it with anything else
	if len(equal_components) == 1:
	conj = ForbiddenAndConjunction(*_and_parts, equal_components[0])
	conj.set_vector_idx(self.index_of)
	forbiddens_to_return.append(conj)
	continue
	isin_clause = ForbiddenInClause(
	equal_components[0].hyperparameter,
	[x.value for x in equal_components],
	)
	conj = ForbiddenAndConjunction(*_and_parts, isin_clause)
	conj.set_vector_idx(self.index_of)
	forbiddens_to_return.append(conj)
	return forbiddens_to_return

[ixeixe]

Thank you for taking the time out of your busy schedule to get back to me, you mentioned that I can print space._dag.fast_forbidden_checks, the result of which is:

[(Forbidden: lp2 in {1} && Forbidden: A in {2, 8} && Forbidden: tmp in {2, 8} && Forbidden: x in {2, 8}),
 (Forbidden: lp2 in {2} && Forbidden: A in {1, 8} && Forbidden: tmp in {1, 8} && Forbidden: x in {1, 8}),
 (Forbidden: lp2 in {8, 64} && Forbidden: A in {1, 2} && Forbidden: tmp in {1, 2} && Forbidden: x in {1, 2})]

In line 2, the Forbidden I want to be effective is：
prohibit [lp2=2 and (A=1 or A=8) and (tmp=1 or tmp=8) and (x=1 or x=8)]
The negation is denoted as
[lp2≠2 or (A≠1 and A≠8) or (tmp≠1 and tmp≠8) or (x≠1 and x≠8)]
I hope that only [lp2=2 and A=2 and tmp=2 and x=2] can appear.
I don’t understand the logic of your source code for the time being, I’m sorry, but I still looking forward to your reply at your convenience, thank you!

[eddiebergman]

No worries, the code is hard to make understandable and it's really just an efficiency thing done under the hood. The extra info you gave will be super helpful! I will take a look at this next week once I am back! Apologies for the inconvenience