算法博弈论 W47 Congestion games, potential functions
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 ...
计算几何 W46 More Orthogonal problems
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 ...
计算机视觉 W46 Visualizing and understanding CNNs
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 ...
算法博弈论 W46 Non-atomic selfish routing and price of anarchy
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 ...
计算几何 W45 Orthogonal Range Searching
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 ...
计算机视觉 W45 Generative models
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 ...
算法博弈论 W45 Mechanism design without money
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 ...
计算几何 W44 Arrangements and Duality, Zone Theorem
Duality there is a 1-to-1 mapping between points and non-vertical lines map every point p to a line: p∗:y=pxx−pyp^*:y=p_xx-p_yp∗:y=pxx−py, p∗∗:y=pxx+pyp^{**}:y=p_xx+p_yp∗∗:y=pxx+py every line l:y=ax+bl:y=ax+bl:y=ax+b to a point l∗=(a,−b)l^*=(a,-b)l∗=(a,−b). claim: if ppp is on(below/above) l⇔l∗l\Leftrightarrow l^*l⇔l∗ is on(below/above) p∗p^*p∗. Proof: p(px,py),l:y=ax+bp is on l⇒py=apx+bl∗(a,−b),p∗:y=pxx−pywe plug l∗ into p∗:pxa−(−b)=apx+b=pyQ.E.D.p(p_x,p_y),l:y=ax+b\\ \text{p is on l}\Rig ...
德语学习 B2 Kapitel 2 Sprich mit mir!
Inhalt Gesten sagen mehr als tausend Worte … Sprachen kinderleicht?! Smalltalk - Die Kunst der kleinen Worte Wenn zwei sich streiten 2-1 Sprich mit mir verbale Kommunikation und nonverbale Kommunikation 语言交际和非语言交际 非语言交际的方式 Gesichtsausdruck 面部表情 Mimik Körperhaltung und Körperbewegung 体态和动作 Berührung 触摸 räumliche Distanz 空间距离 stimmliche Merkmale 声音特征: Tonfall 语调, Sprechgeschwindigkeit 语速, Betonung 重音, Pause 停顿 usw. demütig 恭顺的，谦虚的 leidend 虚弱的 hochnäsig 自大的，目空一切的，傲慢的 das Piktogramm-e 形象符号，标志牌 ...
计算机视觉 W44 Object detection and segmentation
Object localization Classification + Localization: ImageNet 1000 classes each image has 1 class and at least one bounding box 800 training images per class in the competition, algorithm should produce 5 (class, box) predictions correct if at least one prediction has the correct class and a bounding box with at least 0.5 intersection over union IoU Evaluation mean average precision mAP compute average precision separately for each class, then average over classes. a detection is a true positiv ...
