John Dvorak
f8f6c5cb1b
Dead code with zero callers (deprecation notes promised removal): - RelationCSR index: always-off option (useRelationCsrIndex), never enabled in production, wired through RelationManager/RelationUpdates/ RelationLookup. Removed the module and all wiring. - getAggregatedBlurredValue (RelationManager) and aggregateBlurredValues (ValueManager): @deprecated shims, zero callers. - QualitativeRelationalComparatorRule._aggregateBlurredValues: @deprecated shim, zero callers. Kept compareRelationValues: non-deprecated public API, coherent and clock-threaded, just currently callerless. Stale scaffolding shipping in the published artifact (files: src/): - src/ast/tests/* and src/ast/examples/*: orphaned duplicates of tests/ast/, zero references anywhere, 11 files in the tarball. Removed; the live copies live in tests/ast/. Internal docs moved out of the shipped surface (1266 lines) to docs/internal/: VALUE_OPTIMIZATION_SUMMARY, rules API_SPECIFICATION, ast README, qualitative README — repo-kept, not packaged. Tarball .md count: 11 -> 1. Rigor 251/251, full suite 853/791/0.
257 lines
8.7 KiB
Markdown
257 lines
8.7 KiB
Markdown
# Qualitative Capacity System
|
||
|
||
This module provides a complete implementation of qualitative capacities (q-capacities) as described in the research paper on qualitative capacities and their applications to evidential reasoning, decision making, and imprecise possibility.
|
||
|
||
## Overview
|
||
|
||
A qualitative capacity γ: 2^W → L is a monotonic set-function where:
|
||
- γ(∅) = 0, γ(W) = 1
|
||
- If A ⊆ B, then γ(A) ≤ γ(B)
|
||
- L is a finite totally ordered scale with order-reversing negation
|
||
|
||
The core design principle is to use the Qualitative Möbius Transform (QMT) γ# as the canonical internal representation for any q-capacity γ.
|
||
|
||
## Core Components
|
||
|
||
### 1. SetUtils
|
||
|
||
Utility functions for working with Sets as Map keys, providing canonical string representations for consistent and efficient Map operations.
|
||
|
||
```javascript
|
||
import { getSetKey, setFromKey, setsEqual } from './src/qualitative/index.js';
|
||
|
||
const set = new Set(['a', 'b', 'c']);
|
||
const key = getSetKey(set); // "a,b,c"
|
||
const reconstructed = setFromKey(key); // Set(['a', 'b', 'c'])
|
||
const areEqual = setsEqual(set, reconstructed); // true
|
||
```
|
||
|
||
### 2. QualitativeScale
|
||
|
||
Finite totally ordered scales with order-reversing negation.
|
||
|
||
```javascript
|
||
import { QualitativeScale } from './src/qualitative/index.js';
|
||
|
||
// Create a 5-point scale
|
||
const scale = QualitativeScale.fivePoint(); // [0, 0.25, 0.5, 0.75, 1]
|
||
|
||
// Test operations
|
||
console.log(scale.min(0.25, 0.75)); // 0.25
|
||
console.log(scale.max(0.25, 0.75)); // 0.75
|
||
console.log(scale.negate(0.25)); // 0.75 (order-reversing)
|
||
```
|
||
|
||
### 3. QualitativeCapacity
|
||
|
||
Q-capacities with QMT internal representation.
|
||
|
||
```javascript
|
||
import { QualitativeCapacity } from './src/qualitative/index.js';
|
||
|
||
const stateSpace = ['s1', 's2', 's3'];
|
||
const scale = QualitativeScale.ternary();
|
||
|
||
// Create a simple support capacity
|
||
const ssc = QualitativeCapacity.createSimpleSupport(
|
||
stateSpace,
|
||
['s1'],
|
||
0.5,
|
||
scale
|
||
);
|
||
|
||
// Get capacity values
|
||
console.log(ssc.getCapacity(['s1'])); // 0.5
|
||
console.log(ssc.getCapacity(['s1', 's2'])); // 1
|
||
|
||
// Check if it's a necessity measure
|
||
console.log(ssc.isNecessityMeasure()); // true
|
||
```
|
||
|
||
### 4. QualitativeFusion
|
||
|
||
Theoretically sound fusion rules for capacity combination.
|
||
|
||
```javascript
|
||
import { QualitativeFusion } from './src/qualitative/index.js';
|
||
|
||
// Create multiple capacities
|
||
const cap1 = QualitativeCapacity.createSimpleSupport(stateSpace, ['s1'], 0.5, scale);
|
||
const cap2 = QualitativeCapacity.createSimpleSupport(stateSpace, ['s2'], 0.5, scale);
|
||
|
||
// Normalized conjunctive fusion (theoretically sound)
|
||
const fused = QualitativeFusion.normalizedConjunctive([cap1, cap2]);
|
||
|
||
// Disjunctive fusion
|
||
const disjunctive = QualitativeFusion.disjunctive(cap1, cap2);
|
||
|
||
// Sugeno integral for decision making
|
||
const decisionFunction = { 's1': 0.5, 's2': 1, 's3': 0.5 };
|
||
const sugenoValue = QualitativeFusion.sugenoIntegral(fused, decisionFunction);
|
||
```
|
||
|
||
### 5. OWAQualitativeFusion
|
||
|
||
Bag algebras for sophisticated qualitative aggregation.
|
||
|
||
```javascript
|
||
import { OWAQualitativeFusion } from './src/qualitative/index.js';
|
||
|
||
const values = [0.25, 0.5, 0.75];
|
||
const metas = [{ source: 'rule1' }, { source: 'rule2' }, { source: 'rule3' }];
|
||
|
||
// Different aggregation modes
|
||
const maxResult = OWAQualitativeFusion.max(values, metas, scale);
|
||
const majorityResult = OWAQualitativeFusion.majority(values, metas, scale);
|
||
const optimisticResult = OWAQualitativeFusion.optimistic(values, metas, scale);
|
||
|
||
// Configurable activation threshold
|
||
const selectiveResult = OWAQualitativeFusion.max(values, metas, scale, 0.8);
|
||
|
||
// Proper Sugeno integral
|
||
const sugenoResult = OWAQualitativeFusion.sugenoIntegral(capacity, decisionFunction);
|
||
```
|
||
|
||
### 6. QMTOWAFusion
|
||
|
||
Theoretically sound OWA-like operators that work directly on QMTs.
|
||
|
||
```javascript
|
||
import { QMTOWAFusion } from './src/qualitative/index.js';
|
||
|
||
// These methods preserve monotonicity by working on QMTs directly
|
||
const optimistic = QMTOWAFusion.optimisticFusion([cap1, cap2]);
|
||
const pessimistic = QMTOWAFusion.pessimisticFusion([cap1, cap2]);
|
||
const majority = QMTOWAFusion.majorityFusion([cap1, cap2]);
|
||
const priority = QMTOWAFusion.priorityFusion([cap1, cap2], [10, 5]);
|
||
```
|
||
|
||
## Theoretical Considerations
|
||
|
||
### Pointwise OWA Fusion Warning
|
||
|
||
The `pointwiseOWAFusion` method (formerly `fuseCapacities`) performs pointwise OWA fusion on capacity values, which **does NOT guarantee** that the result is a valid qualitative capacity. The resulting set-function may violate the fundamental monotonicity property: A⊆B ⟹ γ(A)≤γ(B).
|
||
|
||
**Use this method only for experimental purposes or when monotonicity is not required.**
|
||
|
||
For theoretically sound capacity fusion, use:
|
||
- `QualitativeFusion.normalizedConjunctive()`
|
||
- `QualitativeFusion.disjunctive()`
|
||
- `QMTOWAFusion` methods
|
||
|
||
### Qualitative OWA Operator
|
||
|
||
The qualitative OWA operator implements a novel weighted maximum where weights act as "gates" that must pass a threshold to allow their corresponding values to be considered. This is distinct from the standard Sugeno integral but provides a practical way to introduce weight influence in purely ordinal contexts.
|
||
|
||
The activation threshold is configurable (default 0.5) to allow for more or less "selective" aggregations.
|
||
|
||
### Sugeno Integral
|
||
|
||
The Sugeno integral is the qualitative counterpart to the Choquet integral and provides a theoretically sound way to aggregate qualitative values with respect to a capacity:
|
||
|
||
S_γ(f) = max_{i=1}^n min(f_{(i)}, γ(A_{(i)}))
|
||
|
||
where f_{(i)} are the sorted values in descending order and A_{(i)} = {w_{(1)}, ..., w_{(i)}}.
|
||
|
||
## Applications
|
||
|
||
### 1. Evidential Reasoning
|
||
|
||
Combine testimonies from different sources using Simple Support Capacities and normalized conjunctive fusion.
|
||
|
||
```javascript
|
||
// Create testimonies as Simple Support Capacities
|
||
const testimony1 = QualitativeCapacity.createSimpleSupport(
|
||
stateSpace,
|
||
['s1'],
|
||
0.8,
|
||
scale
|
||
);
|
||
|
||
const testimony2 = QualitativeCapacity.createSimpleSupport(
|
||
stateSpace,
|
||
['s2'],
|
||
0.6,
|
||
scale
|
||
);
|
||
|
||
// Fuse testimonies
|
||
const combinedEvidence = QualitativeFusion.normalizedConjunctive([
|
||
testimony1,
|
||
testimony2
|
||
]);
|
||
```
|
||
|
||
### 2. Qualitative Decision Making
|
||
|
||
Use Sugeno integrals to evaluate decisions based on qualitative utility functions and uncertainty represented by q-capacities.
|
||
|
||
```javascript
|
||
// Define decision function (utility for each state)
|
||
const utility = {
|
||
's1': 0.8, // High utility
|
||
's2': 0.4, // Medium utility
|
||
's3': 0.2 // Low utility
|
||
};
|
||
|
||
// Evaluate decision using Sugeno integral
|
||
const decisionValue = QualitativeFusion.sugenoIntegral(capacity, utility);
|
||
```
|
||
|
||
### 3. Imprecise Possibility
|
||
|
||
Represent ill-known possibility measures bounded by lower (q-capacity) and upper (possibility) measures.
|
||
|
||
```javascript
|
||
// Get upper capacity (possibility measure)
|
||
const upperCapacity = capacity.getUpperCapacity();
|
||
|
||
// Get contour function
|
||
const contour = capacity.getContourFunction();
|
||
|
||
// Get conjugate capacity
|
||
const conjugate = capacity.getConjugate();
|
||
```
|
||
|
||
## Performance Considerations
|
||
|
||
The current implementation has O(2^|W|) complexity for operations that generate all subsets. This is suitable for small state spaces (|W| < 20) but may not scale to larger ones.
|
||
|
||
### Optimizations Implemented
|
||
|
||
1. **QualitativeScale Optimizations**:
|
||
- `contains()`: O(1) average time using Set-based lookup
|
||
- `indexOf()`: O(log n) time using binary search
|
||
- These optimizations significantly improve performance for scale operations
|
||
|
||
2. **Canonical QMT Optimization**:
|
||
- `_convertToCanonicalQMT()`: Only checks immediate proper subsets instead of all smaller subsets
|
||
- Uses the mathematical property: γ#(A) > 0 ⟺ γ(A) > max_{w∈A} γ(A∖{w})
|
||
- Provides substantial performance improvement for canonicalization
|
||
|
||
3. **String Key Robustness**:
|
||
- All Set objects are converted to canonical string keys for Map operations
|
||
- Eliminates JavaScript Set reference comparison issues
|
||
- Ensures consistent and efficient Map key operations
|
||
|
||
4. **Canonicalization Consistency**:
|
||
- All fusion methods return canonical QMTs by default
|
||
- Ensures minimal representation and consistent behavior
|
||
- Simplifies subsequent operations and saves memory
|
||
|
||
For large state spaces, consider:
|
||
1. Working with QMTs directly (already implemented)
|
||
2. Using sparse representations
|
||
3. Implementing approximation algorithms
|
||
|
||
## Future Research Directions
|
||
|
||
1. **QMT-based OWA**: Develop more sophisticated OWA-like operators that work directly on QMTs
|
||
2. **Complexity Optimization**: Implement efficient algorithms for large state spaces
|
||
3. **Approximation Methods**: Develop approximation algorithms for intractable operations
|
||
4. **Integration with DSL**: Extend the Evidence DSL to support qualitative capacities
|
||
|
||
## References
|
||
|
||
This implementation is based on the research paper "Qualitative capacities: basic notions and potential applications" and related work on qualitative uncertainty theory, possibility theory, and evidential reasoning.
|