Perface

This is the notes when I was reading A Three-Way Model for Collective Learning on Multi-Relational Data paper.

Introduction Notes

In this paper, the model learns relations mainly based on tensor factorization related to DEDICOM model.

Modelling and Notation Notes

The authors model the triples into a three-way tensor $\chi$, where two modes are concantenated entities and the third are relations.

• $\chi_{ijk} = 1$ indicates existing the relation $\text{(i-th entity, k-th predicate, j-th entity).}$
• $\chi_{ijk} = 0$ indicates non-existing and unknown relations.

$\text{Some Notations}$

• $\chi_k$ is the k-th frontal slice of the tensor $\chi$.
• $X(n)$ denotes the unfolding of the tensor $chi$ in mode $n$
• $A \otimes B$ refers to the Kronecker product of the matrices A and B
• $vec(X)$ is the vectorization of the matrix $X$
• Data is given as a $n \times n \times m$ tensor $\chi$, where $n$ is the number of entities and $m$ the number of relations.

Perface

This is the notes when I was reading Reading The Web with Learned Syntactic-Semantic Inference Rules paper.

Terminology and Notation Notes

• $C$ is a set of entities, $R$ is a set of relations, $T$ is a set of triples, $T \subseteq C \times R \times C$.
• $(c, r, c^{‘})$ is the triple. Each triple represents an instance $r(c, c^{‘})$ of the relation $r \in R$
• $r^{-1}$, the inverse relation $r(c, c^{‘}) \Longleftrightarrow r^{-1}(c^{‘}, c)$, e.g. $Parent^{-1} = Children$
• $\pi = $ is the path type. For example,:
• “the persons who were born in the same town as the
  query person” $\rightarrow$ $\pi_{1} : $
• “the nationalities of persons who were born in the same town as the query person” $\rightarrow$ $\pi_{2} : $

Perface

This is the notes when I was reading Relation Extraction with Matrix Factorization and Universal Schemas paper.

Introduction Notes

semantic equivalence？
surface pattern relations？

Model Notes

• Inspired from collaborative filtering
• Matrix Factorization
• $R$ is the set of relations
• $T$ is the set of input tuples (entity pairs)

Predict the probability of $$. $r \in R, t \in T$

Using a natural parameter $\theta_{r, t}$ and the logistic function

Perface

This is the notes when I was reading Representing Text for Joint Embedding of Text and Knowledge Bases paper.

Introduction Notes

This paper was based on jointly learning continuous representations for knowledge base and textual relations by Riedel et al. [1]. The textual relations of two entities were extracted by the lexicalized dependency path. The previous work made textual relation learn its continuous latent representation from the pattern of its co-occurrences in the knowledge graph.

前言

《Text-Augmented Knowledge Representation Learning Based on Convolutional Network》阅读笔记

Introduction Notes

Knowledge Graphs have the relationship triples (subject, relation, object) denoted as (h,r,t), which are useful for IR tasks.

KGs completion or link prediction

Some research focused on the knowledge graph completion or link prediction task which aims to predict missing triples in KGs.

• $\text{Rescal model}$: Matrix decomposition for knowledge representation learning.
• $\text{DistMult model}$: Set relation matrix as diagonal matrix; Use “circular correlation” of the head and tail entity vectors to represent the entity pair.
• $\text{ConvE model}$: The first model applying convolutional neural network for the knowledge graph completion task.
• $\text{ConvKB model}$: Apply a convolutional neural network to calculate the fraction of the input triples.

前言

因为研究生要开始做知识图谱相关的项目了，因此记录一下阅读论文的过程。此文也借鉴了一下知乎上的一些阅读笔记知乎阅读笔记

Perface

This is the notes when I was reading Knowledge Graphs cookbook paper.

Introduction notes

Since 2012, the modern incarnation of the phases “Knowledge Graph” begins at 2012 announcement of the Google Knowledge Graph. Graphs could provide the abstraction for a variety of domains.

Some Definitions

• $\text{Node}$: The nodes of the graph represent related entities.
• $\text{Edge}$: Capture the (potentially cyclical) relations between the entities.

题目列表

1. 寻找两个正序数组的中位数 5. 最长回文子串 15. 三数之和

4. 寻找两个正序数组的中位数

这个题被标记为困难主要是因为需要实现$O(log(m+n))$的解法，我最开始想到的是$O(log(m+n))$的解法，就是利用双指针，不过不是最优解，更适合合并正序数组，最优解法是看了官方的题解才会的，官方的题解解释的比较好一些。

双指针

双指针法的思路很简单，因为是两个正序数组嘛，所以知道两个数组长度，中位数在第几小的位置一定能看的出来。就开始利用两个指针，每次比较两个数组指针位置元素的大小，谁小就指针向前移动并计数，把元素加入列表中。当进行到$\frac{len(nums1) + len(nums2)}{2} + 1$的位置时，这时对于总长为奇数的数组来说，列表的最后一个元素就是中位数，取出即可。对于总长为偶数的数组来说，列表的最后一个元素和倒数第二个元素就是中位数，全部取出求均值即可。因为遍历一半两个数组，因此时间复杂度是$O(m + n)$

简述

k近邻算法主要思想就是根据给定的距离度量方法，在训练集中找到与目标点最近邻的k个点，在这k个点中根据决策规则（通常是多数表决）决定目标点的类别。

距离度量

$L_p$距离（$L_p$ distance）

假设$x_i, x_j \in \textbf{R}^n$，$x_i = (x_i^{(1)},x_i^{(2)},\dots, x_i^{(n)})^T$，$x_j = (x_j^{(1)},x_j^{(2)},\dots, x_j^{(n)})^T$

则$L_p$距离的定义为

当$p=1$时，称为曼哈顿距离(Manhattan distance)

题目列表

1. 两数之和 2. 两数相加 3. 无重复字符的最长子串

1. 两数之和

暴力循环

最简单的方法是使用暴力循环的方法，时间复杂度为$O(n^2)$。

1
2
3
4
5
6
7
8

class Solution(object):
def twoSum(self, nums, target):
    if len(nums) == 0:
        return []
    for i in range(len(nums) - 1):
        for j in range(len(nums) - i - 1):
            if (nums[i] + nums[i + j + 1] == target):
                return [i, i + j + 1]

利用字典特性实现哈希查表

较优解是利用python字典来当作hash表，从而使时间复杂度为$O(n)$。

简述

由于首先接触到的是支持向量机，因此，感觉感知机算法就像是一个弱化版的支持向量机。在学习书中内容时，对对偶形式的解释进一步加强了我的理解，明白了向量内积矩阵对于算法加速的意义。

感知机模型

感知机模型属于判别模型，目的是寻找可以将特征空间的训练数据集分为正负两类的超平面。在公式中，$x$代表输入向量， $w$代表权重向量（$weight$），$b$代表偏差（$bias$）。$sign$函数代表超平面将数据集划分为正负两类。

对于感知机模型来说，训练数据集必须是线性可分的，这样才存在超平面解。其次，分离平面也不是唯一的。由于采用随机梯度下降的方式，学习时数据的顺序也会导致超平面的变化。