Bob Kasenchak and Ahren Lehnert, Synatpica

The theme of last week’s class in the ongoing free-to-attend Stanford Knowledge Graph course was “What is the role of knowledge graphs in machine learning?” and featured points of view from computer science, e-commerce, and (surprisingly) psychology.

Video of the session can be found here.

——————————————————————————————————–

Jure Leskovec, Stanford

Reasoning Over Knowledge Graphs in Vector Space using Embeddings

Leskovec’s talk described a novel method for querying graphs based on mapping graph representations to n-dimensional Euclidean space for faster and more accurate reasoning and queries. The method, called Query2Box, purports to be effective in querying graphs that have incomplete or noisy data.

Essentially, the argument goes, knowledge graphs contain entities connected by different types of relations: heterogeneous graphs with facts represented by triples, but since such graphs are notoriously incomplete, the task is to use machine learning  to insert or predict missing relations to allow better queries.

Traditional graph querying traverses nodes to find answers using existing information and infer new triples; however, this presents difficulties, namely:

  • Knowledge graphs are often very heterogeneous, comprising many linked and disparate sources
  • Large graphs often have lots of noise
  • Large graphs are often incomplete, missing crucial links or data
  • Large graphs can be very, very massive so traversing them does not always scale
  • In order to be effective, queries need to be fast

So a key challenge of graph querying is that big graphs can involve noisy relations and unobserved data; Query2Box aims to solve this by using representation learning to map a graph into a Euclidean space (of as many dimensions as necessary) and “learn to reason in that space.”

Without getting into the details (assuming we understood them) the process looks much like clustering-type analysis based on set theory; in any event, the benefits of this type of query structure are:

  • Scalability and efficiency: Any query can be reduced to a couple of matrix operators
  • Generality: Any arbitrary query (even those never seen during training) works
  • Robustness to noise: A graph can contain missing and noisy relationships and still produce accurate results

Leskovec’s talk concluded with some demonstrations of queries over deliberately incomplete datasets with convincing results. As the size of graphs discussed is often massive in scope it’s interesting to see solutions grapple with issues of scale like this.

——————————————————————————————————–

Luna Dong, Principal Scientist, Amazon Product Graph team

Knowledge Graphs and Machine Learning: A Natural Synergy

Amazon is doing a lot of work on graphs, and Dong began by asking, “what is the role of knowledge graphs in machine learning?” with a tripartite answer:

  1. A knowledgeable search engine returns better answers: entering “stanford president” in Google returns the right card with accurate information;
  2. A knowledgeable personal assistant (in this case, Amazon Alexa) gets more things done: it has to know what the latest Taylor Swift song is;
  3. In e-commerce, a knowledgeable recommender makes better recommendations: tracks trends and buying patterns..

In order to achieve this, a graph must be able to absorb sources, align information from disparate sources, and separate useful information from the sea of data that’s available. Machine learning is well-suited to assist with some of these tasks:

  • Knowledge extraction (data extraction, text mining etc.)
  • Knowledge alignment )entity linkage, schema mapping, ontology alignment, etc)
  • Knowledge cleaning (data cleaning, anomaly detection, knowledge fusion etc.)
  • Knowledge mining, KG-based search and QA (graph mining, knowledge embedding, search, question answering)

To this end, the Amazon Product Graph team currently consists of 50 people (including 13 scientists and 10 interns) managing three graphs, with the mission to be able to “answer any question about products and related knowledge in the world.”

Dong went on to outline some of the differences between product graphs and knowledge graphs, followed by “Ten Challenges in Building and Using a Product Knowledge Graph.”

  1. A vast unknown space: What are the types and relationships you need to model? How can you build the underlying ontology if you don’t have complete entity types and relationships when you begin?
  2. Too little structured data: limited structured data is available as retailers are not trained to provide structured information so it’s all packed into unstructured text
  3. Abundant but heterogeneous data: publishers (for example) provide structured data but schemas and formats are different, entities are named in different ways, and there is no consistent data delivery format; in addition, entities are named in various ways and need to be resolved.
  4. Data, Data Everywhere: for example, web pages describing movies have lots of information (semi-structured information), again in different schemas, so multi-model information extraction algorithms are required.
  5. Non-trustworthy data: how can we decide what is correct when information is different from different sources? This requires data cleanup and validation.
  6. A working solution may not scale up! 100,000 product categories require potentially 100K different models (different value vocabularies, attributes, etc.)
  7. Never-Ending Requirements for Training Data: different categories have different characteristics, distribution, and sources so it’s a challenge to get good training data for every scenario; possible solutions include active learning, weak learning, and Learn with Limited Labels (LLL).
  8. Find the Needle in the Hay(stack): how to deliver relevant results, related products, and provide useful ways to narrow search results? This requires understanding user needs and parsing search queries to extract critical information and, conversely, eliminate less-important information for query relaxation.
  9. From Facts to Insights: Graphs are good for random walks, and random walks with supervision help identify important patterns.
  10. Can you explain it?: Why did someone who bought [some specific] lamp also purchase [some specific] chair? Is it possible to form paths (perhaps using random walks, again) to find patterns that are explainable and predictable?

Dong concluded by noting that building and using a knowledge graph involves tons of research problems from many research areas; at Amazon, this work involves building a product graph and using web knowledge extraction techniques for both products and Alexa.

——————————————————————————————————–

Robert Hoffman. Institute of Human and Machine Cognition

Challenges for Explainable AI

Hoffman’s background is in psychology, and he advocates for the union of computer science and experimental psychology to foster better processes for explaining machine learning and artificial intelligence systems.

Hoffman began by outlining what he calls “word misuse”: the borrowing of terms from ordinary language and giving them a technical meaning that is orthogonal to the everyday meaning, the result of which he declared to be “cross-disciplinary disconnects and a confused general public.”

The problem to be solved is that there is no current good practice for explaining ML and AI models and outcomes; for example, “why did this recommendation algorithm recommend me these movies?” is not an easily answerable question. Why do ML systems seem to come up with answers (recommendations, for example) that defy all common sense? We assume that we have built some kind of “meaning” or “understanding” into a system, but this is an anthropomorphic fallacy that is widely misunderstood.

Hoffman said that people assume explanations are statements or diagrams, but they’re not: “Explaining is a process.” Further, what a researcher thinks is a good explanation may not be good for a user; most things that are touted as “explanations” for ML processes are really just cues or clues, and the user still has to self-explain.

Hoffman proposes solutions based around user involvement: being able to ask and answer questions, for example, about why the system behaves a certain way, recommended ways of using it, or understanding what it will do next. Putting the user (as opposed to the researcher or the project) at the center of the design from the beginning (via things like usability testing) as part of the design process, instead of tacking them on at the end, is critical to his proposed methodology.

To close, Hoffman exhorted the class that “knowledge graphers [sic] need experimental psychologists!”

——————————————————————————————————–

Only two sessions remain and we’ll be updating the blog again after each.

You can follow Bob and Ahren on Twitter.

Bob Kasenchak @TaxoBob

Ahren Lehnert @AhrenLehnert

You can read the full series of blogs on the Stanford University Knowledge Graphs course here.

%d bloggers like this: