Adjustment of document relationship graphs
Provided is a process of modifying semantic similarity graphs representative of pair-wise similarity between documents in a corpus, the method comprising obtaining a semantic similarity graph that comprises more than 500 nodes and more than 1000 weighted edges, each node representing a document of a corpus, and each edge weight indicating an amount of similarity between a pair of documents corresponding to the respective nodes connected by the respective edge; obtaining an n-gram indicating that edge weights affected by the n-gram are to be increased or decreased; expanding the n-gram to produce a set of expansion n-grams; adjusting edge weights of edges between pairs of documents in which members of the expanded n-gram set co-occur.
1. A method of modifying semantic similarity graphs representative of pair-wise similarity between documents in a corpus, the method comprising:
obtaining, with one or more processors, a semantic similarity graph that comprises more than 500 nodes and more than 1000 weighted edges, each node representing a document of a corpus, and each edge weight indicating an amount of similarity between a pair of documents corresponding to the respective nodes connected by the respective edge;
after obtaining the semantic similarity graph, obtaining, with one or more processors, a n-gram indicating a request that edge weights affected by the n-gram are to be increased or decreased;
expanding, with one or more processors, the n-gram to produce a set of expansion n-grams, wherein expanding the n-gram comprises:
determining which documents in at least part of the corpus contain the n-gram to form a first set of documents;
determining which documents in at least part of the corpus do not contain the n-gram to form a second set of documents, the first set of documents and the second set of documents each including more than 20 documents;
selecting a set of candidate n-grams from the first set of documents, the set of candidate n-grams having more than five n-grams;
determining an amount of times each candidate n-gram occurs in the first set of documents to form a first amount;
determining an amount of times each candidate n-gram occurs in the second set of documents to form a second amount;
determining, for each of the candidate n-grams, a candidate n-gram score based on the first amount and the second amount, wherein the candidate n-gram scores tends to increase or decrease as a ratio of the first amount to the second amount increases or decreases; and
selecting expansion n-grams based on the candidate n-gram scores, the expansion n-grams and n-gram collectively forming an adjustment n-gram set;
adjusting, with one or more processors, edge weights of the semantic similarity graph of edges between pairs of documents in which members of the adjustment n-gram set co-occur in response to determining that the respective documents contain a member of the adjustment n-gram set, wherein the expansion n-grams are inferred to be conceptually related to the obtained n-gram indicating the request, and wherein the expansion n-grams cause the adjustment of edge weights to be a more comprehensive response to the request than an adjustment based solely on the obtained n-gram indicating the request; and
storing the adjusted weights in memory.
2. The method of claim 1 , where adjusting comprises:
influencing the semantic similarity graph based on user-supplied n-grams that indicate aspects of the semantic similarity graph for which the user requests modification.
3. The method of claim 1 , wherein determining an amount of times each candidate n-gram occurs in the first set of documents to form a first amount is performed before selecting a set of candidate n-grams from the first set of documents.
4. The method of claim 1 , wherein determining, for each of the candidate n-grams, a candidate n-gram score based on the first amount and the second amount comprises:
determining a candidate n-gram score proportionate to the ratio of the first amount to the second amount.
5. The method of claim 1 , wherein determining, for each of the candidate n-grams, a candidate n-gram score based on the first amount and the second amount comprises:
determining a candidate n-gram score disproportionate to the ratio of the first amount to the second amount, wherein the candidate n-gram score monotonically changes in relation to the ratio of the first amount to the second amount.
6. The method of claim 1 , wherein determining, for each of the candidate n-grams, a candidate n-gram score based on the first amount and the second amount comprises:
determining a ratio of a first value to a second value, the first value and the second value both being based on the first amount.
7. The method of claim 1 , wherein the first amount is based on both a count of a number of times the corresponding candidate n-gram appears in the first set of documents and a count of a number of n-grams in the first set of documents.
8. The method of claim 7 , wherein the count of a number of n-grams in the first set of documents is a count of a number of n-grams of the same number of terms as the corresponding candidate n-gram.
9. The method of claim 1 , wherein the second amount is a frequency based on a measure of central tendency of a number of n-grams in each of the second set of documents.
10. The method of claim 1 , wherein determining the candidate n-gram score based on the first amount and the second amount comprises performing steps for determining the candidate n-gram score.
11. The method of claim 1 , wherein adjusting edge weights comprises:
obtaining a feature vector representation of each document, each feature vector indicating an amount of occurrences of respective n-grams in the respective document with respective cardinal values; and
for each of at least some of the feature vectors, selecting cardinal values of the respective feature vector correspond to n-grams in the adjustment n-gram set and adjusting the selected cardinal values.
12. The method of claim 11 , wherein adjusting edge weights comprises:
determining document pair-wise similarity based on angles between adjusted feature vectors.
13. The method of claim 11 , wherein adjusting edge weights comprises:
steps for determining similarity of feature vectors.
14. The method of claim 1 , wherein the obtained graph is a semantic similarity graph comprising vectors as nodes and edges with weights,
the vectors being generated by:
generating, for each document of the corpus, a list of all the unique document n-grams occurring in the document;
counting, for each document of the corpus, the number of times each unique document n-gram occurs in the document and the number of times each unique document n-gram occurs in each of the other documents of the corpus to form a third count and a fourth count, respectively;
calculating, for each document n-gram, a document n-gram relation score;
removing from each list of each document of the corpus a portion of the lowest ranking document n-grams based on their respective document n-gram relation score; and
determining, for each document of the corpus, a vector based on the document n-gram relation score of each n-gram of the respective list,
wherein the weighted similarity comprises a similarity value that is based on angles between the vectors of two nodes and that is above a threshold.
15. The method of claim 1 , comprising:
preparing instructions to form a graphical representation of a semantic similarity graph having the adjusted weights, the graphical representation being a force directed graph, wherein preparing the graphical representation comprises:
clustering the semantic similarity graph having the adjusted weights; and
extracting cluster topics from text of documents corresponding to at least some resulting clusters.
16. The method of claim 1 , wherein expanding on the n-grams to produce the one or more expansion n-grams comprises comparing a conditional probability of observing a matching n-gram given a user-input n-gram with a probability to observe an arbitrary number of times the matching n-gram in the respective document, the probability to observe the arbitrary number of times the matching n-gram being based on a hypergeometric distribution or a Poisson distribution.
17. The method of claim 1 , wherein the n-gram is obtained based on a cluster of the semantic similarity graph selected by a user.
18. The method of claim 1 , wherein the n-gram is an expansion n-gram of another n-gram input by a user.
19. The method of claim 1 , further comprising:
determining expansion n-grams of a plurality of n-grams to form a plurality of adjustment n-gram sets; and
detecting and removing duplicate expansion n-grams of the plurality of adjustment n-gram sets.
20. The method of claim 1 , wherein:
the semantic similarity graph that comprises more than 10,000 nodes and more than 20,000 edges;
the semantic similarity graph is encoded as a square symmetric matrix having rows and columns corresponding to an ordered list of the documents and values corresponding to edge weights;
the documents have an average number of words greater than 200; and
determining adjusted weights or obtaining the semantic similarity graph comprises steps for reducing an amount of time spent shifting data back and forth between levels of a memory hierarchy.
21. The method of claim 1 , wherein selecting expansion n-grams based on the candidate n-gram scores comprises:
ranking the candidate n-grams by the candidate n-gram scores; and
selecting candidate n-grams in response to determining that the selected candidate n-grams satisfy a threshold ranking.
22. A system, the system comprising:
one or more processors; and
memory storing instructions that when executed by at least some of the processors effectuate operations comprising:
obtaining a semantic similarity graph that comprises more than 500 nodes and more than 1000 weighted edges, each node representing a document of a corpus, and each edge weight indicating an amount of similarity between a pair of documents corresponding to the respective nodes connected by the respective edge;
after obtaining the semantic similarity graph, obtaining a n-gram indicating a request that edge weights affected by the n-gram are to be increased or decreased;
expanding the n-gram to produce a set of expansion n-grams, wherein expanding the n-gram comprises:
determining which documents in at least part of the corpus contain the n-gram to form a first set of documents;
determining which documents in at least part of the corpus do not contain the n-gram to form a second set of documents, the first set of documents and the second set of documents each including more than 20 documents;
selecting a set of candidate n-grams from the first set of documents, the set of candidate n-grams having more than five n-grams;
determining an amount of times each candidate n-gram occurs in the first set of documents to form a first amount;
determining an amount of times each candidate n-gram occurs in the second set of documents to form a second amount;
determining, for each of the candidate n-grams, a candidate n-gram score based on the first amount and the second amount, wherein the candidate n-gram scores tends to increase or decrease as a ratio of the first amount to the second amount increases or decreases; and
selecting expansion n-grams based on the candidate n-gram scores, the expansion n-grams and n-gram collectively forming an adjustment n-gram set;
adjusting edge weights of the semantic similarity graph of edges between pairs of documents in which members of the adjustment n-gram set co-occur in response to determining that the respective documents contain a member of the adjustment n-gram set wherein the expansion n-grams are inferred to be conceptually related to the obtained n-gram indicating the request, and wherein the expansion n-grams cause the adjustment of edge weights to be a more comprehensive response to the request than an adjustment based solely on the obtained n-gram indicating the request; and
storing the adjusted weights in memory.
23. The system of claim 22 , wherein determining, for each of the candidate n-grams, a candidate n-gram score based on the first amount and the second amount comprises:
determining a ratio of a first value to a second value, the first value and the second value both being based on the first amount.
24. The system of claim 22 , wherein the first amount is based on both a count of a number of times the corresponding candidate n-gram appears in the first set of documents and a count of a number of n-grams in the first set of documents.
25. The system of claim 22 , wherein the second amount is a frequency based on a measure of central tendency of a number of n-grams in each of the second set of documents.
26. The system of claim 22 , wherein adjusting edge weights comprises:
obtaining a feature vector representation of each document, each feature vector indicating an amount of occurrences of respective n-grams in the respective document with respective cardinal values; and
for each of at least some of the feature vectors, selecting cardinal values of the respective feature vector correspond to n-grams in the adjustment n-gram set and adjusting the selected cardinal values.
27. The system of claim 22 , wherein the obtained graph is a semantic similarity graph comprising vectors as nodes and edges with weights,
the vectors being generated by:
generating, for each document of the corpus, a list of all the unique document n-grams occurring in the document;
counting, for each document of the corpus, the number of times each unique document n-gram occurs in the document and the number of times each unique document n-gram occurs in each of the other documents of the corpus to form a third count and a fourth count, respectively;
calculating, for each document n-gram, a document n-gram relation score;
removing from each list of each document of the corpus a portion of the lowest ranking document n-grams based on their respective document n-gram relation score; and
determining, for each document of the corpus, a vector based on the document n-gram relation score of each n-gram of the respective list,
wherein the weighted similarity comprises a similarity value that is based on angles between the vectors of two nodes and that is above a threshold.
28. The system of claim 22 , the operations comprising:
preparing instructions to form a graphical representation of a semantic similarity graph having the adjusted weights, the graphical representation being a force directed graph, wherein preparing the graphical representation comprises:
clustering the semantic similarity graph having the adjusted weights; and
extracting cluster topics from text of documents corresponding to at least some resulting clusters.
29. The system of claim 22 , wherein the n-gram is obtained based on a cluster of the semantic similarity graph selected by a user.
30. The system of claim 22 , wherein selecting expansion n-grams based on the candidate n-gram scores comprises:
ranking the candidate n-grams by the candidate n-gram scores; and
selecting candidate n-grams in response to determining that the selected candidate n-grams satisfy a threshold ranking.