Argumentation graduée — sémantiques de classement (h-Categoriser & fardeau)

Dans le notebook compagnon Argument_Analysis_Dung_AF_Semantics, les sémantiques de Dung (fondée, préférée, stable) répondent par oui ou non : un argument est dans une extension, ou il n’y est pas. C’est une vision tout-ou-rien de l’acceptabilité.

Les sémantiques de classement (ranking-based / gradual semantics) répondent à une question plus fine : « à quel point » cet argument est-il acceptable ? Elles attribuent à chaque argument une force numérique et en déduisent un ordre. Deux arguments tous deux « rejetés » au sens de Dung peuvent ainsi être départagés : celui qui subit trois attaques est plus faible que celui qui n’en subit qu’une.

Ce notebook présente deux méthodes déterministes, calculables à la main :

Méthode Principe Référence
h-Categoriser point fixe \(\mathrm{Cat}(a) = \dfrac{1}{1 + \sum_{b \to a} \mathrm{Cat}(b)}\) Besnard & Hunter 2001 ; convergence : Pu et al. 2014
Fardeau (burden-based) suite \(\mathrm{Bur}^{i}(a) = 1 + \sum_{b \to a} \tfrac{1}{\mathrm{Bur}^{i-1}(b)}\), comparée lexicographiquement Amgoud & Ben-Naim 2013

Tout est en Python standard (pas de dépendance) : les calculs sont reproductibles et déterministes.

1. Le cadre d’argumentation (rappel)

On réutilise exactement la structure AF \(\langle \text{args}, \text{attacks}\rangle\) du notebook Dung : un ensemble d’arguments et un ensemble d’attaques (couples attaquant → attaqué).

from itertools import combinations


class AF:
    """Cadre d'argumentation abstrait de Dung : <args, attacks>."""

    def __init__(self, args, attacks):
        self.args = set(args)
        self.attacks = set(attacks)  # ensemble de couples (attaquant, attaque)

    def attackers(self, x):
        """Arguments qui attaquent directement x."""
        return {a for (a, b) in self.attacks if b == x}

    def __repr__(self):
        att = ", ".join(f"{a}->{b}" for (a, b) in sorted(self.attacks))
        return f"AF(args={sorted(self.args)}, attacks=[{att}])"


# Exemple fil rouge : e n'est pas attaque, a subit 1 attaque, b en subit 3.
af = AF(
    args={"e", "a", "b", "y", "z1", "z2", "z3"},
    attacks={("y", "a"), ("z1", "b"), ("z2", "b"), ("z3", "b")},
)
print(af)
for x in ["e", "a", "b"]:
    print(f"  attaquants de {x} : {sorted(af.attackers(x)) or 'aucun'}")
AF(args=['a', 'b', 'e', 'y', 'z1', 'z2', 'z3'], attacks=[y->a, z1->b, z2->b, z3->b])
  attaquants de e : aucun
  attaquants de a : ['y']
  attaquants de b : ['z1', 'z2', 'z3']

2. h-Categoriser : un point fixe d’acceptabilité

L’idée de Besnard & Hunter (2001) : la force d’un argument décroît avec la force cumulée de ses attaquants. Formellement, on cherche un vecteur \(\mathrm{Cat} : \text{args} \to (0, 1]\) tel que

\[\mathrm{Cat}(a) \;=\; \frac{1}{1 + \displaystyle\sum_{b \,\to\, a} \mathrm{Cat}(b)}.\]

  • Un argument non attaqué a une force de \(1\) (somme vide au dénominateur).
  • Plus ses attaquants sont nombreux ou forts, plus sa force baisse vers \(0\).

On calcule ce point fixe par itération à partir de \(\mathrm{Cat}^{(0)} \equiv 1\). Pu et al. (2014) ont prouvé que cette itération converge sur tout AF fini (même cyclique).

def h_categoriser(af, tol=1e-12, max_iter=10_000):
    """Calcule le classement h-Categoriser par iteration de point fixe.

    Renvoie (cat, n_iter) ou cat[a] in (0, 1] est la force de a (plus grand = plus fort).
    """
    cat = {a: 1.0 for a in af.args}
    for it in range(1, max_iter + 1):
        nxt = {a: 1.0 / (1.0 + sum(cat[b] for b in af.attackers(a))) for a in af.args}
        delta = max((abs(nxt[a] - cat[a]) for a in af.args), default=0.0)
        cat = nxt
        if delta < tol:
            return cat, it
    return cat, max_iter


cat, n_iter = h_categoriser(af)
print(f"Convergence en {n_iter} iterations.\n")
for a in sorted(af.args, key=lambda a: cat[a], reverse=True):
    print(f"  Cat({a}) = {cat[a]:.4f}")
Convergence en 2 iterations.

  Cat(y) = 1.0000
  Cat(z3) = 1.0000
  Cat(z1) = 1.0000
  Cat(e) = 1.0000
  Cat(z2) = 1.0000
  Cat(a) = 0.5000
  Cat(b) = 0.2500

Lecture du classement

Le classement induit (force décroissante) départe finement les arguments :

  • les non attaqués (e, y, z1, z2, z3) sont au sommet à \(1{,}0\) ;
  • a, attaqué une seule fois par y (de force \(1\)), vaut \(\tfrac{1}{1+1} = 0{,}5\) ;
  • b, attaqué trois fois, vaut \(\tfrac{1}{1+3} = 0{,}25\).

Donc a est strictement mieux classé que b.

3. Contraste avec la sémantique fondée de Dung

Calculons la sémantique fondée (grounded) sur le même AF — le plus petit point fixe de la fonction caractéristique \(F(S) = \{a \mid S \text{ défend } a\}\) (rappel du notebook compagnon).

def grounded_extension(af):
    """Plus petit point fixe de la fonction caracteristique (semantique fondee de Dung)."""
    def defends(S, x):
        return all(any((c, b) in af.attacks for c in S) for b in af.attackers(x))

    S = set()
    while True:
        nxt = {a for a in af.args if defends(S, a)}
        if nxt == S:
            return S
        S = nxt


g = grounded_extension(af)
print("Extension fondee :", sorted(g))
print()
# Statut Dung : IN si dans l'extension, OUT si attaque par l'extension, sinon UNDEC.
def dung_status(af, g, x):
    if x in g:
        return "IN"
    if any((c, x) in af.attacks for c in g):
        return "OUT"
    return "UNDEC"

for x in ["a", "b"]:
    print(f"  {x} : statut Dung = {dung_status(af, g, x)}  |  force h-Cat = {cat[x]:.4f}")
Extension fondee : ['e', 'y', 'z1', 'z2', 'z3']

  a : statut Dung = OUT  |  force h-Cat = 0.5000
  b : statut Dung = OUT  |  force h-Cat = 0.2500

Le verdict

a et b ont le même statut dans la sémantique fondée : tous deux OUT (rejetés, car attaqués par des arguments acceptés). Dung ne les distingue pas.

La sémantique de classement, elle, les départage : a (\(0{,}5\)) \(\succ\) b (\(0{,}25\)). C’est précisément la valeur ajoutée des sémantiques graduées — une granularité que le tout-ou-rien ne capture pas.

# Verification programmatique du contraste.
print("Meme statut Dung (a, b tous deux OUT) ?",
      dung_status(af, g, "a") == dung_status(af, g, "b") == "OUT")
print("h-Categoriser les departe (Cat(a) > Cat(b)) ?", cat["a"] > cat["b"])
Meme statut Dung (a, b tous deux OUT) ? True
h-Categoriser les departe (Cat(a) > Cat(b)) ? True

4. Sémantique du fardeau (burden-based)

Amgoud & Ben-Naim (2013) proposent une autre construction. On définit une suite de nombres de fardeau, à partir de \(\mathrm{Bur}^{0}(a) = 1\) :

\[\mathrm{Bur}^{i}(a) \;=\; 1 + \sum_{b \,\to\, a} \frac{1}{\mathrm{Bur}^{i-1}(b)}.\]

Un fardeau plus faible signifie un argument plus fort. Le classement compare les vecteurs \(\big(\mathrm{Bur}^{1}(a), \mathrm{Bur}^{2}(a), \dots\big)\) de façon lexicographique (le premier pas qui les départage tranche).

def burden_numbers(af, steps=8):
    """Renvoie {a: (Bur^1, ..., Bur^steps)} (Bur^0 = 1 pour tous)."""
    bur = {a: 1.0 for a in af.args}
    seq = {a: [] for a in af.args}
    for _ in range(steps):
        nxt = {a: 1.0 + sum(1.0 / bur[b] for b in af.attackers(a)) for a in af.args}
        for a in af.args:
            seq[a].append(nxt[a])
        bur = nxt
    return {a: tuple(seq[a]) for a in af.args}


def burden_rank(af, steps=8):
    """Classement par fardeau : fardeau lexicographiquement plus petit = plus fort."""
    bn = burden_numbers(af, steps)
    return sorted(af.args, key=lambda a: bn[a]), bn


order, bn = burden_rank(af)
print("Classement par fardeau (du plus fort au plus faible) :")
for rank, a in enumerate(order, 1):
    print(f"  {rank}. {a:3} -> Bur^1..3 = ({bn[a][0]:.3f}, {bn[a][1]:.3f}, {bn[a][2]:.3f})")
Classement par fardeau (du plus fort au plus faible) :
  1. y   -> Bur^1..3 = (1.000, 1.000, 1.000)
  2. z3  -> Bur^1..3 = (1.000, 1.000, 1.000)
  3. z1  -> Bur^1..3 = (1.000, 1.000, 1.000)
  4. e   -> Bur^1..3 = (1.000, 1.000, 1.000)
  5. z2  -> Bur^1..3 = (1.000, 1.000, 1.000)
  6. a   -> Bur^1..3 = (2.000, 2.000, 2.000)
  7. b   -> Bur^1..3 = (4.000, 4.000, 4.000)

Accord des deux méthodes

Sur cet AF, fardeau et h-Categoriser s’accordent sur l’essentiel : a reste mieux classé que b, et les non-attaqués dominent. Les deux familles satisfont des principes communs (Amgoud & Ben-Naim) :

  • Abstraction : le classement ne dépend que de la structure du graphe (renommer les arguments ne change rien).
  • Indépendance : des composantes non connectées du graphe n’interfèrent pas.
  • Contre-transitivité : plus d’attaquants (ou des attaquants plus forts) ⇒ plus faible.
# Les deux methodes s'accordent sur a > b.
hcat_order = sorted(af.args, key=lambda a: cat[a], reverse=True)
print("h-Cat : a avant b ?", hcat_order.index("a") < hcat_order.index("b"))
print("Fardeau : a avant b ?", order.index("a") < order.index("b"))
h-Cat : a avant b ? True
Fardeau : a avant b ? True

5. Le cas cyclique : convergence garantie

Sur un cycle \(a \leftrightarrow b\), le tout-ou-rien de Dung laisse les deux arguments indécidés (UNDEC). h-Categoriser, lui, converge vers une valeur finie identique pour les deux, solution de \(x = \tfrac{1}{1+x}\), soit le nombre d’or inverse \(\tfrac{\sqrt{5}-1}{2} \approx 0{,}618\).

af_cycle = AF({"a", "b"}, {("a", "b"), ("b", "a")})
cat_cyc, it_cyc = h_categoriser(af_cycle)
phi_inv = (5 ** 0.5 - 1) / 2
print(f"AF cyclique a<->b : convergence en {it_cyc} iterations.")
print(f"  Cat(a) = {cat_cyc['a']:.6f}, Cat(b) = {cat_cyc['b']:.6f}")
print(f"  Valeur theorique (sqrt(5)-1)/2 = {phi_inv:.6f}")
print("  Statut Dung (fonde) des deux : UNDEC (extension fondee =",
      sorted(grounded_extension(af_cycle)) or "vide", ")")
AF cyclique a<->b : convergence en 29 iterations.
  Cat(a) = 0.618034, Cat(b) = 0.618034
  Valeur theorique (sqrt(5)-1)/2 = 0.618034
  Statut Dung (fonde) des deux : UNDEC (extension fondee = vide )

6. Exercices

Les cellules ci-dessous sont des squelettes à compléter. Le notebook s’exécute de bout en bout même si vous ne les complétez pas (elles renvoient None par défaut).

Exercice 1 — Départage strict

Complétez is_strictly_stronger(cat, a, b) : renvoyer True si a est strictement mieux classé que b selon le vecteur cat de h-Categoriser, False sinon.

def is_strictly_stronger(cat, a, b):
    # TODO : comparer cat[a] et cat[b]
    # Indice : "strictement mieux classe" = force strictement superieure.
    return None  # remplacez par votre comparaison


# Test attendu (une fois complete) : True, puis False.
print("a strictement > b ?", is_strictly_stronger(cat, "a", "b"))
print("b strictement > a ?", is_strictly_stronger(cat, "b", "a"))
a strictement > b ? None
b strictement > a ? None

Exercice 2 — Construire un cas de départage

Définissez un AF af_ex2 à 4 arguments dans lequel h-Categoriser départage deux arguments que la sémantique fondée déclare tous deux rejetés (OUT).

Indice : reprenez le motif de la section 3 — un argument attaqué une fois, un autre attaqué deux fois, par des arguments non attaqués.

# TODO : construire af_ex2 = AF({...}, {...})
af_ex2 = None  # remplacez par votre cadre

if af_ex2 is not None:
    c2, _ = h_categoriser(af_ex2)
    print("Forces h-Cat :", {a: round(v, 3) for a, v in c2.items()})
else:
    print("Exercice 2 a completer")
Exercice 2 a completer

Exercice 3 — Détecter la convergence du fardeau

Complétez burden_converged(af, steps, tol) : renvoyer True si, sur l’AF donné, le dernier pas de la suite de fardeau ne diffère du précédent que de moins de tol pour tous les arguments.

Indice : burden_numbers(af, steps) renvoie les vecteurs ; comparez les deux dernières composantes.

def burden_converged(af, steps=8, tol=1e-6):
    # TODO : comparer les deux derniers pas de chaque vecteur de fardeau
    # bn = burden_numbers(af, steps) ; bn[a] est un tuple de longueur steps.
    return None  # remplacez par votre test de convergence


print("Fardeau convergent sur l'AF fil rouge ?", burden_converged(af))
Fardeau convergent sur l'AF fil rouge ? None

Conclusion

  • Les sémantiques de classement raffinent le tout-ou-rien de Dung en attribuant une force numérique à chaque argument, ce qui départage des arguments de même statut.
  • h-Categoriser (\(\mathrm{Cat}(a) = 1/(1+\sum_{b\to a}\mathrm{Cat}(b))\)) est un point fixe qui converge sur tout AF fini, y compris cyclique.
  • La sémantique du fardeau classe par comparaison lexicographique d’une suite de nombres.
  • Les deux respectent des principes structurels (abstraction, indépendance, contre-transitivité).

Pour aller plus loin : la bibliothèque Tweety (org.tweetyproject.arg.rankings) implémente ces sémantiques et bien d’autres (Categoriser, Burden, Discussion-based, Tuples*, Matt & Toni). Voir aussi le notebook compagnon Argument_Analysis_Dung_AF_Semantics pour les sémantiques d’extension.

Références. - P. Besnard, A. Hunter (2001). A logic-based theory of deductive arguments. Artificial Intelligence. - L. Amgoud, J. Ben-Naim (2013). Ranking-based semantics for argumentation frameworks. SUM. - F. Pu, J. Luo, Y. Zhang, G. Luo (2014). Argument ranking with categoriser function. KSEM (convergence).

Retour au sommet