崔添翼 § 翼若垂天之云

• Making Recommendations (Collaborative Filtering)
• User-based
• Finding similar users
• User as vector based on item score
• Euclidean distance
• Pearson correlation
• Reverse users and items, we can find similar items to a given item
• Sort and recommend items based on
• sum(user similarity * user’s item score) for each other user
• Item-based
• Find item similarities
• These results can be cached and periodically updated
• Sort and recommend items based on
• sum((item similarity * user’s item score) / sum(item similarity)) for each user’s item
• Significantly faster and better for sparse dataset

• Discovering Groups (Clustering)
• Supervised Learning
• use example inputs and outputs
• neural networks, decision trees, support-vector machines, and Bayesian filtering
• Word Vectors of texts
• Hierarchical Clustering
• choose two nearest vectors to combine
• results in binary tree
• Can cluster articles or words
• transpose the matrix
• Dendrogram drawing
• K-Means clustering
• randomly place k centroids
• assign every item to the nearest centroid, and move the centroid to the average location of all items assigned to them

• Searching and Ranking
• word index stored in relational database
• ranking
• content-based
• various metrics: word frequency, document location, word distance
• use inbound links
• simple count
• PageRank algorithm
• random walk
• sparse matrix multiplication iterations
• use link text
• learning from clicks
• click-tracking neuro-network (multilayer perception network, i.e. MLP network)
• one hidden layer
• Optimization
• stochastic optimization
• numerical solution
• cost function
• random searching
• hill climbing
• increase the most promising dimension of a vector
• simulated annealing
• variable: temperature, starts very high and gradually gets lower
• worse solution being accepted depending on temperature
• generic algorithms
• mutate, crossover, …
• Document Filtering (to be expanded…)
• use words as features
• naive Bayesian classifier
• the Fisher method
• Modeling with Decision Trees
• Algorithm: CART (Classification and Regression Trees)
• choose the best split from all possible splits
• Gini impurity
• information entropy
• sum of p(x)log(p(x))
• recursively build the whole tree
• then can be used to classify new observations
• pruning the tree
• when it becomes overfitted
• checking pairs of nodes that have a common parent to see if merging them would increase the entropy by less than a specified threshold
• Dealing with
• missing data
• use both branches
• numerical outcomes
• use variance instead of entropy
• Building Price Models
• k-nearest neighbors (kNN)
• weighted
• may need scaling or normalizing
• to estimate the probability density
• cross-validation
• divide data into training sets and test sets
• Advanced Classification: Kernel Methods and SVMs
• basic linear classification
• using dot-products to determine distance
• kernel methods
• define another dot-product == move the points into different space
• support-vector machines
• find the line that is as far away as possible from classes
• Finding Independent Features
• non-negative matrix factorization
• factor the article-word matrix into two matrix
• the features matrix: row for features, column for words
• the weight matrix: row for articles, column for features
• Evolving Intelligence
• creating an algorithm that creating algorithms
• mutation, crossover/breeding
• use trees to represent algorithm to enable evolving
• use to guess numerical functions or, game AI
• Algorithm Summary
• Supervised Learning
• Bayesian Classifier
• Decision Tree Classifier
• Neural Networks
• Support-Vector Machines
• Unsupervised Learning
• k-Nearest Neighbors
• Clustering
• Multidimensional Scaling
• Non-Negative Matrix Factorization
• Optimization

（本文是 http://llvm.org/releases/2.9/docs/LangRef.html 的阅读笔记，前作为《LLVM笔记(2)：LLVM的语言（中）》。）

• Instruction Reference
• terminator instruction
• indicates which block should be executed after the current block is finished
• yields ‘void’ value,
• ret (return)
• ret <type> <value>
• ret void
• branch
• br i1 <cond>, label <iftrue>, label <iffalse>
• br label <dest> ; Unconditional branch
• switch <intty> <value>, label <defaultdest> [ <intty> <val>, label <dest> ... ]
• indirectbr <somety>* <address>, [ label <dest1>, label <dest2>, ... ]
• invoke
• invoke [cconv] [ret attrs] <ptr to function ty> <function ptr val>(<function args>) [fn attrs] to label <normal label> unwind label <exception label>
• unwind
• unreachable
• binary instruction
• add, fadd, sub, fsub
• mul, fmul, udiv, sdiv, fdiv, urem, srem, frem
• bitwise binary instructions
  • shl, lshr, ashr
  • and, or, xor
• memory instructions
• Vector Operations
• extractelement
• <result> = extractelement <n x <ty>> <val>, i32 <idx> ; yields <ty>
• insertelement
• <result> = insertelement <n x <ty>> <val>, <ty> <elt>, i32 <idx> ; yields <n x <ty>>
• shufflevector
• <result> = shufflevector <n x <ty>> <v1>, <n x <ty>> <v2>, <m x i32> <mask> ; yields <m x <ty>>
• Aggregate Operations
• extractvalue
• <result> = extractvalue <aggregate type> <val>, <idx>{, <idx>}*
• insertvalue
• <result> = insertvalue <aggregate type> <val>, <ty> <elt>, <idx> ; yields <aggregate type>
• Memory Access and Addressing Operations
• alloca
• <result> = alloca <type>[, <ty> <NumElements>][, align <alignment>] ; yields {type*}:result
• load
• <result> = load <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>]
• <result> = volatile load <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>]
• !<index> = !{ i32 1 }
• store
• store <ty> <value>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>] ; yields {void}
• volatile store <ty> <value>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>] ; yields {void}
• getelementptr
• <result> = getelementptr <pty>* <ptrval>{, <ty> <idx>}*
• <result> = getelementptr inbounds <pty>* <ptrval>{, <ty> <idx>}*
• Conversion Operations
• trunc .. to (truncate value type)
• zext .. to (zero ext)
• sext .. to (sign ext)
• fptrunc .. to (float point truncate)
• fpext .. to
• fptoui .. to (float point to unsigned int)
• fptosi .. to
• uitofp .. to
• sitofp .. to
• ptrtoint .. to (pointer to int)
• inttoptr .. to
• bitcast .. to
• other instructions
• ‘icmp’ Instruction
• <result> = icmp <cond> <ty> <op1>, <op2> ; yields {i1} or {<N x i1>}:result
• Intrinsic Functions
• Variable Argument Handling Intrinsics
• llvm.va_start
• llvm.va_end
• llvm.va_copy
• Accurate Garbage Collection Intrinsics
• llvm.gcroot
• llvm.gcread
• llvm.gcwrite
• Code Generator Intrinsics
• llvm.returnaddress
• declare i8 *@llvm.returnaddress(i32 <level>)
• llvm.frameaddress
• declare i8* @llvm.frameaddress(i32 <level>)
• llvm.stacksave
• declare i8* @llvm.stacksave()
• llvm.stackrestore
• declare void @llvm.stackrestore(i8* %ptr)
• llvm.prefetch
• declare void @llvm.prefetch(i8* <address>, i32 <rw>, i32 <locality>)
• llvm.pcmarker
• declare void @llvm.pcmarker(i32 <id>)
• llvm.readcyclecounter
• declare i64 @llvm.readcyclecounter()
• Standard C Library Intrinsics
• llvm.memcpy llvm.memmove llvm.memset.*
• llvm.sqrt.* llvm.powi.* llvm.sin.* llvm.cos.* llvm.pow.*
• Bit Manipulation Intrinsics
• llvm.bswap.*
• swap high and low
• llvm.ctpop.*
• counts the number of bits set
• llvm.ctlz.*
• count the number of leading zeros
• llvm.cttz.*
• count the number of trailing zeros
• llvm.sadd.with.overflow.*
• llvm.uadd.with.overflow.*
• llvm.ssub.with.overflow.*
• llvm.usub.with.overflow.*
• llvm.smul.with.overflow.*
• llvm.umul.with.overflow.*
• Half Precision Floating Point Intrinsics
• llvm.convert.to.fp16
• llvm.convert.from.fp16
• Debugger Intrinsics
• start with llvm.dbg. prefix
• Exception Handling Intrinsics
• start with llvm.eh. prefix
• Trampoline Intrinsic
• llvm.init.trampoline
• Atomic Operations and Synchronization Intrinsics
• llvm.memory.barrier
• llvm.atomic.cmp.swap.*
• llvm.atomic.swap.*
• llvm.atomic.load.add.* llvm.atomic.load.sub.*
• llvm.atomic.load.and.* llvm.atomic.load.nand.* llvm.atomic.load.or.* llvm.atomic.load.xor.*
• llvm.atomic.load.max.* llvm.atomic.load.min.* llvm.atomic.load.umax.* llvm.atomic.load.umin.*
• Memory Use Markers
• llvm.lifetime.start
• llvm.lifetime.end
• llvm.invariant.start
• llvm.invariant.end
• General Intrinsics
• llvm.var.annotation
• llvm.annotation.*
• llvm.trap
• llvm.stackprotector
• llvm.objectsize

（本文是 http://llvm.org/releases/2.9/docs/LangRef.html 的阅读笔记，前作为《LLVM笔记(0)：在一切开始之前》。）

• 一句话总结： LLVM is a Static Single Assignment (SSA) based representation that provides type safety, low-level operations, flexibility, and the capability of representing ‘all’ high-level languages cleanly. It is the common code representation used throughout all phases of the LLVM compilation strategy.
• LLVM语言有三种形式：in-memory compiler IR, on-disk bitcode representation, human readable assembly language representation。三种表现形式是等价的。
• LLVM语言的目标是：一方面 light-weight and low-level，另一方面expressive, typed, and extensible。
• “universal IR”
• Identifiers
• global: @开头
• local: %开头
• ‘;’开始注释
• High Level Structure
• Module
• llvm linker to combine
• global values: functions and global variables
• linkage types
• private, linker_private, linker_private_weak, linker_private_weak_def_auto
• internal, available_externally, linkonce, weak, common, appending, extern_weak
• linkonce_odr, weak_odr
• externally visible (default)
• Calling Conventions
• ccc: the C calling convention
• fastcc: the fast calling convention
• coldcc: the cold calling convention
• Visibility styles (for global variables and functions):
• default, hidden, protected
• Named types
• e.g. %mytype = type { %mytype*, i32 }
• Global variables
• many aspects can be controlled
• Functions
• definition and declaration
• definition contains a list of basic blocks, Control Flow Graph for the function
• each basic block optionally starts with a label, contains a list of instructions, and ends with a terminator instruction
• first basic block is special: 1. immediately executed on entrance; 2. not allowed to have predecessors
• Aliases
• Named Metadata: a collection of metadata
• Parameter Attributes
• zeroext, signext, inreg, byval, sret, noalias, nocapture, nest
• Garbage Collector Names
• Function Attributes
• …
• Module-Level Inline Assembly
• Data Layout
• target datalayout = “layout specification”
• Pointer Aliasing Rules
• memory access must be through pointers
• a pointer value is based on another pointer value according to the rules
• Volatile Memory Accesses