数据挖掘 11 Frequent Subgraph Mining
A labeled graph is a triple G=(V,E,ℓ)G=(V,E,\ell)G=(V,E,ℓ) where ℓ:V∪E→L\ell:V\cup E\rarr Lℓ:V∪E→L is a labeling function assigning a label from a set of labels LLL to each node and each edge. Definition of frequency: it is encoded into a support measure that return the number of occurrences of the subgraph in the graph. FSM in Graph Collections A graph collection aka a graph database is a set D={G1,G2,⋯ ,Gn}\mathcal D=\{G_1,G_2,\cdots,G_n\}D={G1,G2,⋯,Gn} of labeled graphs Gi=(Vi,Vi,ℓi),i∈[1 ...
随机算法 10 Invertible Bloom Filters
Brief Introduction Invertible Bloom Lookup Table (abbr. IBLT) a fancy hash-table stores key-value pair (x,y)(x,y)(x,y) space budget: ttt Guarantee It “works” when the number of key-value pairs, nnn, in table has n≤tn\le tn≤t. “temporarily” stops working if n>tn\gt tn>t. starts working again if nnn drops below ttt. Operations (x,y) is key-value pair. insert(x,y), delete(x,y), get(x), listentries. Details Start with table with k≥3k\ge3k≥3 rows, m=2×tm=2\times tm=2×t columns. In each row, ...
丹麦 IT 学生工求职记（已接 offer 版）
Kdag (Katrinebjerg Karrieredag) 2024 2024 年 4 月 12 日，期待已久的 Kdag 😍 在 Katrinebjerg AUDatalogi 的 Nygaard 楼，一年一度🎆 总共有 54 家企业/单位，针对 IT 的岗位信息交流会。我认得的企业也就 乐高、Arla（乳制品垄断企业，经常喝这家的牛奶）、Uber。 也有跟国防有关的企业，看宣传资料像是给 F35 战机生产零部件的企业，反正 in collaboration with Lockheed Martin （一眼不招非 EU 国籍的） 有些企业是针对丹麦本地的生意，或者员工大部分是丹麦人的。这种企业的宣传资料上只有丹麦语的，也可以直接跳过了。所以想在丹麦有更多的工作机会，需要学好丹麦语😭 还有就是，说 danish is not mandatory, but highly recommended 的，那就是 mandatory 的意思。 为什么我喜欢这样的活动 可以白嫖吃的喝的，谁不喜欢啊？😍😍😍 目标 主要是有 Student Job 岗位的企业，狠狠地投简历 ...
数据挖掘 10 Graph Neural Networks
GNN - graph neural networks Intuition: how to propagate information over the neighbors in a non-linear manner. Graph Embeddings as Matrix Factorization Linear embeddings correspond to SVD of the similarity matrices chosen in the objective. For adjacency-based similarity, the best linear ddd-dimensional embedding corresponds to the projection of the dataset into the ddd directions associated to the top-ddd singular values: if SVD(A)=UΣV⊤then the embedding matrix Z=UdΣd\text{if }SVD(\mathbf A)=\m ...
随机算法 9 Prophets, Secretaries and Martingales
First part of lecture notes on prophet inequality and secretary problem is by Anupam Gupta (CMU) Prophet inequalities and Secretary problems are 2 classes of problem where online decision-making meets stochasticity: in the first set of problems the inputs are random variables, whereas in the second one the inputs are worst-case but revealed to the algorithm (aka decision maker) in random order. Here are some results, proofs and techniques about them. The Prophet Inequality 在之前的算法博弈论课上学过，具体可以参考我 ...
德语学习 B2 Kapitel 5 Wer Wissen schafft, macht Wissenschaft
Inhalt Wissenschaft für Kinder Wer einmal lügt, … Ist da jemand? Gute Nacht! 5-1 Wer Wissen schafft, macht Wissenschaft verschlafen 因睡觉而耽误；睡眠过度 die Längeneinheit-en 长度单位 das/der Millimeter 毫米 das/der Femtometer 飞米 1 飞米 = 10-15 米 das/der Nanometer 纳米 der Benzinmotor-en 汽油引擎 der Speck-e 皮下脂肪；腌肉，熏肉 die Lebenserwartung 预计寿命 die Mücke-n 蚊子 der Flügel- 翅膀 5-2 Wissenschaft für Kinder (1) lenken 操纵，控制 gespannt 集中注意力的 bestmöglich 尽可能好的 ausgewechselt 判若两人的 jmdm an den Lippen hängen 仔细听某人，集中注意力听某人 die ...
Fair Division 6 Computing EF1 + PO
Objective: Investigate methods for computing allocations satisfying both EF1 and PO. Activities: Review the paper Finding Fair and Efficient Allocations. Caragiannis et al has established the result: for additive valuations, there always exists an allocation that is EF1 + PO by maximizing Nash Social Welfare. However, computing MNW is NP-Hard. This paper: develop a pseudo-polynomial time algorithm for finding EF1 + PO. When valuations are bounded, the algorithm is polynomial time. For additive ...
丹麦语 DU 3.2 7-8 Sundhed og livsstil
读音辨析 hun - hund man - mand - men - mænd 不加 清音 d 的时候，读的舒缓一点，加了 d 的单词需要读快一点，狠一点 Selvom 中的 v 不发音 en have / haven 花园 et hav / havet 大海 en havn / haven 港口 at have 有 Kirsten har et jernhelbred helbred 健康 通常指一个人的身体健康或心理健康状况 f. eks. Min son har et godt helbred. jernhelbred “铁打的”健康身体 rask 健康的，充满活力的 bl.a. = blandt andet 除其他事项外 hygge sig 找乐子 er fuld af energi 充满了能量 i god form 保持好身材 cerut -ten - ter -terne 香烟 sundhed 健康 涵盖了健康的各个方面，包括生活方式、饮食、运动等 Hvad gør du for at holde dig rask? 为了保持健康，你会做啥？ Hvad gør ...
数据挖掘 9 Graph Embedding
Main problem with graphs: lack of predefined node ordering. Graph is non-Euclidean: the distance among two nodes does not depend on the coordinates of the nodes. Origin idea of graph embedding: graph could become a set of multi-dimensional points in which Euclidean distances represent similarities among the nodes. 2 methods of embedding: Linear embedding: linear transformation of the edges. Random-walk embedding: preserving the probability that a node is reachable from another node. Linear Em ...
Fair Division Conjectures on Price of Fairness for EEFX/MXS
After reading the paper Optimal Bounds on the Price of Fairness for Indivisible Goods to know the notion of Price of Fairness and the paper New Fairness Concepts for Allocating Indivisible Items to adapt new fairness notions EEFX and MXS, it is natural to consider the left open problem: What is the PoF for EEFX and MXS? The Relation between EFX, EEFX, MXS, PROP1 It is not hard to say that EFX⊂EEFX⊂MXS⊂PROP1EFX\sub EEFX\sub MXS\sub PROP1 EFX⊂EEFX⊂MXS⊂PROP1 Every EFX allocation is EEFX allocatio ...
