TL;DR
This paper tackles the persistent challenge of handling exceptions in knowledge representation systems, specifically within parallel semantic networks like NETL. The authors propose a novel cancellation scheme using "UNCANCEL" and "UNEXCLUDE" links to manage exceptions efficiently and maintain parallelism, addressing limitations of prior approaches.
What Problem Does This Paper Address?
Representing knowledge often involves making general statements about classes of objects (e.g., "all elephants are gray"). However, real-world knowledge is full of exceptions (e.g., "royal elephants are white"). Traditional logical systems struggle with these exceptions, and early semantic network systems often handled them inefficiently or with complex masking mechanisms that broke down in more intricate scenarios. This paper focuses on the specific problem of cancelling inherited class membership in parallel semantic networks, where speed is paramount. The core issue is how to allow for exceptions without sacrificing the performance benefits of parallel processing, especially when dealing with complex inheritance hierarchies.
Methods
The paper introduces a new cancellation scheme for NETL-like parallel semantic networks. The core idea is to augment the existing "CANCEL" links with two new types of links:
- UNCANCEL Link: This link is used to explicitly override a "CANCEL" link for a specific subclass. It effectively "turns off" a cancellation for a particular path in the hierarchy.
- UNEXCLUDE Link: This is the counterpart to "UNCANCEL" for downscans. It's used to override a cancellation that would prevent inheritance in a downward traversal of the network.
These new links are integrated into the existing marker-passing algorithms (upscans and downscans). The authors propose a strategy of maintaining network consistency by checking for and resolving potential conflicts (merge points) at the time of network modification, rather than solely at access time. This involves adding UNCANCEL/UNEXCLUDE links or new direct CANCEL links to ensure that all merge points below a CANCEL link are properly handled.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Cancellation is Fundamental: The paper strongly argues that handling exceptions (cancellation) is not a minor feature but a fundamental requirement for any practical knowledge representation system.
- Parallelism vs. Complexity: The inherent difficulty in handling cancellation in parallel systems like NETL stems from the decision to use simple, single-bit markers and parallel scans. More complex markers or processing would solve the problem but at a significant cost in hardware and complexity.
- Consistency is Key: The authors emphasize that the problem isn't just about defining cancellation but about ensuring the network remains in a consistent state. Ambiguous situations (merge points) must be resolved to guarantee correct upscan and downscan behavior.
- Proactive Conflict Resolution: The proposed solution shifts the burden of resolving conflicts from access time to modification time. This pre-processing approach ensures the network is always in a "legal" and unambiguous state, making subsequent queries faster and more reliable.
- Symmetry in Cancellation: The introduction of UNCANCEL and UNEXCLUDE links creates a more symmetrical and robust system for handling cancellations in both upward (inheritance) and downward (recognition) traversals.
Key Results
The paper doesn't present quantitative results in terms of specific performance metrics (e.g., speedup percentages). Instead, it focuses on the qualitative results of the proposed scheme:
- Workable Cancellation for NETL: The UNCANCEL and UNEXCLUDE link scheme is presented as a workable solution for handling class membership cancellation in parallel semantic networks like NETL.
- Preservation of Parallelism: The proposed algorithms aim to preserve the parallel nature of upscans and downscans, ensuring that their running time remains proportional to the depth of the relevant chain, not the number of nodes marked.
- Resolution of Ambiguities: The scheme provides a mechanism to resolve ambiguous situations arising from multiple inheritance paths and cancellations, preventing "race conditions" where cancellation markers arrive too late.
- Handling Complex Examples: The paper demonstrates how the scheme can naturally handle complex scenarios like the mollusc-cephalopod-nautilus example, which posed problems for simpler cancellation methods.
Limitations and Future Work
- "Partial" Solution: The authors acknowledge that their solution is "partial" and doesn't deal with all possible complicating factors, such as multiple contexts.
- Consistency Maintenance Cost: While the scheme preserves parallelism during access, maintaining network consistency by adding/deleting auxiliary links at modification time incurs a computational cost. The authors believe this is a worthwhile trade-off, assuming modifications are less frequent than accesses.
- Theoretical Understanding: The paper highlights a lack of firm theoretical understanding of what kinds of problems are efficiently solvable by marker-passing parallelism. Further exploration in this area is needed.
- Inconsistency Detection: While race conditions can indicate inconsistencies, they are not an infallible indicator. The authors suggest that the system might need to re-check CANCEL links periodically to ensure consistency.
- Future Work: The authors suggest that much more exploration of parallelism and its limitations is needed. They also note that the consistency checking for a change might not always complete, requiring mechanisms to handle such events.
Summary updated