Questions & explanations
1. Determine if the CSP with variables x,y in {1,2} and constraint (x!=y) belongs to a known tractable subclass.
The constraint x!=y is a binary inequality constraint. It is known that the class of all binary disequality constraints over a domain of size 2 is NP-complete (it encodes graph coloring for 2 colors? Actually 2-coloring is polynomial). For domain size 2, disequality is essentially XOR, which is not tractable because it can express linear equations mod 2, which is polynomial? Wait: linear equations mod 2 are tractable via Gaussian elimination. However, one disequality constraint alone is trivial. But the general class of binary constraints over a Boolean domain with disequality is equivalent to 2-SAT? Actually 2-SAT is polynomial, but disequality is not a Horn clause. The class of all binary constraints on a Boolean domain? Schaefer's dichotomy says that if all constraints are bijunctive (2-CNF), then it's polynomial. Disequality is bijunctive? (x!=y) is equivalent to (x OR y) AND (¬x OR ¬y), which is 2-CNF. So it is tractable via 2-SAT. So yes, it belongs to the tractable subclass of bijunctive constraints.
2. Prove that the CSP with domain {0,1} and a single ternary constraint allowing only (0,0,0) and (1,1,1) is NP-complete by reducing from 3-SAT.
We reduce 3-SAT to this CSP. For each 3-SAT clause (l1 OR l2 OR l3), we create a new variable c that is forced to 1 (by adding a unary constraint? Actually we need to simulate disjunction. Note that the allowed constraint is 'all equal' but with a twist: it only permits all zeros or all ones. This is essentially a 'equality' constraint across three variables. To encode a clause, we can use auxiliary variables. A standard reduction: for each clause, add a constraint that (l1, l2, a) is allowed, (a, l3, b) allowed, and b=1. This forces at least one li=1. Since the constraint only allows all zeros or all ones, but with auxiliary variables we can force the implication. This shows that deciding whether a CSP with only that constraint is NP-complete. [Note: This is a sketch; full reduction requires more steps but it's a known NP-complete CSP.]
3. Compare an ontology (like OWL) with a simple taxonomy (like a hierarchy of categories). When would you need an ontology over a taxonomy?
A taxonomy is just a tree of categories, like 'Animal -> Mammal -> Dog'. It only shows 'is-a' relationships. An ontology in OWL can express many more relationships, like 'has part', 'works for', and properties that can be transitive or inverse. It can also define rules, restrictions, and equivalence between classes. You need an ontology when you require complex reasoning. For example, in medicine, you might need to say that 'every patient has exactly one primary doctor' or that 'a treatment cures a disease'. Taxonomies cannot capture such constraints. Ontologies allow inference, like if X is part of Y and Y is part of Z, then X is part of Z. So use ontology for deep domain knowledge, taxonomy for simple classification.
4. Why is knowledge representation important for understanding the sentence 'I saw the man with the telescope'?
This sentence is ambiguous: 'with the telescope' could describe how I saw (using a telescope) or which man (the man who holds a telescope). Knowledge representation can help resolve such ambiguity by using world knowledge. For example, if the system knows that telescopes are often used for seeing, it might favor the instrument reading. Or if it knows that a man carrying a telescope is likely, it might choose the modification reading. The system can encode such preferences as rules or probabilistic weights. It also uses syntactic parse and semantic roles to generate candidate interpretations. The chosen interpretation is stored as a formal representation that can be used in further reasoning or question answering.
5. How can an ontology help resolve the word sense of 'bank' in the sentence 'He deposited money at the bank'?
The word 'bank' has multiple senses: financial institution, river bank, etc. An ontology contains concepts like BankFinancial and RiverBank, along with related concepts. For the sentence, the ontology might link 'deposit' to a financial event, which typically involves a financial institution. It also has properties like 'location of deposit' that expect a BankFinancial. The ontology can use context: the word 'money' is often associated with financial banks. So by matching the semantic relationships, the system can infer that the correct sense is BankFinancial. The ontology provides a structured way to encode these associations and disambiguate polysemous words in natural language understanding.
6. Give an example of a neuro-symbolic system that combines learning and reasoning.
One example is a system that learns to play a board game. A neural network learns from many game rounds to evaluate board positions. Then, a symbolic search uses that evaluation to decide the best move by looking ahead. Another example is a visual question-answering system: a neural network finds objects in an image, and a symbolic engine uses logical rules to answer queries like "Is there a red cube on top of a blue cylinder?" These systems can learn new concepts and then reason with them. They often use a hybrid architecture where the neural part produces symbols that the symbolic part manipulates. This combination can outperform pure neural approaches on tasks that need precise reasoning.
7. Compare conceptual graphs with semantic networks. What extra formal semantics do conceptual graphs provide?
Both represent knowledge with nodes and arcs. Semantic networks are informal; they lack strict rules about meaning, so two different networks might mean the same thing but look different. Conceptual graphs have formal logic semantics based on existential graphs. Each graph corresponds to a logical formula. For example, a box around a subgraph represents negation. Conceptual graphs also use canon, a set of rules for building well-formed graphs, ensuring consistency. They have a defined inference mechanism called projection, which checks if one graph is a specialization of another. This makes conceptual graphs more rigorous for machine reasoning, while semantic networks are more heuristic.
8. Give an application of a legal ontology in analyzing legal documents.
An application is automatic contract review. A system uses a legal ontology to identify key clauses, such as 'confidentiality' or 'termination'. It extracts these from the document and compares them to standard templates. For example, it can flag a clause that says 'the employee cannot work for any competitor for 5 years' as potentially too broad. The ontology knows that such restrictions are often limited in duration. The system can also link the clause to relevant case law and suggest changes. This saves time for lawyers. Another application is in legal search: the ontology helps find documents that mention related concepts like 'breach of contract' even if they use different words.
9. How does the canon of conceptual graphs ensure that newly formed graphs are meaningful?
The canon is a set of constraints that every valid conceptual graph must satisfy. It includes: every concept must have a type from the hierarchy; each relation must have appropriate arcs to concepts of specific types (type compatibility); no cycles in the subtype hierarchy; and there is a coreference rule to avoid duplicate concepts representing the same individual. For example, if a relation 'mother' expects a Person as first argument and a Woman as second, the canon ensures that any graph using 'mother' has such types. The canon prevents nonsense like connecting a relation to wrong concept types. It also ensures graphs are logically well-formed, making reasoning sound.
10. What is a challenge in building neuro-symbolic systems?
A major challenge is bridging the gap between neural and symbolic representations. Neural networks work with continuous values (like 0.5, 0.8), while symbolic systems use discrete symbols (like 'cat', 'dog'). Converting between them is difficult. For example, how do you turn a neural image feature into a logical fact like 'object is a cat'? Another challenge is training the whole system end-to-end, because gradient-based learning for neural parts may not work well with symbolic operations. Also, designing the symbolic rules requires expert knowledge, which is hard to scale. Finally, these systems can be slower than pure neural ones due to the symbolic reasoning step.
11. Compare a pure neural network to a neuro-symbolic system on a mathematical word problem.
A pure neural network might try to guess the answer by pattern matching from similar problems it saw during training. For example, given "Mary has 3 apples and gives 2 away, how many left?" it might answer 1 by recognizing the pattern, but it could fail if the wording is slightly different. A neuro-symbolic system would first parse the sentence using neural methods to identify numbers and actions, then use symbolic arithmetic to compute the correct answer. This ensures accuracy even for new wordings. The neuro-symbolic system can also explain its steps, like 'start with 3 apples, subtract 2, result is 1'. The neural network only outputs a number without explanation.
12. What is the difference between a type hierarchy and a relation type in conceptual graphs?
A type hierarchy organizes concept types, like Man and Woman as subtypes of Person. It shows which types are more general or specific. For example, Man is a subtype of Person, so every Man is a Person. Relation types describe how concepts interact, such as 'agent', 'object', or 'location'. For instance, the relation type 'agent' links an action to its doer. Type hierarchy is about individual objects, while relation types are about connections between objects. Both are part of the ontology. The hierarchy helps reason about inheritance (if Man is Person, then all attributes of Person apply to Man). Relation types define the kinds of relationships allowed in graphs.