<commit_before>;
; gram-class.scm
;
; Merge words into grammatical categories.
;
; Copyright (c) 2017, 2018 <NAME>
;
; ---------------------------------------------------------------------
; OVERVIEW
; --------
; When a pair of words are judged to be grammatically similar, they
; can be used to create a "grammatical class", containing both the
; words, and behaving as thier union/sum.  When a word is judged to
; belong to an existing grammatical-class, then some mechanism must
; be provided to add that word to the class.  This file implements
; the tools for creating and managing such classes.  It does not
; dictate how to judge when words belong to a class; this is done
; independently of the structure of the classes themselves.
;
; A grammatical class is represented as
;
;     MemberLink
;         WordNode "wordy"      ; the word itself
;         WordClassNode "noun"  ; the grammatical class of the word.
;
; Word classes have a designated grammatical behavior, using Sections,
; behaving just like the pseudo-connectors on single words. Thus, either
; a WordNode or a WordClassNode can appear in a Connector link, as
; shown below.
;
;     Section
;         WordClassNode "noun"
;         ConnectorSeq
;             Connector
;                WordClassNode "verb" ; or possibly a WordNode
;                LgConnDirNode "+"
;             Connector
;                ....
;
; Basic assumptions
; -----------------
; It is assummed that grammatical classes are stepping stones to word
; meaning; that meaning and grammatical class are at least partly
; correlated. It is assumed that words can have multiple meanings,
; and can belong to multiple grammatical classes. It is assumed that
; the sum total numner of observations of a word is a linear combination
; of the different ways that the word was used in the text sample.
; Thus, the task is to decompose the observed counts on a single word,
; and assign them to one of a number of different grammatical classes.
;
; The above implies that each word should be viewed as a vector; the
; disjuncts form the basis of the vector space, and the count of
; observations of different disjuncts indicating the direction of the
; vector. It is the linearity of the observations that implies that
; such a vector-based linear approach is correct.
;
; The number of grammatical classes that a word might belong to can
; vary from a few to a few dozen; in addition, there will be some
; unknown amount of "noise": incorrect sections due to incorrect parses.
;
; It is assumed that when a word belong to several grammatical classes,
; the sets of disjuncts defining those classes are not necessarily
; disjoint; there may be significant overlap.
;
; Merging
; -------
; There are several ways in which two words might be merged into a
; word-class, or a word added to a word-class. All of these are
; quasi-linear, trying to project out the different classes that
; the word belongs to.
;
; Union word-pair merging
; ------------------------
; Given two words, add them as vectors, creating a new vector, the
; word-class. This is purely linear summation. Next, compute the
; orthogonal components of the words to the word-class, and replace
; the words by thier orthogonal components - i.e. subtract the parallel
; components. It seems best to avoid negative observation counts, so
; if any count on any section is negative, it is clamped to zero (i.e.
; that section is removed, as this is a sparse vector). This last step
; renders this process only quasi-linear.
;
; Note the following properties of the above algo:
; a) The combined vector has strictly equal or larger support than
;    the parts. This might not be correct, as it seems that it will
;    mix in disjuncts that should have been assigned to other meanings.
; b) The process is not quite linear, as orthogonal components with
;    negative counts are clamped to zero.
; c) The number of vectors being tracked in the system is increasing:
;    before there were two, once for each word, now there are three:
;    each word remains, with altered counts, as well as thier sum.
;    It might be nice to prune the number of vectors, so that the
;    dataset does not get outrageously large. Its possible that short
;    vectors might be mostly noise.
; d) There is another non-linearity, when a word is assigned to an
;    existing word-class. This assignment will slightly alter the
;    direction of the word-class vector, but will not trigger the
;    recomputation of previous orthognoal components.
; e) The replacement of word-vectors by thier orthogonal components
;    means that the original word vectors are "lost". This could be
;    avoided by creating new "left-over" word vectors to hold just
;    the orthogonal components. However, this increases the size of
;    the dataset, and does not seem to serve any useful purpose.
;
; Overlap merging
; ---------------
; Similar to the above, a linear sum is taken, but the sum is only over
; those disjuncts that both words share in common. This might be more
; appropriate for disentangling linear combinations of multiple
; word-senes. It seems like it could be robust even with lower
; similarity scores (e.g. when using cosine similarity).
;
; Overlap merging appears to solve the problem a) above, but, on the
; flip side, it also seems to prevent the discovery and broadening
; of the ways in which a word might be used.
;
; merge-ortho
; -----------
; The above two merge methods are implemented in the `merge-ortho`
; function. It takes, as an argument, a fractional weight which is
; used when the disjunct isn't shared between both words. Setting
; the weight to zero gives overlap merging; setting it to one gives
; union merging. Setting it to fractional values provides a merge
; that is intermediate betwen the two: an overlap, plus a bit more,
; viz some of the union.
;
; In the code below, this is currently a hard-coded paramter, set to
; the ad hoc value of 0.3.  Behavior with different values is unexplored.
;
; Agglomerative clustering
; ------------------------
; The de facto algorithm implemented here is agglomerative clustering.
; That is, each word is compared to each of the existing clusters, and
; if it is close enough, it is merged in.  If a word cannot be assigned
; to a cluster, it is treated as a new cluster-point, and is tacked onto
; the list of existing clusters.
;
; That is, the existing clusters act as a seive: new words either fall
; into one of the existing "holes", or start a new "hole".
;
; XXX Except this is not what the code actually does, as written. It
; deviates a bit from this, in a slightly wacky fashion. XXX FIXME.
;
; Similarity; Cosine similarity
; -----------------------------
; There are several different means of comparing similarity between
; two words.  The simplest is cosine distance: if the cosine of two
; word-vectors is greater than a threshold, they should be merged.
;
; The cosine-distance is a user tunable paramter in the code below;
; it is currently hard-coded to 0.65.
;
; A very diff
;
; Broadening
; ----------
; The issue described in a) is an issue of broadening the known usages
; of a word, beyond what has been strictly observed in the text.  There
; are two distinct opportunities to broaden: first, in the union vs.
; overlap merging above, and second, in the merging of disjuncts. That
; is, the above merging did not alter the number of disjuncts in use:
; the disjuncts on the merged class are still disjuncts with single-word
; connectors. At some point, disjuncts should also be merged, i.e. by
; merging the connectors on them.
;
; If disjunct merging is performed after a series of word mergers have
; been done, then when a connector-word is replaced by a connector
; word-class, that class may be larger than the number of connectors
; originally witnessed. Again, the known usage of the word is broadened.
;
; Disjunct merging
; ----------------
; Disjunct merging is the second step in creating grammatical classes.
; The idea here is to replace individual connectors that specifiy words
; with connectors that specify word-classes. This step is examined in
; greater detail in `cset-class.scm`.
;
; ---------------------------------------------------------------------

(use-modules (srfi srfi-1))
(use-modules (ice-9 threads))<commit_msg>Add a section on semantic similarity.<commit_after>;
; gram-class.scm
;
; Merge words into grammatical categories.
;
; Copyright (c) 2017, 2018 <NAME>
;
; ---------------------------------------------------------------------
; OVERVIEW
; --------
; When a pair of words are judged to be grammatically similar, they
; can be used to create a "grammatical class", containing both the
; words, and behaving as thier union/sum.  When a word is judged to
; belong to an existing grammatical-class, then some mechanism must
; be provided to add that word to the class.  This file implements
; the tools for creating and managing such classes.  It does not
; dictate how to judge when words belong to a class; this is done
; independently of the structure of the classes themselves.
;
; A grammatical class is represented as
;
;     MemberLink
;         WordNode "wordy"      ; the word itself
;         WordClassNode "noun"  ; the grammatical class of the word.
;
; Word classes have a designated grammatical behavior, using Sections,
; behaving just like the pseudo-connectors on single words. Thus, either
; a WordNode or a WordClassNode can appear in a Connector link, as
; shown below.
;
;     Section
;         WordClassNode "noun"
;         ConnectorSeq
;             Connector
;                WordClassNode "verb" ; or possibly a WordNode
;                LgConnDirNode "+"
;             Connector
;                ....
;
; Basic assumptions
; -----------------
; It is assummed that grammatical classes are stepping stones to word
; meaning; that meaning and grammatical class are at least partly
; correlated. It is assumed that words can have multiple meanings,
; and can belong to multiple grammatical classes. It is assumed that
; the sum total numner of observations of a word is a linear combination
; of the different ways that the word was used in the text sample.
; Thus, the task is to decompose the observed counts on a single word,
; and assign them to one of a number of different grammatical classes.
;
; The above implies that each word should be viewed as a vector; the
; disjuncts form the basis of the vector space, and the count of
; observations of different disjuncts indicating the direction of the
; vector. It is the linearity of the observations that implies that
; such a vector-based linear approach is correct.
;
; The number of grammatical classes that a word might belong to can
; vary from a few to a few dozen; in addition, there will be some
; unknown amount of "noise": incorrect sections due to incorrect parses.
;
; It is assumed that when a word belong to several grammatical classes,
; the sets of disjuncts defining those classes are not necessarily
; disjoint; there may be significant overlap.
;
; Merging
; -------
; There are several ways in which two words might be merged into a
; word-class, or a word added to a word-class. All of these are
; quasi-linear, trying to project out the different classes that
; the word belongs to.
;
; Union word-pair merging
; ------------------------
; Given two words, add them as vectors, creating a new vector, the
; word-class. This is purely linear summation. Next, compute the
; orthogonal components of the words to the word-class, and replace
; the words by thier orthogonal components - i.e. subtract the parallel
; components. It seems best to avoid negative observation counts, so
; if any count on any section is negative, it is clamped to zero (i.e.
; that section is removed, as this is a sparse vector). This last step
; renders this process only quasi-linear.
;
; Note the following properties of the above algo:
; a) The combined vector has strictly equal or larger support than
;    the parts. This might not be correct, as it seems that it will
;    mix in disjuncts that should have been assigned to other meanings.
;    (the SUPPORT issue; discussed further below).
; b) The process is not quite linear, as orthogonal components with
;    negative counts are clamped to zero.
;    (the LEXICAL issue; discussed further, below)
; c) The number of vectors being tracked in the system is increasing:
;    before there were two, once for each word, now there are three:
;    each word remains, with altered counts, as well as thier sum.
;    It might be nice to prune the number of vectors, so that the
;    dataset does not get outrageously large. Its possible that short
;    vectors might be mostly noise.
; d) There is another non-linearity, when a word is assigned to an
;    existing word-class. This assignment will slightly alter the
;    direction of the word-class vector, but will not trigger the
;    recomputation of previous orthognoal components.
; e) The replacement of word-vectors by thier orthogonal components
;    means that the original word vectors are "lost". This could be
;    avoided by creating new "left-over" word vectors to hold just
;    the orthogonal components. However, this increases the size of
;    the dataset, and does not seem to serve any useful purpose.
;
; Overlap merging
; ---------------
; Similar to the above, a linear sum is taken, but the sum is only over
; those disjuncts that both words share in common. This might be more
; appropriate for disentangling linear combinations of multiple
; word-senses. It seems like it could be robust even with lower
; similarity scores (e.g. when using cosine similarity).
;
; Overlap merging appears to solve the problem a) above (the SUPPORT
; issue), but, on the flip side, it also seems to prevent the discovery
; and broadening of the ways in which a word might be used.
;
; merge-ortho
; -----------
; The above two merge methods are implemented in the `merge-ortho`
; function. It takes, as an argument, a fractional weight which is
; used when the disjunct isn't shared between both words. Setting
; the weight to zero gives overlap merging; setting it to one gives
; union merging. Setting it to fractional values provides a merge
; that is intermediate betwen the two: an overlap, plus a bit more,
; viz some of the union.
;
; In the code below, this is currently a hard-coded paramter, set to
; the ad hoc value of 0.3.  Behavior with different values is unexplored.
;
; Agglomerative clustering
; ------------------------
; The de facto algorithm implemented here is agglomerative clustering.
; That is, each word is compared to each of the existing clusters, and
; if it is close enough, it is merged in.  If a word cannot be assigned
; to a cluster, it is treated as a new cluster-point, and is tacked onto
; the list of existing clusters.
;
; That is, the existing clusters act as a seive: new words either fall
; into one of the existing "holes", or start a new "hole".
;
; XXX Except this is not what the code actually does, as written. It
; deviates a bit from this, in a slightly wacky fashion. XXX FIXME.
;
; Cosine similarity
; -----------------
; There are several different means of comparing similarity between
; two words.  The simplest is cosine distance: if the cosine of two
; word-vectors is greater than a threshold, they should be merged.
;
; The cosine-distance is a user tunable paramter in the code below;
; it is currently hard-coded to 0.65.
;
; Semantic similarity
; -------------------
; A very different, and more semantically correct merge and clustering
; criterion is possible.  Its inspired by the observation that some
; words have multiple different meanings. Consider the word "saw" with
; the meanings "observe" and "cut".
;
; The cosine distance between the two words w_a, w_b is
;
;    cos(w_a, w_b) = v_a . v_b / |v_a||v_b|
;
; Where, as usual, v_a . v_b is the dot product, and |v| is the length.
; The vector v_b can be decomposed int parallel and perendicular parts:
;
;   v_b = v_llel + v_perp
;
;   v_llel = v_a |v_b| cos / |v_a|
;   v_perp = v_b - v_llel
;
; which has the properties that v_llel points in the same direction as
; v_a and v_perp is perpendicular to v_a.  Now, because v_perp involves
; a subtraction, there will be, in general, vector components in v_perp
; that are negative (as mentioned above). However, if all vector
; components of v_perp are positive, then we can conclude that v_b can
; be decomposed into "two meanings" (or more).  One "meaning" is indeed
; v_a (i.e. is v_llel), the second meaning is v_perp.
;
; It seems reasonable to expect that "saw" would obey this relationship,
; with w_a == observe, w_b == saw, w_perp == cut.
;
; However, if v_perp has lots of negative components, then such an
; orthogonalization seems incorrect. That is, suppose that some other
; v_a and v_b had a small cosine distance (viz are alost colinear) but
; v_perp had many negative components. One cannot reasonably expect
; v_perp to identify "some other meaning" for v_b. Instead, it would
; seem that v_perp just consists of grunge that "should have been" in
; v_a, but wasn't.
;
; Thus, to solve problem b) above, (the LEXICAL issue), the correct
; merge algo would seem to be:
;
;   Let w_a be an existing cluster
;   Let w_b be a candidate word to be merged into the cluster.
;   Compute v_llel and v_perp.
;   Let v_clamp = v_perp with negative components set to zero.
;   Let v_anew = v_a + v_llel + (v_b - v_clamp)
;   Let v_bnew = v_clamp
;
; This would seem to have the effect of "broadening" v_a with missing
; vector components, while cleanly extracting the semantically different
; parts of v_b and sticking them into v_bnew.
;
; XXX this is not yet implemented; FIXME.
;
; Broadening
; ----------
; The issue described in a) is an issue of broadening the known usages
; of a word, beyond what has been strictly observed in the text.  There
; are two distinct opportunities to broaden: first, in the union vs.
; overlap merging above, and second, in the merging of disjuncts. That
; is, the above merging did not alter the number of disjuncts in use:
; the disjuncts on the merged class are still disjuncts with single-word
; connectors. At some point, disjuncts should also be merged, i.e. by
; merging the connectors on them.
;
; If disjunct merging is performed after a series of word mergers have
; been done, then when a connector-word is replaced by a connector
; word-class, that class may be larger than the number of connectors
; originally witnessed. Again, the known usage of the word is broadened.
;
; Disjunct merging
; ----------------
; Disjunct merging is the second step in creating grammatical classes.
; The idea here is to replace individual connectors that specifiy words
; with connectors that specify word-classes. This step is examined in
; greater detail in `cset-class.scm`.
;
; ---------------------------------------------------------------------

(use-modules (srfi srfi-1))
(use-modules (ice-9 threads))
{'fraction_non_alphanumeric': 0.08675319216015974, 'fraction_numerical': 0.001576375387525616, 'mean_word_length': 3.2180851063829787, 'pattern_counts': {'":': 2, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4135223', 'n_tokens_mistral': 5118, 'n_tokens_neox': 4882, 'n_words': 2822}