Thứ Hai, 23 tháng 3, 2020

Dựng simple project với nextjs, redux, reactjs , redux-saga, học phải đi đôi với hành :#)

Đồ chơi.

The React Framework https://nextjs.org
  • Bộ combo trọn gói mì ăn liền nextjs, hỗ trợ từ đầu đến đuôi, từ frontend tới backend, server side rendering.
  • Mình sẽ làm thử một cái notebook cho việc ghi chú bằng thằng này :#).

Cấu trúc folder mình học được từ các cao nhân trên github.

API thì chúng ta bỏ vào đây, code này wrapper express để chạy phía server, cách đặt tên thư mục và tên file sẽ quyết định đường dẫn nhé.
Như trên nó sẽ có đường dẫn /api/note/{noteID}.
Một số code index vào elasticsearch content gửi lên khakha :v
export default (req, res) => {
  if (req.method === 'POST') {
    const { id } = req.query;
    client.index({
      index: 'wnote',
      id: id,
      type: 'note',
      body: req.body
    },function(error, response, status) {
        if (error){
          console.log("index error: "+error)
        } else {
          res.statusCode = 200
          res.setHeader('Content-Type', 'application/json')
          try {
            var body = JSON.parse(response.meta.request.params.body);
          } catch (e) {
            res.status(400).json('fail')
          }

          body = fnBuildResponse(id, body)
          res.status(200).json(body)
        }
    });
  } else if (req.method == 'GET') {
    const { id } = req.query;
    client.search({
      index: 'wnote',
      body: {
        query: {
          match: {_id: id}
        },
      }
    },function(error, response, status) {
        if (error){
          console.log("index error: "+error)
        } else {
          res.statusCode = 200
          res.setHeader('Content-Type', 'application/json')
          res.status(200).json(response.body.hits)
        }
    });
  }
}
Ở client cũng vậy, Router sẽ dựa vào cách mà bạn đặt tên file và thư mục.
Như trên bạn sẽ có đường dẫn ở client là http://localhost:3000/w/ba9d4acc-0fd4-4b75-8e71-4b581865cb29, tương ứng với thư mục w, và file [id].js, ở đây id = "ba9d....."
Về style ư, quá dễ dàng chỉ cần tạo file scss code ngon ăn rồi import vào file _app.js
import "./w/[id].scss";

import App from 'next/app';
import React from 'react';

class MyApp extends App {

    ....
}
Cách tương tác với redux , redux saga cũng giống như bình thường, chả có gì mới :#), nhờ vào package next-redux-wrapper, import vào và ăn liền, chẳng cần hiểu tại sao :v
_app.js
import "./w/[id].scss";

import App from 'next/app';
import {Provider} from 'react-redux';
import React from 'react';
import withRedux from "next-redux-wrapper";
import store from '../redux/store';

class MyApp extends App {

    static async getInitialProps({Component, ctx}) {
        const pageProps = Component.getInitialProps ? await Component.getInitialProps(ctx) : {};

        //Anything returned here can be accessed by the client
        return {pageProps: pageProps};
    }

    render() {
        //pageProps that were returned  from 'getInitialProps' are stored in the props i.e. pageprops
        const {Component, pageProps, store} = this.props;

        return (
            <Provider store={store}>
                <Component {...pageProps}/>
            </Provider>
        );
    }
}

//makeStore function that returns a new store for every request
const makeStore = () => store;

//withRedux wrapper that passes the store to the App Component
export default withRedux(makeStore)(MyApp);
Show hàng:
Quá nhẹ nhàng cho việc làm quen một framework ngon ăn 👍

Thứ Ba, 25 tháng 2, 2020

Authentication cho socket.io

Về việc authentication, hẳn khi làm việc với HTTP đa phần đều đã được hỗ trợ rất kĩ với 2 kĩ thuật session và token. Hôm nay mình xin đề cập đến authentication cho giao thức socket và kĩ thuật mình muốn giới thiệu tới là JSON Web Tokens

JSON Web Tokens

JSON Web Tokens (JWT) là một chuẩn để mang thông tin dưới dạng json. Nó mang tất cả thông tin bên trong chính nó, đó là khả năng tự mô tả. Nó thường được pass vào HTTP header để authentication cho API Nó là một chuổi được chia thành 3 phần, được chia tách mới dấu dot:
aaaaaaaaaa.bbbbbbbbbbb.cccccccccccc
Bao gồm:
  • header
  • payload
  • signature
Ở đây:
  • Header có dạng:
{
  "typ": "JWT",
  "alg": "HS256"
}
mô tả loại và thuật toán để hash
  • Payload mang theo thông tin user, bất cứ data nào chúng ta muốn đính kèm cho quá trình auth
{
  "iss": "chatbot.dev",
  "exp": 1300819380,
  "name": "Phan Ngoc",
  "admin": true
}
  • Phần thứ 3 là secret, nó là thành phần được server mã hóa thông qua 1 secret key, được server dùng để verify token hiện tại hoặc để tạo 1 cái mới.

Các bước để auth.

Mình muốn giới thiệu một packet nổi tiếng cho việc verify vào tạo token trong nodejs là: https://github.com/auth0/node-jsonwebtoken Đây là ví dụ cho việc sinh token:
// sign with default (HMAC SHA256)
var jwt = require('jsonwebtoken');
var token = jwt.sign({ foo: 'bar' }, 'shhhhh');
//backdate a jwt 30 seconds
var older_token = jwt.sign({ foo: 'bar', iat: Math.floor(Date.now() / 1000) - 30 }, 'shhhhh');

// sign with RSA SHA256
var cert = fs.readFileSync('private.key');  // get private key
var token = jwt.sign({ foo: 'bar' }, cert, { algorithm: 'RS256'});
Lưu ý là file private.key sẽ chứa secret key của chúng ta, nó chỉ được lưu trữ ở server. Để sinh ra token chúng ta chỉ cần:
// sign asynchronously
jwt.sign({ foo: 'bar' }, cert, { algorithm: 'RS256' }, function(err, token) {
  console.log(token);
});
Để verify token chúng ta cần:
// verify a token symmetric
jwt.verify(token, 'secret key', function(err, decoded) {
  console.log(decoded.foo) // bar
});
Biến decoded sẽ mang theo thông tin payload của chúng ta.

Tiến hành auth cho socket.

Để auth cho giao thức socket, chúng ta tiến hành sinh token và gửi xuống client, khi client tiến hành handsocket với server, nó phải pass lại token đó để verify thông tin.
socket = io.connect('http://localhost', {
  query: "token=" + myAuthToken
});
Ở server chúng ta tiến hành get lại token, thông qua middleware mà socket io hỗ trợ:
io.use(function(socket, next) {
  var token = socket.request.query.token;
  checkAuthToken(token, function(err, authorized){
    if (err || !authorized) {
      next(new Error("not authorized"));
    }
    next();
  });
});
Tuy nhiên cách làm trên gặp một số vấn đề về security, đặc biệt là khi pass token trong query string. Ở đây chúng ta có thể cải thiện bằng cách cho user connect tới socket rồi sau đó mới emit token cho server auth, một khi user được auth chúng ta mới cho emit và listen sự kiện.
var io = require('socket.io').listen(app);
 
io.on('connection', function(socket){
  socket.auth = false;
  socket.on('authenticate', function(data){
    // check data được send tới client
    checkAuthToken(data.token, function(err, success){
      if (!err && success){
        console.log("Authenticated socket ", socket.id);
        socket.auth = true;
      }
    });
  });
 
  setTimeout(function(){
    //sau 1s mà client vẫn chưa dc auth, lúc đấy chúng ta mới disconnect.
    if (!socket.auth) {
      console.log("Disconnecting socket ", socket.id);
      socket.disconnect('unauthorized');
    }
  }, 1000);
}
Ở client chúng ta sẽ sửa thành:
var socket = io.connect('http://localhost');
socket.on('connect', function(){
  socket.emit('authenticate', {token: myAuthToken});
});
Chúng ta cần ngăn chặn client nhận broadcast messages khi được connect mà vẫn chưa được authentication:
var _ = require('underscore');
var io = require('socket.io').listen(app);
 
_.each(io.nsps, function(nsp){
  nsp.on('connect', function(socket){
    if (!socket.auth) {
      console.log("removing socket from", nsp.name)
      delete nsp.connected[socket.id];
    }
  });
});
Và khi authentication hoàn tất chúng ta sẽ gán socket id đó lại vào mảng socket namespace cần tracking cho việc nhận boardcast message hay listen event.
socket.on('authenticate', function(data){
  //check the auth data sent by the client
  checkAuthToken(data.token, function(err, success){
    if (!err && success){
      console.log("Authenticated socket ", socket.id);
      socket.auth = true;
 
      _.each(io.nsps, function(nsp) {
        if(_.findWhere(nsp.sockets, {id: socket.id})) {
          console.log("restoring socket to", nsp.name);
          nsp.connected[socket.id] = socket;
        }
      });
 
    }
  });
});
Hy vọng các bạn có cái nhìn tổng quan về authentication cho socket. Cảm ơn các bạn đã đọc !

Thứ Sáu, 21 tháng 2, 2020

Sơ lược Word2vec

  • Cách truyền thống để thể hiện 1 từ là dùng one-hot vector.
  • Độ lớn vector đúng bằng số lượng từ vựng.
  • Vấn đề là làm thế nào để thể hiện mối quan hệ giữa các từ, tính tương đồng thế nào. Word2vec là giải pháp cho vấn đề này.
  • Có 2 mô hình Word2vec được áp dụng: Skip-gram, Continuous Bag of Words (CBOW)
  1. Skip-gram
Input là từ cần tìm mối quan hệ, output là từ các từ có quan hệ gần nhất với từ đó.
Ví dụ câu: "I have a cute dog", input từ "a", output là “I”, “have”, “cute”, “dog”.  
  1. Continuous Bag of Words
CBOW thì ngược lại, input context, output là từ gần nhất với contenxt đó.
  • Mô hình tranning:
  • Cách tính toán cơ bản:
  1. Tính sigmoid probability
import math
z = [1.0, 2.0, 3.0, 4.0, 1.0, 2.0, 3.0]
z_exp = [math.exp(i) for i in z]
print([round(i, 2) for i in z_exp])
[2.72, 7.39, 20.09, 54.6, 2.72, 7.39, 20.09]
sum_z_exp = sum(z_exp)
print(round(sum_z_exp, 2))
114.98
softmax = [i / sum_z_exp for i in z_exp]
print([round(i, 3) for i in softmax])
[0.024, 0.064, 0.175, 0.475, 0.024, 0.064, 0.175]
  • Ví dụ dùng Numpy:
import numpy as np
z = [1.0, 2.0, 3.0, 4.0, 1.0, 2.0, 3.0]
softmax = np.exp(z)/np.sum(np.exp(z))
softmax
array([0.02364054, 0.06426166, 0.1746813 , 0.474833 , 0.02364054, 0.06426166, 0.1746813 ])
  1. Dự đoán probability của từ:
  • Dùng gensim cho word2vec:
num_features = 300  # Word vector dimensionality
min_word_count = 2 # Minimum word count
num_workers = 4     # Number of parallel threads
context = 10        # Context window size
downsampling = 1e-3 # (0.001) Downsample setting for frequent words

# Initializing the train model
from gensim.models import word2vec
print("Training model....", len(sentences))
model = word2vec.Word2Vec(sentences,\
                          workers=num_workers,\
                          size=num_features,\
                          min_count=min_word_count,\
                          window=context,
                          sample=downsampling)

# To make the model memory efficient
model.init_sims(replace=True)

# Saving the model for later use. Can be loaded using Word2Vec.load()
model_name = "300features_40minwords_10context"
model.save(model_name)
model.wv.most_similar("awful")
[('also', 0.5430739521980286),
 ('of', 0.5334444046020508),
 ('that', 0.5331112742424011),
 ('with', 0.5315108299255371),
 ('s', 0.5286026000976562),
 ('it', 0.5267502069473267),
 ('be', 0.5258522033691406),
 ('but', 0.5237830877304077),
 ('time', 0.5198161602020264),
 ('way', 0.5197839140892029)]
  • Một nhược điểm lớn, là nó không detect được những từ không có trong traning dataset, để khắc phục được điều này chúng ta có FastText là mở rộng của Word2Vec, được suggest bởi facebook năm 2016. Thay thế cho đơn vị word, nó chia text ra làm nhiều đoạn nhỏ, ví dụ apple sẽ thành app, ppl, and ple, vector của từ apple sẽ bằng tổng của tất cả cái này.
  • Cảm ơn các bạn đã theo dõi. 😃
  • Tham khảo:

Thứ Bảy, 15 tháng 2, 2020

Giới thiệu Principal Component Analysis

Mở đầu.

Đây là thuật toán sinh ra để giải quyết vấn đề dữ liệu có quá nhiều chiều dữ liệu, cần giảm bớt chiều dữ liệu nhằm tăng tốc độ xử lí, nhưng vẫn giữ lại thông tin nhiều nhất có thể (high variance).
  • Chúng ta cần tìm ra chiều dữ liệu có độ quan trọng cao, nhằm giảm bớt việc tính toán, cũng như tăng tốc độ xử lí. 
  • PCA chuyển dữ liệu từ linear thành các thuộc tính mới không liên quan lẫn nhau.

Dữ liệu.

Chúng ta cần phân biệt 2 loại dữ liệu:
  1. Dữ liệu liên quan (correlated):
  1. Dữ liệu không liên quan (uncorrelated):
PCA tìm ra mean và principal components.
 

Làm thế nào để implement PCA:

  • Biến đổi X về dạng đồng nhất.
  • Tính toán covariance matrix Σ
  • Tìm eigenvectors của Σ
  • Lấy K dimensions có giá trị variance cao nhất

eigenvectors (vector màu đỏ)

là vector không thay đổi hướng khi apply linear transformation.

eigenvalue cho PC1

eigenvalue cho PC2

eigenvector

Sự phân bổ độ quan trọng của chiều dữ liệu

 

Algorithm

from numpy import array
from numpy import mean
from numpy import cov
from numpy.linalg import eig
# define a matrix
A = array([[1, 2], [3, 4], [5, 6]])
print(A)
# calculate the mean of each column
M = mean(A.T, axis=1)
print(M)
# center columns by subtracting column means
C = A - M
print(C)
# calculate covariance matrix of centered matrix
V = cov(C.T)
print(V)
# eigendecomposition of covariance matrix
values, vectors = eig(V)
print(vectors)
print(values)
# project data
P = vectors.T.dot(C.T)
print(P.T)
Output:
[[1 2]
 [3 4]
 [5 6]]

[[ 0.70710678 -0.70710678]
 [ 0.70710678  0.70710678]]

[ 8.  0.]

[[-2.82842712  0.        ]
 [ 0.          0.        ]
 [ 2.82842712  0.        ]]

Kết.

  • Đây chỉ bài viết mang mục đích giới thiệu, hy vọng các bạn có cái nhìn tổng quan về nó, 😆😀
Reference:

Giới thiệu sơ lược về NMF (nonnegative matrix factorization)

Giới thiệu. 
NMF chuyển một matrix X thành phép nhân 2 maxtrix cấp thấp hơn với độ xấp xỉ và sai số nhỏ. Mục đích để giảm cho việc lưu trữ và việc tính toán nhưng vẫn đảm bảo được các đặc điểm của dữ liệu (các đặc tính của mô hình).
Như trên, chúng ta có một ma trận dữ liệu X (p x n), mục đích của NMF là giảm chiều dữ liệu từ p xuống r thông qua việc tìm 2 ma trận con có phép nhân ~= X Để làm được vậy chúng ta thông qua việc
  • random dữ liệu ban đầu.
  • So sánh các dữ liệu sinh ra với ma trận kết quả X.
  • điều chỉnh lại các thông số cho hợp lí => để tối ưu hàm lỗi (error function).
  • lặp lại các bước trên cho đến khi lỗi đủ nhỏ (đủ tốt)

Ví dụ. (ứng dụng trong việc dự đoán phìm của netflix bình chọn của NMF):

Chúng ta có 4 người, với 2 thể loại phim là "comedy" và "action", ma trận X tương đương với ma trận lớn, các con số là số điểm rating bộ phim) ma trận "trái" "trên" tương đương với các ma trận cần tìm (phân tách).
Như bạn thấy, với ma trận lớn ta cần 2 triệu entries để lưu trữ, trong khi việc phân tách ra 2 ma trận sẽ chỉ tốn 300.000 entries
Để tìm được 2 ma trận này ta random các giá trị khởi tạo, tính toán và so sánh với ma trận gốc.
1.44 là nhỏ hơn 3, nên ta cần nâng các param lên.
Hoặc giảm xuống (như đối với giá trị tiếp theo).
Error function sẽ bằng tổng bình phương chênh lệch, đạo hàm của nó chính là cái chúng ta cần tối ưu.
Sau khi tìm được 2 ma trận tương ứng, chúng ta có thể dự đoán được những điểm dữ liệu bị thiếu dựa vào việc nhân ma trận (vì dữ liệu thực tế thường không đầy đủ, rời rạc, chúng ta có thể filling các giá trị giả định, sau khi tìm được các ma trận phù hơp, chúng ta có thể quay lại dùng phép nhân ma trận để dự đoán các dữ liệu bị thiếu).
Hy vọng sẽ giúp bạn hiểu phần nào NMF. Cảm ơn mọi người (bow)

Thứ Hai, 17 tháng 12, 2018

Giới thiệu thuật toán Kd Trees (Nearest neighbour search)

Sơ lược:

 
  • Kd-trees dùng để tìm kiếm các dữ liệu gần, liên quan nhất (neighbouring data points) trong miền không gian 2 chiều, hoặc nhiều chiều.
  • Kd-trees thuộc họ Nearest neighbor (NN) search.

Tóm tắt:

  1. Cách build Kd-trees từ tranning data:
  • chọn 1 chiều random, tìm toạ độ trung bình, chia data theo toạ độ đó, lặp lại.
  1. Cách tìm các dữ liệu liên quan cho point (7,4)
  • tìm các phân vùng chứa điểm (7,4)
  • so sánh khoảng cách điểm đó tới tất cả các điểm trong phân vùng để chọn cái gần nhất.

Chi tiết:

  1. Code build tree:
from collections import namedtuple
from operator import itemgetter
from pprint import pformat
 
class Node(namedtuple('Node', 'location left_child right_child')):
 
    def __repr__(self):
        return pformat(tuple(self))
 
def kdtree(point_list, depth=0):
    """ build K-D tree
    :param point_list list of input points
    :param depth      current tree's depth
    :return tree node
    """
 
    # assumes all points have the same dimension
    try:
        k = len(point_list[0])
    except IndexError:
        return None
 
    # Select axis based on depth so that axis cycles through
    # all valid values
    axis = depth % k
 
    # Sort point list and choose median as pivot element
    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2         # choose median
 
    # Create node and construct subtrees
    return Node(
        location=point_list[median],
        left_child=kdtree(point_list[:median], depth + 1),
        right_child=kdtree(point_list[median + 1:], depth + 1)
    )
  1. Từ tree có được, ta build hàm tìm các điểm neighbour của một điểm cho trước:
Cách search như sau:
  • Bắt đầu root node, move qua các nhánh một cách đệ quy.
  • Trong khi lướt qua các nhánh, thuật toán sẽ lưu lại node có khoảng cách ngắn nhất với khoảng cách chưa target point (là điểm cần tìm neghibour), được gọi là current best (tốt nhất hiện tại)
  • Nếu node hiện tại gần target point hơn current best, nó sẽ trở thành current best.
  • Trong khi di chuyển nó sẽ check xem, với điểm current best ở nhánh trái thì distance best(khoảng cách từ target point tới current best) có ngắn hơn khoảng cách từ target point tới bờ phân chia hay không, nếu ngắn hơn tức là bên nhánh trái đã cho kết quả tốt nhất và ta không cần tìm tiếp bên phải, nếu dài hơn tức là có lẽ sẽ có 1 điểm nào đó bên phải cho khoảng cách tới target point tốt hơn nên ta phải tiếp tục loop qua các nhánh bên phải. 
  • Với mỗi nhánh, thuật toán hoàn thành cho tới khi chạm leaf node.
Code
nearest_nn = None           # nearest neighbor (NN)
distance_nn = float('inf')  # distance from NN to target
 
def nearest_neighbor_search(tree, target_point, hr, distance, nearest=None, depth=0):
    """ Find the nearest neighbor for the given point (claims O(log(n)) complexity)
    :param tree         K-D tree
    :param target_point given point for the NN search
    :param hr           splitting hyperplane
    :param distance     minimal distance
    :param nearest      nearest point
    :param depth        tree's depth
    """
 
    global nearest_nn
    global distance_nn
 
    if tree is None:
        return
 
    k = len(target_point)
 
    cur_node = tree.location         # current tree's node
    left_branch = tree.left_child    # its left branch
    right_branch = tree.right_child  # its right branch
 
    nearer_kd = further_kd = None
    nearer_hr = further_hr = None
    left_hr = right_hr = None
 
    # Select axis based on depth so that axis cycles through all valid values
    axis = depth % k
 
    # split the hyperplane depending on the axis
    if axis == 0:
        left_hr = [hr[0], (cur_node[0], hr[1][1])]
        right_hr = [(cur_node[0],hr[0][1]), hr[1]]
 
    if axis == 1:
        left_hr = [(hr[0][0], cur_node[1]), hr[1]]
        right_hr = [hr[0], (hr[1][0], cur_node[1])]
 
    # check which hyperplane the target point belongs to
    if target_point[axis] <= cur_node[axis]:
        nearer_kd = left_branch
        further_kd = right_branch
        nearer_hr = left_hr
        further_hr = right_hr
 
    if target_point[axis] > cur_node[axis]:
        nearer_kd = right_branch
        further_kd = left_branch
        nearer_hr = right_hr
        further_hr = left_hr
 
    # check whether the current node is closer
    dist = (cur_node[0] - target_point[0])**2 + (cur_node[1] - target_point[1])**2
 
    if dist < distance:
        nearest = cur_node
        distance = dist
 
    # go deeper in the tree
    nearest_neighbor_search(nearer_kd, target_point, nearer_hr, distance, nearest, depth+1)
 
    # once we reached the leaf node we check whether there are closer points
    # inside the hypersphere
    if distance < distance_nn:
        nearest_nn = nearest
        distance_nn = distance
 
    # a nearer point (px,py) could only be in further_kd (further_hr) -> explore it
    px = compute_closest_coordinate(target_point[0], further_hr[0][0], further_hr[1][0])
    py = compute_closest_coordinate(target_point[1], further_hr[1][1], further_hr[0][1])
 
    # check whether it is closer than the current nearest neighbor => whether a hypersphere crosses the hyperplane
    dist = (px - target_point[0])**2 + (py - target_point[1])**2
 
    # explore the further kd-tree / hyperplane if necessary
    if dist < distance_nn:
        nearest_neighbor_search(further_kd, target_point, further_hr, distance, nearest, depth+1)
  1. Chạy thử:

Dùng với scikit-learn:

  1. Dùng sklearn:
>>> import numpy as np
>>> np.random.seed(0)
>>> X = np.random.random((10, 3))  # 10 points in 3 dimensions
>>> tree = KDTree(X, leaf_size=2)              
>>> dist, ind = tree.query([X[0]], k=3)                
>>> print(ind)  # indices of 3 closest neighbors
[0 3 1]
>>> print(dist)  # distances to 3 closest neighbors
[ 0.          0.19662693  0.29473397]



Cảm ơn các bạn đã đọc, happy learning 😄

Reference: