min hjemmeside

Cut games Graph G=(V,E)G=(V,E)G=(V,E) with weight wew_ewe​ on each edge e∈Ee\in Ee∈E. Every node corresponds to a player. Two strategies per player/node vvv: To put vvv at the left or right side of the cut Cut(S)Cut(S)Cut(S): the set of edges with their endpoints on different sides of the cut at a state SSS payoffi(S)=∑e∈Cut(S)∩Niwe\text{payoff}_i(S)=\sum_{e\in Cut(S)\cap N_i}w_e payoffi​(S)=e∈Cut(S)∩Ni​∑​we​ A pure Nash equilibrium was found. 带权图的最大割 Maximum cut Cut games are potential game ...

Voronoi Diagrams nnn points p1,⋯ ,pnp_1,\cdots,p_np1​,⋯,pn​. Nearest neighbor problem 举一个具象化的例子： nnn post offices Find the closest post office For which region, point pip_ipi​ is the closest point? What is the region that pip_ipi​ servies? （对于二维空间使用欧几里得距离定义的距离）两个最近点对连线线段的中垂线就是分界。 Definition of Voronoi Diagrams A set PPP of nnn points p1,⋯ ,pnp_1,\cdots,p_np1​,⋯,pn​ decomposition of R2\mathbb R^2R2 into regions R1,⋯ ,RnR_1,\cdots,R_nR1​,⋯,Rn​. for any q∈Riq\in R_iq∈Ri​, pip_ipi​ is the closes ...

Sequence Models sequence models are the machine learning models that input or output sequences of data sequential data includes text streams, audio clips, video clips, time-series data etc. NLP technology to handle human language using computers aid human-human communication and/or human-machine communication analyze/understand text (syntactic analysis, text classification, named entity recognition, building knowledge graphs). Language model ≈ next word prediction P(X=sentence)=∏i=1tP(xi∣x1 ...

Atomic selfish routing 3 players: strategies: connect source sis_isi​ with destination tit_iti​. Assuming that all edges have latency functions ce(x)=xc_e(x)=xce​(x)=x how do the players act? 肯定尽量选不挤的路径。 Load balancing games Every player has a job and wants to assign it to some machine so that its completion time is minimized mmm parallel machines Machine jjj has speed σj\sigma_jσj​ If machine jjj gets xxx jobs, the latency/cost experienced by each of the players/owners of these jobs is xσj ...

Kd-Trees Problem set given a set PPP of nnn points in R2\mathbb R^2R2 store PPP in a data structure s.t. given a query rectangle RRR, we can find the points in RRR efficiently. idea generalize BST to R2\mathbb R^2R2 every node vvv corresponds to a rectangular region SvS_vSv​; the points in the subtree of vvv lie in SvS_vSv​. Build Kd-Tree BuildKDTree(P,dP,dP,d) if P={p}P=\{p\}P={p} then return a leaf node representing ppp. if ddd is even then partition PPP into P1,P2P_1,P_2P1​,P2​ usin ...

Why visualizing The inner workings of ConvNets After training, each layer progressively extracts higher and higher-level features of the image, until the final layer essentially makes a decision on what the image shows. early layers: features like “corners” and “blobs” late layers: semantic like “wheel” and “door”. assemble features into complete interpretations Motivation why visualize CNN? Debugging with neural networks we have little insight about learning and internal operation through v ...

Today we start to consider other topic than mechanism design. Review of Braess’ paradox A road network for sending traffic from location sss to location ttt Latency of the long wide road: 111 hour Latency of the short narrow road: xxx hours, where xxx is the fraction traffic graph TD 1((S)) 2((T)) 3((A)) 4((B)) 1-->|short narrow road|3 1-->|long wide road|4 3-->|long wide road|2 4-->|short narrow road|2 Travel time: 1.51.51.5 hours 因为均衡：左边多了会有人到右边，右边多了会有人到左边 If autho ...

Orthogonal Problems aka 正交问题 input: set PPP of nnn points goal: process PPP in a DS​ query: axis-aligned rectangle rrr orthogonal range counting: number of points in rrr orthogonal range reporting: list of points in rrr 3-sided queries: 3 boundaries Rectangle stabbing aka 穿刺矩形 input: set PPP of nnn rectangles goal: process PPP in a DS query: a point qqq output: list of rectangles containing qqq 1D Orthogonal Range Searching input: set PPP of nnn points in 1D goal: process PPP in a DS query: a ...

Unsupervised learning regression vs. classification why unsupervised learning? few of data are labeled pre-train an unsupervised model anomaly detection - learn what data distribution typically looks like cheaper than supervised learning Generative models a generative model is a class of statistical model that contrasts with discriminative models. informally discriminative model - classifier data∼pdata(x)\text{data}\sim p_{data}(x)data∼pdata​(x) generative model - generate new data instance ...

last lecture about mechanism design mechanism without money? kidney exchange and stable matching Kidney exchange patients with a final stage kidney disease in the waiting list for kidney transplant by a deceased donor. 已故捐献者肾移植等候名单中患有末期肾病的患者。 98k in the US, 800 in Denmark demand>>supply! Transplantations from living donors 活体移植 e.g. transplantation from mother to child unfortunately, such transplantations are allowed between relatives and are not always possible Incompatibilities of bloo ...