Processing math: 100%

Compositionality

Dealing with Compositionality

This blog will introduce the research done in syntax that addressed compositionality. In one of the connectionist natural language processing papers I have read about, it touches on government binding theory proposed by Chomsky, and the paper tried to model the motion from d-structure to s-structure in GB theory through the non-overlap constraint and chain map combined with NNs.

And the demonstration of the non-overlap map is below

Non-Overlap Constraint Explained

The non-overlap constraint is a rule in cognitive models or neural networks that prevents overlapping activations of units in a chain map. This ensures that no two units representing the same syntactic marker can be active simultaneously, which helps maintain clear and distinct representations.

Diagram Breakdown

Components:
Chain Map (Green Text):
  • Represents the initial activation of units.
  • Units in this map correspond to elements or tokens that can be active.
Non-Overlap Map (Red Text):
  • Corresponds to the chain map and enforces non-overlapping activations.
  • Units in this map prevent other units in the same diagonal from activating.
  • These links prevent other units in the corresponding diagonal of the chain map from activating, thereby enforcing the non-overlap constraint.
Activation of Corresponding Unit In The Non-Overlap Map (Red Arrow)
  • The red arrow or the lateral link indicates an activation process from the chain map where there is a unit activated. Correspondingly, there is a unit in direct parallel in the non-overlap map being activated.
Process:
  1. When a unit in the chain map is activated, it activates its corresponding unit in the non-overlap map.
  2. The active unit in the non-overlap map then inhibits all other units in the same diagonal in the chain map.
  3. This ensures no two units in the chain map, which represent the same syntactic marker, can be active simultaneously.

Code Example with Explanation

Let’s look at a pseudo implementation that matches the diagram:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Unit:
def __init__(self, identifier):
self.identifier = identifier
self.active = False

def __repr__(self):
return f"Unit({self.identifier}, active={self.active})"

class Map:
def __init__(self, name):
self.name = name
self.units = [[Unit(f"{name}{chr(65+i)}{j+1}") for j in range(5)]
for i in range(5)]

def activate_unit(self, row, col):
self.units[row][col].active = True
print(f"Activating {self.units[row][col]} in {self.name} map.")
self.enforce_non_overlap(row, col)


def enforce_non_overlap(self, row, col):
for i in range(5): # Iterate through all rows
for j in range(5): # Iterate through all columns
if (i - row) == -(j - col): # Top-right to bottom-left diagonal
if i == row and j == col:
continue # Skip the currently activated unit
self.units[i][j].active = False # Deactivate other diagonal units
print(f"Deactivating {self.units[i][j]} in {self.name} map due to diagonal inhibition.")
else:
# Deactivate all non-diagonal units
self.units[i][j].active = False
print(f"Deactivating {self.units[i][j]} in {self.name} map due to non-overlap constraint.")


# Initialize Chain Map and Non-Overlap Map
chain_map = Map("ChainMap")
non_overlap_map = Map("NonOverlapMap")

# Activate unit in Chain Map
chain_map.activate_unit(2, 3)

# Corresponding unit in Non-Overlap Map becomes active
non_overlap_map.activate_unit(2, 3)

# Output the state of maps
print("Chain Map State:")
for row in chain_map.units:
print(row)

print("\nNon-Overlap Map State:")
for row in non_overlap_map.units:
print(row)

Explaining How The Non-Overlap Constraint Gets Enforced

The logic for the top-right to bottom-left diagonal is that as you move one row down, you always move one column to the left from the previous square.

Why does it work this way?

  • Rows (i): Moving down means increasing the row number (e.g., from 2 to 3).
  • Columns (j): Moving left means decreasing the column number (e.g., from 3 to 2).

So, for any square (row, col), the next square in the same diagonal is:

  • One row down: i = row + 1
  • One column left: j = col - 1

And that’s exactly what the math (i - row) == -(j - col) checks:

  • (i - row) → How far you’ve moved down.
  • -(j - col) → How far you’ve moved left (negative because it’s to the left).
  • If these two are equal, you’re on the same diagonal!

Example

Let’s look at a grid and follow the diagonal logic:

1
2
3
4
5
6
  0   1   2   3   4
0 . . . . X <- Start at (0,4)
1 . . . X . <- Move to (1,3)
2 . . X . . <- Move to (2,2)
3 . X . . . <- Move to (3,1)
4 X . . . . <- Move to (4,0)

If you start at (0,4):

  • Next diagonal position: (1,3) → One row down, one column left.
  • Then (2,2), (3,1), (4,0) follow the same pattern.

Each step satisfies:
(irow)==(jcol)


Always True for This Diagonal

For any unit on the diagonal:

  • If you pick a starting point (row, col) and keep moving one row down and one column left, you’ll stay on the top-right to bottom-left diagonal.

Summary

Chain Map Activation:
  • Activating a unit in the chain map triggers the corresponding unit in the non-overlap map.
  • Example: Activating ChainMapA1 will activate NonOverlapMapA1.
Non-Overlap Map Enforces Constraint:
  • The activated unit in the non-overlap map inhibits other units in the same diagonal in the chain map.
  • This ensures that other units in the corresponding diagonal of the chain map remain inactive, preserving the non-overlap constraint.

Conclusion

By combining the visual diagram with the detailed code example, we’ve illustrated how the non-overlap constraint is implemented and enforced in a cognitive or neural model. The non-overlap map plays a crucial role in ensuring that units representing the same syntactic marker do not overlap in their activation, maintaining a clear and distinct representation of information.